Day 75 — Fermat, Euler, totient, order

Updated

July 30, 2026

Day 75 — Fermat’s little theorem, Euler’s theorem, totient, and order

Stage VII · concept day
Goal: Prove/sketch Fermat; state Euler; compute \(\varphi(n)\) for \(p\), \(p^k\), and coprime products; reduce huge exponents; define the multiplicative order of \(a\) mod \(n\).

Why this matters

Exponent reduction is the workhorse of modular powering: RSA literacy, Diffie–Hellman, and simple “last digit / cycle” problems all need Fermat or Euler. Totient arithmetic explains why key exponents live mod \(\varphi(n)\). Order measures the period of powering — the discrete seed of cyclic-group thinking.

Note

No labs. Hand modular exponentiation only. Toy moduli.

Theory

Fermat’s little theorem

Theorem (Fermat). If \(p\) is prime and \(p\nmid a\), then \[ a^{p-1}\equiv 1\pmod p. \] Equivalently (for all integers \(a\)): \(a^p\equiv a\pmod p\).

Proof sketch (multiplication of units).
If \(p\nmid a\), the residues \(a,2a,\ldots,(p-1)a\) are a permutation of \(1,2,\ldots,p-1\) modulo \(p\) (all nonzero, pairwise distinct because \(p\) prime). Multiply: \[ a^{p-1}(p-1)!\equiv (p-1)!\pmod p. \] Cancel \((p-1)!\) (invertible mod \(p\) by Wilson or because \(p\) prime doesn’t divide it): \(a^{p-1}\equiv 1\pmod p\).

Alternate form. \(a^p\equiv a\pmod p\) holds even if \(p\mid a\) (both sides \(0\)).

Consequence. If \(p\nmid a\) then \(a^{-1}\equiv a^{p-2}\pmod p\).

Euler’s totient function

Definition. \(\varphi(n)=\#\{k:1\le k\le n,\ \gcd(k,n)=1\}\) for \(n\ge 1\) (with \(\varphi(1)=1\)).

Formulas.

  1. Prime: \(\varphi(p)=p-1\).
  2. Prime power: \(\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)\).
    (Count: total \(p^k\) residues \(0,\ldots,p^k-1\); subtract multiples of \(p\): there are \(p^{k-1}\) of them.)
  3. Multiplicative: if \(\gcd(m,n)=1\) then \(\varphi(mn)=\varphi(m)\varphi(n)\).
  4. General FTA: if \(n=\prod p_i^{e_i}\) then \[ \varphi(n)=n\prod_{p\mid n}\Bigl(1-\frac{1}{p}\Bigr)=\prod_i p_i^{e_i-1}(p_i-1). \]

Examples. \(\varphi(12)=\varphi(2^2\cdot 3)=12(1-1/2)(1-1/3)=4\). Units: \(1,5,7,11\).
\(\varphi(100)=\varphi(2^2 5^2)=100(1/2)(4/5)=40\).

Euler’s theorem

Theorem (Euler). If \(\gcd(a,n)=1\) then \[ a^{\varphi(n)}\equiv 1\pmod n. \]

Proof sketch. Let \(r_1,\ldots,r_{\varphi(n)}\) be a reduced residue system mod \(n\). Then \(ar_1,\ldots,ar_{\varphi(n)}\) is also a reduced residue system (multiplication by unit permutes units). Product: \[ a^{\varphi(n)}\prod r_i\equiv \prod r_i\pmod n. \] Cancel \(\prod r_i\) (product of units is a unit). Done.

Fermat is the special case \(n=p\), \(\varphi(p)=p-1\).

Caution. Need \(\gcd(a,n)=1\). Counterexample: \(2^{\varphi(8)}=2^4=16\equiv 0\not\equiv 1\pmod 8\).

Reducing huge exponents

If \(\gcd(a,n)=1\): \(a^k=a^{q\cdot\varphi(n)+r}=(a^{\varphi(n)})^q\cdot a^r\equiv 1^q\cdot a^r\equiv a^r\pmod n\) where \(r=k\bmod\varphi(n)\).

