Definition (Legendre symbol)
If p p p odd prime , and a ∈ Z a\in\mathbb{Z} a ∈ Z Legendre Symbol , written as ( a p ) \left( \frac{a}{p} \right) ( p a ) ( a p ) = { 0 if p ∣ a 1 if a is a quadratic residue − 1 if a is a non-residue \left( \frac{a}{p} \right)=\begin{cases}
0&\text{if }p|a \\
1&\text{if }a\text{ is a quadratic residue} \\
-1 & \text{if }a\text{ is a non-residue}
\end{cases} ( p a ) = ⎩ ⎨ ⎧ 0 1 − 1 if p ∣ a if a is a quadratic residue if a is a non-residue a a a p p p
Proposition (Properties)
The Legendre Symbol satisfies:
( a p ) \left( \frac{a}{p} \right) ( p a ) a ( m o d p ) a\pmod{p} a ( mod p ) ( a b p ) = ( a p ) ( b p ) \left( \frac{ab}{p} \right)=\left( \frac{a}{p} \right)\left( \frac{b}{p} \right) ( p ab ) = ( p a ) ( p b ) For any b b b coprime to p p p ( a b 2 p ) = ( a p ) \left( \frac{ab^{2}}{p} \right)=\left( \frac{a}{p} \right) ( p a b 2 ) = ( p a )
( − 1 p ) = ( − 1 ) p − 1 2 \left( \frac{-1}{p} \right)=(-1)^{\frac{p-1}{2}} ( p − 1 ) = ( − 1 ) 2 p − 1
Proposition (Euler’s criterion)
a p − 1 2 ≡ ( a p ) ( m o d p ) a^{ \frac{p-1}{2} }\equiv\left( \frac{a}{p} \right)\pmod{p} a 2 p − 1 ≡ ( p a ) ( mod p )
Proposition (3)
For a prime p ≡ 1 ( m o d 4 ) p\equiv1\pmod{4} p ≡ 1 ( mod 4 ) [ ( p − 1 2 ) ! ] 2 ≡ − 1 ( m o d p ) \left[ \left( \frac{p-1}{2} \right)! \right]^{2}\equiv-1\pmod{p} [ ( 2 p − 1 ) ! ] 2 ≡ − 1 ( mod p ) x 2 ≡ − 1 ( m o d p ) x^{2}\equiv-1\pmod{p} x 2 ≡ − 1 ( mod p )
Theorem (Quadratic Reciprocity of Legendre)
If p p p q q q odd primes , then the Legendre Symbol satisfies: ( p q ) = ( − 1 ) ( p − 1 ) ( q − 1 ) 4 ( q p ) \left( \frac{p}{q} \right)=(-1)^{\frac{(p-1)(q-1)}{4}}\left( \frac{q}{p} \right) ( q p ) = ( − 1 ) 4 ( p − 1 ) ( q − 1 ) ( p q )