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.
fcn jacobi(a,n){
   if(n.isEven or n<1) 
      throw(Exception.ValueError("'n' must be a positive odd integer"));
   a=a%n;   result,t := 1,0;
   while(a!=0){
      while(a.isEven){
	 a/=2;   n_mod_8:=n%8;
	 if(n_mod_8==3 or n_mod_8==5) result=-result;
      }
      t,a,n = a,n,t;
      if(a%4==3 and n%4==3) result=-result;
      a=a%n;
   }
   if(n==1) result else 0
}