If \(n=p\) prime: reduce exponent mod \(p-1\) when \(p\nmid a\).

Chinese Remainder style (literacy): for composite \(n\), sometimes compute \(a^k\bmod p_i^{e_i}\) separately and recombine (Day 78).

When \(\gcd(a,n)\neq 1\): Euler does not apply; use CRT, factorization, or direct patterns.

Order of \(a\) modulo \(n\)

Definition. Let \(\gcd(a,n)=1\). The multiplicative order of \(a\) modulo \(n\), written \(\mathrm{ord}_n(a)\) or \(\mathrm{order}(a\bmod n)\), is the smallest positive integer \(k\) such that \[ a^k\equiv 1\pmod n. \]

Theorem (order divides \(\varphi(n)\)). \(\mathrm{ord}_n(a)\) exists (by Euler, some positive power is \(1\)) and divides \(\varphi(n)\). More generally: \(a^m\equiv 1\pmod n\) iff \(\mathrm{ord}_n(a)\mid m\).

Proof of “divides”. Write \(m=q\cdot\mathrm{ord}+r\) with \(0\le r<\mathrm{ord}\). Then \(a^m=(a^{\mathrm{ord}})^q a^r\equiv a^r\equiv 1\) forces \(r=0\) by minimality of order.

Corollary. Possible orders of units mod \(n\) are the positive divisors of \(\varphi(n)\).

Primitive roots (awareness). If there exists \(g\) with \(\mathrm{ord}_n(g)=\varphi(n)\), then \(g\) is a primitive root mod \(n\). Exist for \(n=2,4,p^k,2p^k\) (odd prime \(p\)) — statement only; not required to prove.

Worked examples

Example 1 — Fermat.
\(3^{6}\equiv 1\pmod 7\) since \(7-1=6\). Check: \(3^1=3\), \(3^2=2\), \(3^3=6\equiv -1\), \(3^6\equiv 1\pmod 7\).

Example 2 — Reduce \(3^{100}\bmod 7\).
\(100=16\cdot 6+4\), so \(3^{100}\equiv 3^4\equiv 81\equiv 4\pmod 7\) (since \(3^6\equiv 1\)). Or \(3^4=(3^2)^2\equiv 2^2=4\).

Example 3 — \(2^{100}\bmod 17\).
\(17\) prime, \(2^{16}\equiv 1\pmod{17}\). \(100=6\cdot 16+4\), so \(2^{100}\equiv 2^4=16\equiv -1\pmod{17}\).

Example 4 — Totient.
\(\varphi(36)=\varphi(2^2 3^2)=36(1-1/2)(1-1/3)=12\).
\(\varphi(p^3)=p^2(p-1)\) for prime \(p\).

Example 5 — Euler.
\(\gcd(7,10)=1\), \(\varphi(10)=4\), so \(7^4\equiv 1\pmod{10}\). Indeed last digit of powers of \(7\): \(7,9,3,1\) cycle length \(4\). Thus \(7^{402}=7^{4\cdot 100+2}\equiv 7^2\equiv 9\pmod{10}\).

Example 6 — Inverse via Euler.
\(7^{-1}\bmod 10\): \(7^{3}\equiv 343\equiv 3\pmod{10}\)? Better: \(7^{\varphi(10)-1}=7^3=343\equiv 3\), and \(7\cdot 3=21\equiv 1\). Yes.

Example 7 — Order of \(2\) mod \(7\).
\(2^1=2\), \(2^2=4\), \(2^3=1\pmod 7\). Order \(3\), and \(3\mid 6=\varphi(7)\).

Example 8 — Order of \(3\) mod \(10\).
\(3^1=3\), \(3^2=9\), \(3^3=7\), \(3^4=1\pmod{10}\). Order \(4=\varphi(10)\).

