Discover Fermat's Little Theorem, Euler's totient function, and the world of multiplicative functions
Raise any number to a high enough power mod a prime and it comes back to 1. Follow that fact from Fermat to Euler to a whole family of number-counting functions.
Choose a prime p and a base a, and watch the powers of a cycle back to 1 at ap-1. Then try 561 to see a composite fool the test.
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.
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."
Slide n and see which numbers from 1 to n share no factor with it. φ(n) counts them.
φ(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.
Toggle the five functions φ, σ, τ, μ, and λ and compare their plots. Primes and prime powers stand out in each.
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.
Pick a function f, sum it over divisors to get g, then watch Möbius inversion rebuild f from g 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 | ? |
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.
Spot a mistake or have an idea?