Euler's Theorem

Euler's Theorem

1. What It Is (beginner — Fermat grown up!)

Fermat needs PRIME modulus. Euler works for ANY $n$, using $φ(n)$ = count of numbers $< n$ coprime to $n$. If $gcd(a, n) = 1$:

Fermat is the special case: $φ(p) = p - 1$!

2. Totient Table (exam must-compute!)

$n$	Coprime set	$φ(n)$
prime $p$	1..p-1	$p - 1$
$p \times q$ (distinct primes)	all minus multiples	$(p-1)(q-1)$
$p²$	all minus multiples of $p$	$p² - p$

Example RSA: $p = 5$, $q = 11$ → $n = 55$, $φ(n) = 4 \times 10 = 40$!

3. Worked (exam numerical!)

3¹⁰ mod 10? gcd(3,10)=1, φ(10)=4 → 3⁴ ≡ 1 → 3¹⁰ = 3⁸×3² ≡ 1×9 ≡ 9 mod 10!
verify: 3²=9, 3⁴=81≡1 ✓

4. Why Crypto Cares

• RSA correctness: encryption exponent $e$ + decryption $d$ with $e \times d$ mod $φ(n) = 1$ → $m^{ed}$ mod $n = m$ (Euler guarantees round-trip!).
• Exponent reduction mod $φ(n)$ (fast big powers!).

5. Exam Points

• State + $φ(pq)$ + verify ($3⁴$ mod $10$) — 5-7 marks, very frequent.
• Fermat as special case — 3 marks, favourite link.
• RSA $φ(n)$ computation — 3 marks, frequent.