Example 9 — Failure without coprimality.
\(2^{\varphi(12)}=2^4=16\equiv 4\not\equiv 1\pmod{12}\). \(\gcd(2,12)\neq 1\).

Example 10 — \(a^p\equiv a\pmod p\) for \(a=14\), \(p=5\).
\(14\equiv 4\), \(4^5=1024\), \(1024\bmod 5\): \(4\equiv -1\), \((-1)^5=-1\equiv 4\pmod 5\). Also \(14\equiv 4\).

Exercises

A. Fermat

  1. Compute \(2^{10}\bmod 11\) two ways (direct and Fermat).
  2. Compute \(5^{30}\bmod 13\).
  3. Prove: if \(p\) prime and \(p\nmid a\) then \(a^{p-2}\equiv a^{-1}\pmod p\).
  4. Show \(a^p\equiv a\pmod p\) for \(p\mid a\) and for \(p\nmid a\) (combine cases).
  5. Find \(2^{1000}\bmod 13\).

B. Totient

  1. Compute \(\varphi(n)\) for \(n=1,2,3,4,5,6,7,8,9,10,12,15,16,100\).
  2. Prove \(\varphi(p^k)=p^k-p^{k-1}\) by counting.
  3. Using multiplicativity, prove the product formula \(\varphi(n)=n\prod_{p\mid n}(1-1/p)\).
  4. For which \(n\) is \(\varphi(n)\) odd? (Almost never — characterize.)
  5. Show \(\sum_{d\mid n}\varphi(d)=n\) (hint: cycle lengths / fractions \(k/n\) in lowest terms) — stretch proof or accept as fact and verify for \(n=12\).

C. Euler and reduction

  1. Compute \(3^{100}\bmod 10\).
  2. Compute \(7^{123}\bmod 10\).
  3. Compute \(2^{20}\bmod 21\) carefully — note \(\gcd(2,21)=1\) and \(\varphi(21)=\varphi(3)\varphi(7)=2\cdot 6=12\), so reduce exp mod \(12\).
  4. Why can’t you reduce the exponent of \(2\) mod \(\varphi(8)=4\) to get \(2^k\bmod 8\) for large \(k\)? What is the actual pattern of \(2^k\bmod 8\) for \(k\ge 3\)?
  5. Find \(10^{75}\bmod 21\) using \(\varphi\) if valid; if not, use CRT (optional) or another method.

D. Order

  1. Compute \(\mathrm{ord}_7(a)\) for \(a=1,2,3,4,5,6\).
  2. Compute \(\mathrm{ord}_{13}(2)\) and verify it divides \(12\).
  3. Prove: if \(a^m\equiv 1\pmod n\) and \(k=\mathrm{ord}_n(a)\) then \(k\mid m\).
  4. Prove: \(\mathrm{ord}_n(a^j)=k/\gcd(j,k)\) where \(k=\mathrm{ord}_n(a)\) (standard order lemma — sketch).
  5. Is there a primitive root mod \(8\)? List orders of all units mod \(8\).

E. Stretch and CS literacy

  1. RSA setup preview: if \(n=pq\), explain why working exponents mod \(\varphi(n)=(p-1)(q-1)\) is the right place for \(ed\equiv 1\).
  2. Diffie–Hellman preview: if \(g\) has large order mod \(p\), why does “order large” matter for the discrete log story (prose)?
  3. Prove Euler’s theorem carefully with full sentences (permutation of reduced residues).
  4. Compute \(3^{1000000}\bmod 7\) and mod \(13\), then combine with CRT if you know Day 78 early.
  5. Show that if \(\mathrm{ord}_n(a)=k\) and \(\mathrm{ord}_n(b)=\ell\) with \(\gcd(k,\ell)=1\) and \(ab\equiv ba\), it is not always true that \(\mathrm{ord}_n(ab)=k\ell\) — find conditions or a counterexample (stretch).

Deep dive — exponent reduction recipe card

Goal: compute a^k mod n
1. Reduce a ← a mod n
2. If gcd(a,n)=1:
      e ← φ(n)           // or p-1 if n=p prime
      r ← k mod e
      compute a^r mod n  // binary exponentiation by hand for small
