Discover Fermat's Little Theorem, Euler's totient function, and the world of multiplicative functions
Fermat's Little Theorem (1640) states that if p is prime and a is not divisible by p, then ap-1 ≡ 1 (mod p). Euler generalized this using his totient function φ(n), which counts integers coprime to n.
These results belong to a broader family of multiplicative functions — functions f where f(mn) = f(m)f(n) whenever gcd(m,n) = 1. The Möbius function μ provides an elegant inversion formula that ties them all together.
For any prime p and base a not divisible by p, the powers a, a², a³, ... cycle mod p with period dividing p-1, always returning to 1 at ap-1. Try a composite number like 561 (a Carmichael number) to see how the theorem can be "fooled."
For prime p and 1 ≤ a < p: ap-1 ≡ 1 (mod p)
Fermat's little theorem guarantees ap−1 ≡ 1 (mod p) when p is prime and gcd(a, p) = 1. Carmichael numbers are composites that fool this test for many bases.
φ(n) counts how many integers from 1 to n are coprime to n. These are exactly the units in Z/nZ — the elements with multiplicative inverses. Euler's product formula expresses φ(n) in terms of n's prime factors.
Compare five fundamental arithmetic functions: the totient φ, divisor sum σ, divisor count τ, Möbius μ, and Liouville λ. Each reveals different aspects of integer structure, yet they share the key property of multiplicativity.
If g(n) = Σd|n f(d), then the Möbius inversion formula recovers f from g: f(n) = Σd|n μ(n/d) g(d). Watch the inversion perfectly reconstruct the original function, row by row.
If g(n) = Σd|n f(d), then Möbius inversion recovers: f(n) = Σd|n μ(n/d) · g(d)
Here: g(n) = d(n) (divisor count)
| n | f(n) | g(n) | Recovered f(n) | Match? |
|---|---|---|---|---|
| 1 | 1 | 1 | ? | |
| 2 | 1 | 2 | ? | |
| 3 | 1 | 2 | ? | |
| 4 | 1 | 3 | ? | |
| 5 | 1 | 2 | ? | |
| 6 | 1 | 4 | ? | |
| 7 | 1 | 2 | ? | |
| 8 | 1 | 4 | ? | |
| 9 | 1 | 3 | ? | |
| 10 | 1 | 4 | ? | |
| 11 | 1 | 2 | ? | |
| 12 | 1 | 6 | ? |
You've explored the heart of arithmetic function theory:
Next: We shift from algebraic to analytic perspectives, studying how primes are distributed among the integers and the celebrated Prime Number Theorem.