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.
F jacobi(=a, =n)
   I n <= 0
      X ValueError(‘'n' must be a positive integer.’)
   I n % 2 == 0
      X ValueError(‘'n' must be odd.’)
   a %= n
   V result = 1
   L a != 0
      L a % 2 == 0
         a /= 2
         V n_mod_8 = n % 8
         I n_mod_8 C (3, 5)
            result = -result
      (a, n) = (n, a)
      I a % 4 == 3 & n % 4 == 3
         result = -result
      a %= n
   I n == 1
      R result
   E
      R 0
 
print(‘n\k|’, end' ‘’)
V kmax = 20
L(k) 0..kmax
   print(‘#3’.format(k), end' ‘’)
print("\n----", end' ‘’)
L(k) 0..kmax
   print(end' ‘---’)
print()
L(n) (1..21).step(2)
   print(‘#<2 |’.format(n), end' ‘’)
   L(k) 0..kmax
      print(‘#3’.format(jacobi(k, n)), end' ‘’)
   print()