Euler's totient function counts how many integers below n are coprime to n. Fermat's little theorem and Euler's generalization connect this count to modular exponentiation: a^phi(n) ≡ 1 (mod n) whenever gcd(a, n) = 1.
Euler's totient function
phi(n) counts the integers from 1 to n that are coprime to n (share no common factor with n other than 1). For a prime p, phi(p) = p - 1. For a prime power, phi(p^k) = p^k - p^(k-1). For coprime m, n: phi(m n) = phi(m) phi(n).
Scheme
; Euler's totient function
(define (gcd a b) (if (= b 0) a (gcd b (modulo a b))))
(define (totient n)
(let loop ((i 1) (count 0))
(if (> i n)
count
(loop (+ i 1)
(if (= 1 (gcd i n)) (+ count 1) count)))))
(display "phi(12) = ") (display (totient 12)) (newline) ; 4
(display "phi(7) = ") (display (totient 7)) (newline) ; 6 (prime)
(display "phi(10) = ") (display (totient 10)) (newline) ; 4
(display "phi(1) = ") (display (totient 1)) (newline) ; 1; List the coprime residues mod 12
(display "Coprime to 12: ")
(let loop ((i 1))
(when (<= i 12)
(when (= 1 (gcd i 12))
(display i) (display " "))
(loop (+ i 1))))
Fermat's little theorem
Fermat's little theorem: if p is prime and gcd(a, p) = 1, then a^(p-1) ≡ 1 (mod p). Equivalently, a^p ≡ a (mod p) for all a. This is a special case of Euler's theorem.
Scheme
; Fast modular exponentiation (repeated squaring)
(define (mod-pow base exp mod)
(cond ((= exp 0) 1)
((even? exp)
(let ((half (mod-pow base (quotient exp 2) mod)))
(modulo (* half half) mod)))
(else
(modulo (* base (mod-pow base (- exp 1) mod)) mod))))
; Fermat's little theorem: a^(p-1) = 1 (mod p)
(display "2^6 mod 7 = ") (display (mod-pow 267)) (newline) ; 1
(display "3^12 mod 13 = ") (display (mod-pow 31213)) (newline) ; 1
(display "5^10 mod 11 = ") (display (mod-pow 51011)) (newline) ; 1; Euler's theorem: a^phi(n) = 1 (mod n) when gcd(a,n)=1
(display "7^4 mod 12 = ") (display (mod-pow 7412)) ; phi(12)=4, so 1
Python
# Fast modular exponentiationdef mod_pow(base, exp, mod):
result = 1
base = base % mod
while exp > 0:
if exp % 2 == 1:
result = (result * base) % mod
exp //= 2
base = (base * base) % mod
return result
# Fermat: a^(p-1) = 1 mod pprint(f"2^6 mod 7 = {mod_pow(2, 6, 7)}")
print(f"3^12 mod 13 = {mod_pow(3, 12, 13)}")
print(f"5^10 mod 11 = {mod_pow(5, 10, 11)}")
print(f"7^4 mod 12 = {mod_pow(7, 4, 12)}")
Neighbors
→ Cryptography Ch.6 — RSA correctness relies on Euler's theorem: decryption works because m^(ed) ≡ m (mod n)
Fermat's little theorem: if p is prime and gcd(a, p) = 1, then a^(p-1) ≡ 1 (mod p). Equivalently, a^p ≡ a (mod p) for all a. This is a special case of Euler's theorem.