3. If gcd(a,n)>1:
      do NOT use Euler blindly
      options: CRT if n factors; direct pattern; raise carefully

Binary exponentiation (hand). Write \(k\) in binary; successive square \(a, a^2, a^4, \ldots\); multiply factors where bits are \(1\).

Deep dive — order divides \(\varphi(n)\) fully

Let \(k=\mathrm{ord}_n(a)\). By Euler, \(a^{\varphi(n)}\equiv 1\), so the set \(S=\{m\ge 1:a^m\equiv 1\pmod n\}\) is nonempty. \(k=\min S\).
Write \(\varphi(n)=qk+r\), \(0\le r<k\). Then \(1\equiv a^{\varphi(n)}\equiv (a^k)^q a^r\equiv a^r\). Minimality ⇒ \(r=0\). Hence \(k\mid\varphi(n)\).

Corollary. Orders are among the divisors of \(\varphi(n)\) — search only those candidates when computing order by hand.

Additional worked examples

Example 11 — \(\varphi\) multiplicative check.
\(\varphi(36)=\varphi(4\cdot 9)=\varphi(4)\varphi(9)=2\cdot 6=12\) since \(\gcd(4,9)=1\). Direct: units mod \(36\) among \(1..35\) coprime to \(2\) and \(3\).

Example 12 — Last two digits of \(7^{100}\).
Need \(7^{100}\bmod 100\). \(\gcd(7,100)=1\), \(\varphi(100)=40\), \(100\equiv 20\pmod{40}\), so \(7^{100}\equiv 7^{20}\bmod 100\). Compute \(7^2=49\), \(7^4=2401\equiv 01\) wait \(01\)? \(2401\) yes \(\equiv 01\pmod{100}\)? \(2401-24\cdot 100=2401-2400=1\). So \(7^4\equiv 1\pmod{100}\)? Check \(7^4=2401\) yes. Then order divides \(4\), and \(7^{20}=(7^4)^5\equiv 1\). So last two digits \(01\).

Example 13 — Order of \(2\) mod \(17\).
\(2^8=256\equiv 1\pmod{17}\)? \(17\cdot 15=255\), yes \(256\equiv 1\). Is smaller? Divisors of \(8\): \(2^4=16\equiv -1\neq 1\), \(2^2=4\neq 1\). Order \(8\), and \(8\mid 16=\varphi(17)\).

Example 14 — Fermat for inverse.
\(5^{-1}\bmod 17\equiv 5^{15}\bmod 17\). Or \(5^{p-2}=5^{15}\). Easier trial: \(5\cdot 7=35\equiv 1\), inv \(7\).

Example 15 — Euler failure.
\(4^{\varphi(6)}=4^2=16\equiv 4\not\equiv 1\pmod 6\).

More exercises

  1. Compute \(2^{100}\bmod 101\) (\(101\) prime).
  2. Compute \(\varphi(720)\) using FTA.
  3. Find all orders of units mod \(9\).
  4. Prove: if \(\mathrm{ord}_n(a)=k\) then \(a^j\equiv a^i\pmod n\) iff \(k\mid(j-i)\) (for the cyclic powers).
  5. RSA literacy: why \(m^{k\varphi(n)+1}\equiv m\pmod n\) under coprimality.
  6. Reduce \(3^{1000}\bmod 14\) carefully (note \(\gcd(3,14)=1\), \(\varphi(14)=6\)).
  7. Show \(a^{n}\equiv a\pmod n\) is not always true (unlike Fermat’s \(a^p\equiv a\pmod p\)) — find composite counterexample (Carmichael numbers culture optional).

