Jacobi symbol : jacobi_symbol

If n is not prime, the Jacobi symbol of a, denoted as $\left(\vphantom{\frac{a}{n}}\right.$${\frac{{a}}{{n}}}$$\left.\vphantom{\frac{a}{n}}\right)$, is defined from the Legendre symbol and from the decomposition of n into prime factors. Let

n = p₁^$\alpha_{1}$..p_k^$\alpha_{k}$

where p_j is prime and $\alpha_{j}^{}$ is an integer for j = 1..k. The Jacobi symbol of a is defined by :

$$\left(\vphantom{\frac{a}{n}}\right.$$$${\frac{{a}}{{n}}}$$$$\left.\vphantom{\frac{a}{n}}\right)$$ = $$\left(\vphantom{\frac{a}{p_1}}\right.$$$${\frac{{a}}{{p_1}}}$$$$\left.\vphantom{\frac{a}{p_1}}\right)^{{\alpha _1}}_{}$$...$$\left(\vphantom{\frac{a}{p_k}}\right.$$$${\frac{{a}}{{p_k}}}$$$$\left.\vphantom{\frac{a}{p_k}}\right)^{{\alpha _k}}_{}$$

jacobi_symbol takes two arguments a and n, and it returns the Jacobi symbol $\left(\vphantom{\frac{a}{n}}\right.$${\frac{{a}}{{n}}}$$\left.\vphantom{\frac{a}{n}}\right)$.
Input :

jacobi_symbol(25,12)

Output :

1

Input :

jacobi_symbol(35,12)

Output :

-1

Input :

jacobi_symbol(33,12)

Output :

0