Legendre symbol : legendre_symbol

If n is prime, we define the Legendre symbol of a written $\left(\vphantom{\frac{a}{n}}\right.$${\frac{{a}}{{n}}}$$\left.\vphantom{\frac{a}{n}}\right)$ by :

$$\left(\vphantom{\frac{a}{n}}\right.$$$${\frac{{a}}{{n}}}$$$$\left.\vphantom{\frac{a}{n}}\right)$$ = $$\left\{\vphantom{\begin{array}{rl} 0 & \mbox{if }a=0\ \bmod n \\ ... ...f } a \neq 0 \bmod n \mbox{ and if } a \neq b^2 \bmod n\\ \end{array}}\right.$$$$\begin{array}{rl} 0 & \mbox{if }a=0\ \bmod n \\ 1 & \mbox{if } ... ... \mbox{if } a \neq 0 \bmod n \mbox{ and if } a \neq b^2 \bmod n\\ \end{array}$$

Some properties

• If n is prime :
  a^{${\frac{}{}}$}n-12 = $$\left(\vphantom{\frac{a}{n}}\right.$$$${\frac{{a}}{{n}}}$$$$\left.\vphantom{\frac{a}{n}}\right)$$ mod n

• 
  

  $$\left(\vphantom{\frac{p}{q}}\right. {\frac{{p}}{{q}}} \left.\vphantom{\frac{p}{q}}\right) \left(\vphantom{\frac{q}{p}}\right. {\frac{{q}}{{p}}} \left.\vphantom{\frac{q}{p}}\right) {\frac{{p-1}}{{2}}} {\frac{{q-1}}{{2}}} \mbox{ if $p$\ and $q$\ are odd and positive}$$ =

  $$\left(\vphantom{\frac{2}{p}}\right. {\frac{{2}}{{p}}} \left.\vphantom{\frac{2}{p}}\right) {\frac{{p^2-1}}{{8}}}$$ =

  $$\left(\vphantom{\frac{-1}{p}}\right. {\frac{{-1}}{{p}}} \left.\vphantom{\frac{-1}{p}}\right) {\frac{{p-1}}{{2}}}$$ =

  
  

legendre_symbol takes two arguments a and n and returns the Legendre symbol $\left(\vphantom{\frac{a}{n}}\right.$${\frac{{a}}{{n}}}$$\left.\vphantom{\frac{a}{n}}\right)$.
Input :

legendre_symbol(26,17)

Output :

1

Input :

legendre_symbol(27,17)

Output :

-1

Input :

legendre_symbol(34,17)

Output :

0