Selected mini-solutions

  1. \(5^{12}\equiv 1\pmod{13}\), \(30=2\cdot 12+6\), \(5^{30}\equiv 5^6\pmod{13}\).
  2. \(\varphi(100)=40\), \(\varphi(16)=8\), \(\varphi(15)=8\).
  3. Orders mod \(7\): \(1\) has order \(1\); \(2\) has order \(3\); \(3\) has order \(6\) (primitive root), etc.
  4. Units mod \(8\): \(1,3,5,7\) all square to \(1\); no element order \(4=\varphi(8)\); no primitive root.

Common pitfalls

Pitfall Fix
Applying Euler when \(\gcd(a,n)>1\) Check coprimality first
Reducing exponent mod \(n\) instead of mod \(\varphi(n)\) Exponents live mod \(\varphi(n)\) (when coprime)
\(\varphi(p^k)=p^k-1\) Wrong: \(p^k-p^{k-1}\)
Confusing order with discrete log Order is min \(k\) with \(a^k\equiv 1\); dlog solves \(g^x\equiv h\)
Using Fermat mod composite Need Euler or CRT
Stopping order search at \(\varphi(n)\) without checking divisors Order divides \(\varphi(n)\); check divisors

Study notes — exponent reduction at a glance

Setting Reduce exponent mod Hypothesis
Fermat \(p-1\) \(p\) prime, \(p\nmid a\)
Euler \(\varphi(n)\) \(\gcd(a,n)=1\)
Order — \(\mathrm{ord}_n(a)\mid m\) iff \(a^m\equiv 1\)

\(\varphi\) formulas: \(p-1\); \(p^{k-1}(p-1)\); multiplicative on coprime factors; \(n\prod_{p\mid n}(1-1/p)\).

Quick check: after reducing \(a^k\bmod n\), always verify a small related power by hand when \(n\) is tiny.

Synthesis — Fermat / Euler / order workout

S1. Compute \(2^{50}\bmod 13\) two ways (Fermat; successive square).

S2. Compute \(\varphi(360)\) via FTA.

S3. Reduce \(9^{100}\bmod 10\) (last digit) using Euler or cycles.

S4. Find \(\mathrm{ord}_{11}(2)\) by testing divisors of \(10\).

S5. Prove: if \(\mathrm{ord}_n(a)=k\) and \(a^m\equiv 1\pmod n\) then \(k\mid m\).

S6. Explain why \(2^{7}\equiv 2\pmod 8\) does not contradict Euler (hypotheses).

S7. Use \(a^{p-2}\equiv a^{-1}\pmod p\) to find \(6^{-1}\bmod 13\).

S8. RSA literacy paragraph: role of \(\varphi(n)\) in choosing \(d\).

Checkpoint

  • Can state Fermat (both forms) and Euler with hypotheses
  • Can compute \(\varphi(n)\) for prime powers and products
  • Can reduce large exponents correctly
  • Can obtain inverses as \(a^{\varphi(n)-1}\) when coprime
  • Can define order and prove it divides \(\varphi(n)\)
  • Exercises A–D done; synthesis attempted

Two personal takeaways:

  1. …
  2. …

Deeper theory — Fermat via binomial (optional alternate)

Alternate proof idea of \(a^p\equiv a\pmod p\) for prime \(p\).
For \(0<k<p\), \(p\mid\binom{p}{k}\). By induction on \(a\ge 0\): base \(0,1\) clear; if true for \(a\), then \[ (a+1)^p=\sum_{k=0}^p\binom{p}{k}a^k\equiv a^p+1\equiv a+1\pmod p \] using the induction hypothesis and \(p\mid\binom{p}{k}\) for middle terms. Extend to negative \(a\) by sign. This proves the “always” form \(a^p\equiv a\pmod p\); the unit form \(a^{p-1}\equiv 1\) follows when \(p\nmid a\) by cancelling one \(a\) (valid in the field \(\mathbb{Z}/p\mathbb{Z}\)).

Deeper theory — order lemma fully

Lemma. Let \(\gcd(a,n)=1\), \(k=\mathrm{ord}_n(a)\). Then \(a^j\equiv a^i\pmod n\) iff \(k\mid(j-i)\).

