Fermat's Little Theorem

Let $(\mathbb{Z}/n\mathbb{Z}{})^*$ denote the subset of elements $[x] \in \mathbb{Z}/n\mathbb{Z}{}$ such that $\gcd(x,n)=1$ .

The set $(\mathbb{Z}/n\mathbb{Z}{})^*$ is a group, called the group of units of the ring $\mathbb{Z}/n\mathbb{Z}{}$ ; it will be of great interest to us. Each element of this group has an order, and Lagrange's theorem from group theory implies that each element of $(\mathbb{Z}/n\mathbb{Z}{})^*$ has order that divides the order of $(\mathbb{Z}/n\mathbb{Z}{})^*$ . In elementary number theory this fact goes by the monicker ``Fermat's Little Theorem'', and we reprove it from basic principles in this section.

Definition 2.1 (Order of an Element)   Let $n\in\mathbb{N}$ and $x\in\mathbb{Z}$ and suppose that $\gcd(x,n)=1$ . The order of $x$ modulo $n$ is the smallest $m\in\mathbb{N}$ such that

$$x^m \equiv 1\pmod{n}.$$

To show that the definition makes sense, we verify that such an $m$ exists. Consider $x, x^2, x^3, \ldots$ modulo $n$ . There are only finitely many residue classes modulo $n$ , so we must eventually find two integers $i, j$ with $i<j$ such that

$$x^j\equiv x^i\pmod{n}.$$

Since $\gcd(x,n)=1$ , Proposition 2.1.9 implies that we can cancel $x$ 's and conclude that

$$x^{j-i}\equiv 1\pmod{n}.$$

SAGE Example 2.1   Use x.multiplicative_order() to compute the order of an element of $\mathbb{Z}/n\mathbb{Z}$ in SAGE.

sage: R = Integers(10)
sage: a = R(3)                 # create an element of Z/10Z
sage: a.multiplicative_order()
4

Notice that the powers of $a$ are periodic with period $4$ , i.e., there are four powers and they repeat:

sage: [a^i for i in range(15)] 
[1, 3, 9, 7, 1, 3, 9, 7, 1, 3, 9, 7, 1, 3, 9]

The command range(n) we use above returns the list of integers between 0 and $n-1$ , inclusive.

Definition 2.1 (Euler's phi-function)   For $n\in\mathbb{N}$ , let

$$\varphi (n) = \char93 \{a \in \mathbb{N}: a \leq n$$    and $$\gcd(a,n)=1\}.$$

For example,

$$\varphi (1) = \char93 \{1\} = 1,$$

$$\varphi (2) = \char93 \{1\} = 1,$$

$$\varphi (5) = \char93 \{1,2,3,4\} = 4,$$

$$\varphi (12) = \char93 \{1,5,7,11\} = 4.$$

Also, if $p$ is any prime number then

$$\varphi (p) = \char93 \{1,2,\ldots,p-1\} = p-1.$$

In Section 2.2.1, we will prove that $\varphi$ is a multiplicative function. This will yield an easy way to compute $\varphi (n)$ in terms of the prime factorization of $n$ .

SAGE Example 2.1   Use the command euler_phi(n) to compute $\varphi (n)$ in SAGE:

sage: euler_phi(2007)
1332

Theorem 2.1 (Fermat's Little Theorem)   If $\gcd(x,n)=1$ , then

$$x^{\varphi (n)} \equiv 1\pmod{n}.$$

Proof. As mentioned above, Fermat's Little Theorem has the following group-theoretic interpretation. The set of units in $\mathbb{Z}/n\mathbb{Z}{}$ is a group

$$(\mathbb{Z}/n\mathbb{Z}{})^* = \{ a \in \mathbb{Z}/n\mathbb{Z}{} : \gcd(a,n) = 1\}.$$

which has order  $\varphi (n)$ . The theorem then asserts that the order of an element of $(\mathbb{Z}/n\mathbb{Z}{})^*$ divides the order $\varphi (n)$ of $(\mathbb{Z}/n\mathbb{Z}{})^*$ . This is a special case of the more general fact (Lagrange's theorem) that if $G$ is a finite group and $g\in G$ , then the order of $g$ divides the cardinality of $G$ .

We now give an elementary proof of the theorem. Let

$$P = \{ a : 1\leq a \leq n$$    and $$\gcd(a,n)=1\}.$$

In the same way that we proved Lemma 2.1.11, we see that the reductions modulo $n$ of the elements of $xP$ are the same as the reductions of the elements of $P$ . Thus

$$\prod_{a\in P} (xa) \equiv \prod_{a \in P} a \pmod{n},$$

since the products are over the same numbers modulo $n$ . Now cancel the $a$ 's on both sides to get

$$x^{\char93 P} \equiv 1\pmod{n},$$

as claimed. $\qedsymbol$

SAGE Example 2.1   We illustrate Fermat's Little Theorem using SAGE. The command Mod(x,n) returns the equivalence class of $x$ in $\mathbb{Z}/n\mathbb{Z}$ .

sage: n = 20
sage: k = euler_phi(n); k
8
sage: [Mod(x,n)^k for x in range(n) if gcd(x,n) == 1]
[1, 1, 1, 1, 1, 1, 1, 1]