; chinese remainder theorem

(define (euclid x y)
  (let loop ((a 1) (b 0) (g x) (u 0) (v 1) (w y))
    (if (zero? w) (values a b g)
      (let ((q (quotient g w)))
        (loop u v w (- a (* q u)) (- b (* q v)) (- g (* q w)))))))

(define (inverse x m)
  (if (not (= (gcd x m) 1))
      (error 'inverse "divisor must be coprime to modulus")
      (call-with-values
        (lambda () (euclid x m))
        (lambda (a b g) (modulo a m)))))

(define (chinese-remainder as ms)
  (let ((p (apply * ms)))
    (define (f a m)
      (let* ((t (/ p m)) (b (inverse t m)))
        (* a b t)))
    (modulo (apply + (map f as ms)) p)))

(display (chinese-remainder '(2 3 2) '(3 5 7))) (newline)

23