Proof. \(a^j\equiv a^i\) iff \(a^{j-i}\equiv 1\) (multiply by inverse of \(a^i\)). And \(a^m\equiv 1\) iff \(k\mid m\) (standard division argument from Day 75 main text).

Corollary. The powers \(a^0,a^1,\ldots,a^{k-1}\) are pairwise incongruent mod \(n\) — a cyclic subgroup of size \(k\) inside \((\mathbb{Z}/n\mathbb{Z})^\times\).

Worked example — large exponent reductions

Example 16 — \(2^{100}\bmod 13\).
\(2^{12}\equiv 1\pmod{13}\) by Fermat. \(100=8\cdot 12+4\), so \(2^{100}\equiv 2^4=16\equiv 3\pmod{13}\).
Successive square check: \(2^2=4\), \(2^4=3\), \(2^8=9\), \(2^{16}\equiv 3\), … or use binary: \(100=64+32+4\), multiply \(2^{64}2^{32}2^4\) reduced mod \(13\).

Example 17 — \(\varphi(720)\).
\(720=2^4\cdot 3^2\cdot 5\). \(\varphi(720)=720(1-1/2)(1-1/3)(1-1/5)=720\cdot\frac12\cdot\frac23\cdot\frac45=192\).

Example 18 — Order of \(2\) mod \(11\).
Divisors of \(\varphi(11)=10\): check \(2^1=2\), \(2^2=4\), \(2^5=32\equiv -1\neq 1\), \(2^{10}\equiv 1\). Order is \(10\) (primitive root mod \(11\)).

Example 19 — Reduce \(5^{100}\bmod 12\).
\(\gcd(5,12)=1\), \(\varphi(12)=4\), \(100\equiv 0\pmod 4\), so \(5^{100}\equiv (5^4)^{25}\equiv 1^{25}=1\pmod{12}\). Check: \(5^2=25\equiv 1\pmod{12}\) actually, so order divides \(2\); \(5^{100}=(5^2)^{50}\equiv 1\).

Extra exercises — exponent mastery

  1. Compute \(2^{50}\bmod 17\) by Fermat.
  2. Compute \(\varphi(84)\) via FTA.
  3. Find \(\mathrm{ord}_9(2)\) if defined; if not, explain.
  4. Prove: if \(\mathrm{ord}_n(a)=k\) and \(\ell\mid k\) then \(\mathrm{ord}_n(a^{k/\ell})=\ell\).
  5. Last two digits of \(3^{100}\): compute \(3^{100}\bmod 100\) using \(\varphi(100)=40\) (note \(100=2\cdot 40+20\), so need \(3^{20}\bmod 100\)).
  6. Show \(a^{n-1}\equiv 1\pmod n\) for all \(a\) coprime to \(n\) does not characterize primes (Carmichael culture: \(n=561\) awareness only).
  7. RSA literacy: if \(ed=1+t\varphi(n)\), show \(m^{ed}\equiv m\pmod n\) when \(\gcd(m,n)=1\).
  8. Compute \(7^{100}\bmod 13\) and \(7^{100}\bmod 11\), state the system for CRT recombination (Day 78).

Mini-solutions (selected)

  1. \(2^{16}\equiv 1\pmod{17}\), \(50=3\cdot 16+2\) ⇒ \(2^{50}\equiv 2^2=4\).
  2. \(84=2^2\cdot 3\cdot 7\), \(\varphi=84\cdot\frac12\cdot\frac23\cdot\frac67=24\).
  3. \(\gcd(2,9)=1\); \(2^1=2\), \(2^2=4\), \(2^3=8\equiv -1\), \(2^6\equiv 1\pmod 9\); order \(6\), and \(6\mid\varphi(9)=6\).

Closing synthesis card

Skill Check
Fermat both forms □
\(\varphi\) formulas □
Euler reduction of exponents □
Order divides \(\varphi(n)\) □
Avoid Euler when not coprime □

Tomorrow

Day 76 — Hashing mathematics and collisions.