Unit 4: Classical Theorems: Fermat, Euler, Wilson & Primitive Roots

1. Statement and Proof of Fermat's Little Theorem

Pierre de Fermat stated this celebrated theorem in 1640, with the first published proof provided by Leonhard Euler in 1736.

Theorem 4.1 (Fermat's Little Theorem): Let $p$ be a prime number.

1. If $a \in \mathbb{Z}$ is not divisible by $p$ ($\gcd(a, p) = 1$), then:

1. For any integer $a \in \mathbb{Z}$:

Proof: Consider the set of multiples of $a$ by the first $p - 1$ positive integers:

We make two critical observations:

1. No element is divisible by $p$: For any $1 \le k \le p - 1$, $p \nmid k$ and $p \nmid a$, so by Euclid's Lemma, $p \nmid ka$.
2. All elements are pairwise incongruent modulo $p$:

If $j a \equiv k a \pmod p$ with $1 \le j \le k \le p - 1$, then $p \mid (k - j)a$. Since $\gcd(a, p) = 1$, by Euclid's Lemma $p \mid (k - j)$. Since $0 \le k - j < p$, this forces $k - j = 0 \implies j = k$. Therefore, the residues of the elements of $S$ modulo $p$ must be a permutation of the set $\{1, 2, 3, \dots, p - 1\}$. Multiplying all $p - 1$ congruences together:

Factoring out $a$ on the left-hand side:

Since $p$ is prime, none of the integers $1, 2, \dots, p - 1$ share any common factor with $p$, so $\gcd((p - 1)!, p) = 1$. By the cancellation law (Theorem 3.3), we divide both sides by $(p - 1)!$:

2. Pseudoprimes and Carmichael Numbers

The converse of Fermat's Little Theorem is false: if $a^{n-1} \equiv 1 \pmod n$, $n$ is not necessarily prime!

Definition 4.1 (Fermat Pseudoprime): A composite integer $n$ is called a Fermat pseudoprime to base $a$ if:

Example: $341 = 11 \times 31$ is composite, but $2^{340} \equiv 1 \pmod{341}$. Thus $341$ is a pseudoprime to base $2$.

Definition 4.2 (Carmichael Number / Absolute Pseudoprime): A composite integer $n$ is called a Carmichael number if $a^{n-1} \equiv 1 \pmod n$ for all integers $a$ with $\gcd(a, n) = 1$.

Theorem 4.2 (Korselt's Criterion, 1899): A positive composite integer $n$ is a Carmichael number if and only if $n$ is square-free and for every prime divisor $p \mid n$:

The smallest Carmichael number is $561 = 3 \times 11 \times 17$ ($2 \mid 560, 10 \mid 560, 16 \mid 560$).

1. Euler's Totient Function $\phi(n)$

Leonhard Euler generalized Fermat's theorem in 1760 to arbitrary composite moduli $m$ by introducing the totient function $\phi(n)$.

Definition 4.3 (Euler's Totient Function): For $n \in \mathbb{N}$, $\phi(n)$ denotes the number of integers in $\{1, 2, \dots, n\}$ that are coprime to $n$:

Theorem 4.3 (Values of $\phi$ on Prime Powers):

1. For a prime $p$: $\phi(p) = p - 1$.
2. For a prime power $p^k$ ($k \ge 1$):

Proof: The positive integers $\le p^k$ that are NOT coprime to $p^k$ are precisely the multiples of $p$:

There are exactly $p^{k-1}$ such multiples. Subtracting these from the total $p^k$ elements:

2. Multiplicativity of Euler's Function

Theorem 4.4 (Multiplicativity of $\phi$): If $\gcd(m, n) = 1$, then:

Consequently, for any integer $n = \prod_{i=1}^r p_i^{a_i}$:

3. Euler's Totient Theorem

Theorem 4.5 (Euler's Totient Theorem, 1760): If $a, m \in \mathbb{Z}$ with $m \ge 1$ and $\gcd(a, m) = 1$, then:

Proof: Let $\{r_1, r_2, \dots, r_{\phi(m)}\}$ be a reduced residue system modulo $m$. Since $\gcd(a, m) = 1$, the set $\{a r_1, a r_2, \dots, a r_{\phi(m)}\}$ is also a reduced residue system modulo $m$ (Theorem 3.4). Therefore, their products modulo $m$ must be congruent:

Factoring out $a$:

Since each $r_i$ is coprime to $m$, their product $P = \prod r_i$ is coprime to $m$. Dividing both sides by $P$ via Theorem 3.3 yields:

1. Statement and Proof of Wilson's Theorem

John Wilson stated this property in 1770, with the first rigorous proof published by Joseph-Louis Lagrange in 1771.

Theorem 4.6 (Wilson's Theorem): An integer $p > 1$ is a prime number if and only if:

Proof ($\implies$ Forward Direction): Suppose $p$ is prime.

• For $p = 2$: $(2 - 1)! = 1! = 1 \equiv -1 \pmod 2$ (since $1 \equiv -1 \equiv 1 \pmod 2$).
• For $p = 3$: $(3 - 1)! = 2! = 2 \equiv -1 \pmod 3$.

Now assume $p \ge 5$ is an odd prime. Consider the set of integers $S = \{1, 2, 3, \dots, p - 1\}$. For each $a \in S$, $\gcd(a, p) = 1$, so by Corollary 3.1 there exists a unique modular inverse $a' \in S$ such that:

Which elements in $S$ are their own modular inverses ($a = a'$)?

By Euclid's Lemma, $p \mid (a - 1)$ or $p \mid (a + 1)$. Since $1 \le a \le p - 1$:

• $a \equiv 1 \pmod p \implies a = 1$.
• $a \equiv -1 \pmod p \implies a = p - 1$.

Thus, $1$ and $p - 1$ are the only self-inverse elements in $S$! The remaining $p - 3$ elements $\{2, 3, \dots, p - 2\}$ can be grouped into $(p - 3)/2$ disjoint pairs $\{a, a'\}$ with $a \ne a'$ such that $a a' \equiv 1 \pmod p$. Multiplying all elements of $S$:

Proof ($\impliedby$ Reverse Direction): Suppose $(n - 1)! \equiv -1 \pmod n$ for some $n > 1$. We must show that $n$ is prime. Suppose for contradiction that $n$ is composite. Then $n$ has a proper divisor $d$ such that $1 < d < n$. Since $1 < d \le n - 1$, $d$ appears as one of the factors in the product:

By assumption, $n \mid ((n - 1)! + 1)$. Since $d \mid n$, by transitivity $d \mid ((n - 1)! + 1)$. Since $d \mid (n - 1)!$ and $d \mid ((n - 1)! + 1)$, by linearity:

But $d > 1$, which is impossible! Thus, $n$ must be prime. $\blacksquare$

1. Definition of Order

By Euler's Totient Theorem, if $\gcd(a, m) = 1$, then $a^{\phi(m)} \equiv 1 \pmod m$. Therefore, the set of positive integers $k$ such that $a^k \equiv 1 \pmod m$ is non-empty. By the Well-Ordering Principle, this set contains a smallest element.

Definition 4.4 (Order of an Integer Modulo $m$): Let $a, m \in \mathbb{Z}$ with $m \ge 1$ and $\gcd(a, m) = 1$. The order of $a$ modulo $m$, denoted $\operatorname{ord}_m(a)$, is the smallest positive integer $d \in \mathbb{N}$ such that:

2. Fundamental Properties of Order

Theorem 4.7 (Division Property of Order): Let $\gcd(a, m) = 1$ and $d = \operatorname{ord}_m(a)$.

1. $a^k \equiv 1 \pmod m$ if and only if $d \mid k$.
2. In particular, $d \mid \phi(m)$.
3. $a^i \equiv a^j \pmod m$ if and only if $i \equiv j \pmod d$.
4. The powers $a^0, a^1, a^2, \dots, a^{d-1}$ are pairwise incongruent modulo $m$.

Proof: To prove Part 1: Suppose $a^k \equiv 1 \pmod m$. By the Division Algorithm, divide $k$ by $d$:

Then:

Thus $a^r \equiv 1 \pmod m$. If $r > 0$, this contradicts the minimality of $d = \operatorname{ord}_m(a)$ (since $r < d$). Therefore, $r = 0$, which proves $d \mid k$. Conversely, if $d \mid k$, then $k = d c$, so $a^k = (a^d)^c \equiv 1^c \equiv 1 \pmod m$. Part 2 follows immediately by applying Part 1 to $k = \phi(m)$. $\blacksquare$

Theorem 4.8 (Order of Powers): If $\operatorname{ord}_m(a) = d$, then for any positive integer $k \ge 1$:

In particular, $\operatorname{ord}_m(a^k) = d$ if and only if $\gcd(k, d) = 1$.

1. Primitive Roots Modulo $m$

Definition 4.5 (Primitive Root): An integer $g$ is called a primitive root modulo $m$ if:

Equivalently, $g$ is a primitive root if its powers $\{g^1, g^2, \dots, g^{\phi(m)}\}$ generate the entire reduced residue system modulo $m$ (so that the unit group $(\mathbb{Z}/m\mathbb{Z})^\times$ is cyclic).

2. Gauss's Primitive Root Characterization

Not every modulus possesses primitive roots!

Theorem 4.9 (Gauss's Moduli Theorem): A positive integer $m \ge 2$ possesses a primitive root if and only if:

where $p$ is an odd prime and $k \ge 1$. Moduli with two or more distinct odd prime factors or divisible by $8$ have non-cyclic unit groups and no primitive roots.

Theorem 4.10 (Number of Primitive Roots): If a modulus $m$ possesses a primitive root, then the total number of mutually incongruent primitive roots modulo $m$ is exactly:

3. Theory of Indices (Discrete Logarithms)

Let $g$ be a fixed primitive root modulo $m$. Every integer $a$ coprime to $m$ is congruent to exactly one power $g^k$ with $0 \le k < \phi(m)$.

Definition 4.6 (Index / Discrete Logarithm): The exponent $k \in \{0, 1, \dots, \phi(m) - 1\}$ such that $g^k \equiv a \pmod m$ is called the index (or discrete logarithm) of $a$ to base $g$ modulo $m$, written:

Theorem 4.11 (Arithmetic Properties of Indices):

1. $\operatorname{ind}_g(a b) \equiv \operatorname{ind}_g(a) + \operatorname{ind}_g(b) \pmod{\phi(m)}$
2. $\operatorname{ind}_g(a^k) \equiv k \cdot \operatorname{ind}_g(a) \pmod{\phi(m)}$
3. $\operatorname{ind}_g(1) \equiv 0 \pmod{\phi(m)}$ and $\operatorname{ind}_g(g) \equiv 1 \pmod{\phi(m)}$

Indices transform exponential congruences $x^k \equiv a \pmod m$ into simple linear congruences: