Square Roots of One Modulo p
For prime : holds exactly for .
Lemma 4.34
Let be a prime. Then .
Proof
where the fourth step applies Euclid’s lemma to the prime , and conversely.
Primality is necessary
Primality is essential for this to hold: has the four solutions .
Bound on polynomial roots
More generally, a non-zero polynomial of degree over has at most roots . The lemma above is the case for the polynomial .
Related
Stated in
- Lemma 4.34§4.7 Prime Modular Arithmetic