Fermat's Little Theorem and Euler's Theorem
Prove that raising a unit to the size of the unit group returns one, and use it to shortcut enormous modular powers.
What a learner can do afterwards
- Prove Fermat's little theorem by permuting the nonzero residues
- Compute Euler's totient function and state the general theorem
- Reduce a huge exponent modulo the totient before computing the power
1 · Read
Fermat's little theorem says a to the power (p minus 1) leaves remainder 1 modulo p, for prime p not dividing a. So 2 to the power 10 is 1 modulo 11. The proof permutes the nonzero residues: multiplying them all by a just reshuffles the list.
Euler widened the idea with the totient. Phi of n counts numbers from 1 to n that share no factor with n: phi of 9 is 6, namely 1, 2, 4, 5, 7, 8, and phi of 12 is 4. His theorem says a to the phi of n is 1 modulo n whenever a and n are coprime.
That turns huge powers into small ones. For 3 to the 100th modulo 7, phi of 7 is 6, and 100 equals 96 plus 4. So the power reduces to 3 to the 4th, which is 81, and 81 modulo 7 is 4.
Reduce the exponent modulo the totient, never modulo n itself. Then finish with fast squaring: square down the binary form of the exponent, multiplying by the base only at set bits. A million multiplications shrink to about twenty steps.
Spot the prime or the totient, shrink the exponent, and compute the small power that remains.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.