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.
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.
Totient and permutation questions x3 and x5 are original in-repo writing; other items adapt problems, academy and textbooks material with unknown license terms. Readings "Modular exponentiation", "Fast modular exponentiation" and "Trial division" adapt academy material with unknown license terms. The rewritten readings were written for this dataset.
2 · Watch
به انگلیسیTake it off screen
Where it sits
Optional connections
14 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.