Fermat’s Little Theorem states that for a prime modulus p and an integer a not divisible by p, a^(p−1) ≡ 1 mod p. This exponent relation turns modular powers into practical tests and algorithms, especially for quadratic residues and finite-field square roots. section 2.4
Use the theorem operationally in these ways:
- Test whether a value may have a square root modulo p by first checking its quadratic-residue status. section 2.4
- For p ≡ 3 mod 4, compute a square root of a with x = a^((p+1)/4) mod p. section 2.5
- For p ≡ 1 mod 4, use Tonelli–Shanks: factor p−1 as 2^e q, choose a quadratic nonresidue, initialize the state, and iteratively reduce the error term. section 2.5
- Extend the exponent relation to a field with p^k elements: for a prime polynomial f of degree k, x^(p^k−1) ≡ 1 mod f. section 9.6
A degree-two extension over 43
Use the irreducible polynomial x² + x + 3 mod 43. The extension contains 43² = 1849 elements, so raising a nonzero polynomial to 1848 = 43²−1 produces 1. For example, (11x + 3)^1848 = 1. section 9.3
