The Jacobi symbol is a multiplicative function that generalizes the Legendre symbol. Specifically, the Jacobi symbol (a | n) equals the product of the Legendre symbols (a | p_i)^(k_i), where n = p_1^(k_1)*p_2^(k_2)*...*p_i^(k_i) and the Legendre symbol (a | p) denotes the value of a ^ ((p-1)/2) (mod p)

 (a | p) ≡   1     if a is a square (mod p)
 (a | p) ≡ -1     if a is not a square (mod p)
 (a | p) ≡   0     if a ≡ 0 
If n is prime, then the Jacobi symbol (a | n) equals the Legendre symbol (a | n).

Task

Calculate the Jacobi symbol (a | n).

Reference

 Wikipedia article on Jacobi symbol.
(define jacobi (lambda (a n)
		 (let ((a-mod-n (modulo a n)))
		   (if (zero? a-mod-n)
		       (if (= n 1)
			   1
			   0)
		       (if (even? a-mod-n)
			   (case (modulo n 8)
			     ((3 5) (- (jacobi (/ a-mod-n 2) n)))
			     ((1 7) (jacobi (/ a-mod-n 2) n)))
			   (if (and (= (modulo a-mod-n 4) 3) (= (modulo n 4) 3))
			       (- (jacobi n a-mod-n))
			       (jacobi n a-mod-n)))))))