next up previous contents index
suivant: Combinatory analysis monter: Integers (and Gaussian Integers) précédent: Legendre symbol : legendre_symbol   Table des matières   Index


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 = p1$\scriptstyle \alpha_{1}$..pk$\scriptstyle \alpha_{k}$

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

$\displaystyle \left(\vphantom{\frac{a}{n}}\right.$$\displaystyle {\frac{{a}}{{n}}}$$\displaystyle \left.\vphantom{\frac{a}{n}}\right)$ = $\displaystyle \left(\vphantom{\frac{a}{p_1}}\right.$$\displaystyle {\frac{{a}}{{p_1}}}$$\displaystyle \left.\vphantom{\frac{a}{p_1}}\right)^{{\alpha _1}}_{}$...$\displaystyle \left(\vphantom{\frac{a}{p_k}}\right.$$\displaystyle {\frac{{a}}{{p_k}}}$$\displaystyle \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



giac documentation written by Renée De Graeve and Bernard Parisse