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.
with javascript_semantics
function jacobi(integer a, n)
    atom result = 1
    a = remainder(a,n)
    while a!=0 do
        while remainder(a,2)==0 do
            a /= 2
            if find(remainder(n,8),{3,5}) then result *= -1 end if
        end while
        {a, n} = {n, a}
        if remainder(a,4)==3 and remainder(n,4)==3 then result *= -1 end if
        a = remainder(a,n)
    end while
    return iff(n==1 ? result : 0)
end function
 
printf(1,"n\\a   0   1   2   3   4   5   6   7   8   9  10  11\n")
printf(1,"   ________________________________________________\n")
for n=1 to 31 by 2 do
    printf(1,"%3d", n)
    for a=0 to 11 do
        printf(1,"%4d",jacobi(a, n))
    end for
    printf(1,"\n")
end for
