### 5.6.27 Jacobi symbol : jacobi_symbol

If n is not prime, the Jacobi symbol of a,
denoted as (a/n), is defined
from the Legendre symbol and from the
decomposition of n into prime factors.
Let

n=p_{1}^{α 1}..p_{k}^{α k} |

where p_{j} is prime and α _{j} is an integer for j=1..k.
The Jacobi symbol of a is defined by :

⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ | = | ⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ | | ... | ⎛
⎜
⎜
⎝ | | ⎞
⎟
⎟
⎠ | | |

jacobi_symbol takes two arguments a and n, and it returns the Jacobi
symbol (a/n).

Input :

jacobi_symbol(25,12)

Output :

1

Input :

jacobi_symbol(35,12)

Output :

-1

Input :

jacobi_symbol(33,12)

Output :

0