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.
 
//Jacobi Symbol. Nigel Galloway: July 14th., 2020
let J n m=let rec J n m g=match n with
                           0->if m=1 then g else 0
                          |n when n%2=0->J(n/2) m (if m%8=3 || m%8=5 then -g else g)
                          |n->J (m%n) n (if m%4=3 && n%4=3 then -g else g) 
          J (n%m) m 1
printfn "n\m   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30\n     ----------------------------------------------------------------------------------------------------------------------"
[1..2..29]|>List.iter(fun m->printf "%3d" m; [1..30]|>List.iter(fun n->printf "%4d" (J n m)); printfn "")
 