Note - Quadratic Reciprocity Law and the Legendre Symbol

note quadratic-reciprocity

Quadratic Reciprocity Law

Main Law

For distinct odd primes $p$ and $q$ ,

If $q \equiv 1 mod 4$ , then $q \equiv □ mod p ⟺ p \equiv □ mod q$ .
If $q \equiv 3 mod 4$ , then $- q \equiv □ mod p ⟺ p \equiv □ mod q$ .

Supplementary Law

For odd prime $p$ ,

$- 1 \equiv □ mod p ⟺ p \equiv 1 mod 4$ . (related proof)
$2 \equiv □ mod p ⟺ p \equiv 1, 7 mod 8$ .

Expressing these Using the Legendre Symbol

Properties

$a^{\frac{p - 1}{2}} \equiv (\frac{a}{p}) mod p$ for all $a \in Z$ .
$(\frac{ab}{p}) = (\frac{a}{p}) (\frac{b}{p})$ for all $a, b \in Z$ .

Rewrite Quadratic Reciprocity

If $p$ or $q$ is $1 mod 4$ , then $q \equiv □ mod p ⟺ p \equiv □ mod q$ . $q \equiv □ mod p ⟺ (\frac{q}{p})$ $p \equiv □ mod q ⟺ (\frac{p}{q})$ Thus, if $p$ or $q$ is $1 mod 4$ , then $(\frac{q}{p}) = (\frac{p}{q})$ .

If $p$ and $q$ are $3 mod 4$ , then $- q \equiv □ mod p ⟺ p \equiv □ mod q$ . $- q \equiv □ mod p ⟺ (\frac{- q}{p})$ $p \equiv □ mod q ⟺ (\frac{p}{q})$ Thus, if $p$ and $q$ are $3 mod 4$ , then

By multiplicativity of the Legendre symbol, $p$ and $q$ are $3 mod 4 ⟹ (\frac{- q}{p}) = (\frac{- 1}{p}) (\frac{q}{p}) = - (\frac{q}{p})$ since $- 1 \neq \equiv □ mod p$ when $p \equiv 3 mod 4$ .

New Statement of Main Law

For odd primes $p \neq = q$ ,

$p$ or $q$ is $1 mod 4 ⟹ (\frac{q}{p}) = (\frac{p}{q})$
$p$ or $q$ are $3 mod 4 ⟹ (\frac{q}{p}) = - (\frac{p}{q})$

New Statement of Supplementary Laws

For odd primes $p$ ,

(\frac{- 1}{p}) = {1 - 1 if p \equiv 1 mod 4 if p \equiv 3 mod 4 [p \neq \equiv 1 mod 4]

(\frac{2}{p}) = {1 - 1 if p \equiv 1, 7 mod 8 if p \equiv 3, 5 mod 8 [p \neq \equiv 1, 7 mod 8]

Examples

Is $29 \equiv □ mod 59$ ? ( $(\frac{29}{59}) = 1$ ?) $29, 59$ both primes $29 \equiv 1 mod 4$ $(\frac{29}{59}) = (\frac{59}{29})$ by main law since $29 \equiv 1 mod 4$ $(\frac{29}{59}) = (\frac{1}{29})$ since $59 \equiv 1 mod 29$ $(\frac{29}{59}) = 1$ since $1 \equiv 1^{2} mod 59$ Yes: $29 \equiv □ mod 59$ Search finds that $29 \equiv 1 8^{2} mod 59$
Is $31 \equiv □ mod 59$ ? (What is $(\frac{31}{59})$ ?) Both are prime and $31 \equiv 3 mod 4$ $59 \equiv 3 mod 4$ $(\frac{31}{59}) = - (\frac{59}{31})$ by main law since $31, 59 \equiv 3 mod 4$ $(\frac{31}{59}) = - (\frac{28}{31})$ since $59 \equiv 28 mod 31$ $(\frac{31}{59}) = - (\frac{4 \cdot 7}{31})$ $(\frac{31}{59}) = - (\frac{4}{31}) (\frac{7}{31})$ $(\frac{31}{59}) = - (\frac{7}{31})$ $(\frac{31}{59}) = - (- (\frac{31}{7}))$ since $7, 31 \equiv 3 mod 4$ $(\frac{31}{59}) = (\frac{31}{7}) = (\frac{3}{7}) = - 1$ since $3 \neq \equiv □ mod 7$

My Math Notes

Explorer