Fermats Little Theorem and Eulers Theorem

Powers in Modular Arithmetic#

In the last topic we dealt with linear congruences like $ax \equiv c \pmod n$. The natural next step is congruences involving higher powers of $x$, such as $x^2 \equiv c \pmod n$; but before we can say anything about those, we need to understand how powers behave in $\mathbb{Z}_n$ in the first place.

Consider the powers of every element of $\mathbb{Z}_7$:

Notice how much structure is hiding in here:

• In every row except $0^k$, a $1$ eventually appears.
• Column $6$ is (almost) all $1$'s, and column $7$ is identical to column $1$; raising to the power $7$ does nothing in $\mathbb{Z}_7$.
• The first $1$ in each row appears in column $1, 2, 3$ or $6$; always a divisor of $6$.
• The cycle of entries in row $x^k$ is the reverse of the cycle in row $(x^{-1})^k$.
• Going down the rows, the entries of column $2$ cycle with length $3$, and the entries of column $3$ cycle with length $2$.

Running the same experiment in $\mathbb{Z}_{11}$ tells the same story: column $10$ is (almost) all $1$'s, column $11$ repeats column $1$, and the first $1$ of each row lands in column $1, 2, 5$ or $10$ — again, always a divisor of $10$.

So in $\mathbb{Z}_p$ it looks like $a^{p-1} = 1$ for every $a \neq 0$, and $a^p = a$ for absolutely every $a$. This is not a coincidence.

Fermat's Little Theorem#

Basically, modulo a prime, raising to the power $p$ is invisible, and every residue that is not a multiple of $p$ resets to $1$ after exactly $p-1$ steps; this is precisely the "column $6$ is all $1$'s, column $7$ copies column $1$" pattern from the tables. For $p \nmid a$ the two forms are equivalent (multiply the second by $a$ to get the first), but they are not interchangeable in general. The second form requires $p \nmid a$; if $p \mid a$ then $a \equiv 0 \pmod p$ and no power of it will ever be $1$.

Proof.
If $p \mid a$, then $a \equiv 0 \pmod p$, so $a^p \equiv 0 \equiv a \pmod p$ and the first form holds trivially.
So suppose that $p \nmid a$, and consider the $p-1$ numbers

$$a, \; 2a, \; 3a, \; \dots, \; (p-1)a \pmod p.$$

None of these is $0$ modulo $p$; if $p \mid ia$ then, since $p$ is prime, $p \mid i$ or $p \mid a$, and both are impossible for $1 \leq i \leq p-1$. They are also pairwise distinct modulo $p$; if $ia \equiv ja \pmod p$ then $p \mid (i-j)a$, and since $p \nmid a$ we must have $p \mid i-j$, which forces $i = j$ as $|i-j| \leq p-2 < p$.

So the list above is just $1, 2, \dots, p-1$ rearranged. Multiplying everything together,

$$\begin{align*} a \cdot 2a \cdot 3a \cdots (p-1)a &\equiv 1 \cdot 2 \cdot 3 \cdots (p-1) \pmod p, \\ a^{p-1} \, (p-1)! &\equiv (p-1)! \pmod p. \end{align*}$$

Since $p$ is prime, it divides none of $1, 2, \dots, p-1$, so $\gcd((p-1)!, p) = 1$ and $(p-1)!$ is a unit modulo $p$; cancelling it from both sides gives

$$a^{p-1} \equiv 1 \pmod p. \qquad \blacksquare$$

To see the rearrangement step in action, take $p = 7$ and $a = 3$;

$$\{3, \; 6, \; 9, \; 12, \; 15, \; 18\} \equiv \{3, \; 6, \; 2, \; 5, \; 1, \; 4\} \pmod 7,$$

which really is $\{1,2,3,4,5,6\}$ shuffled.

Example. Find $50^{97} \bmod 97$.
Here $97$ is prime, so the first form of Fermat's Little Theorem applies to every integer with no coprimality check needed;

$$\begin{align*} 50^{97} &\equiv 50 \pmod{97}. \end{align*}$$

Therefore, $50^{97} \bmod 97 = 50$; the exponent matching the modulus means we get the answer for free.

Example. Find $99^{100} \bmod 101$, and hence find $99^{909} \bmod 101$.
Since $101$ is prime and $101 \nmid 99$, the second form gives

$$99^{100} \equiv 1 \pmod{101},$$

so $99^{100} \bmod 101 = 1$. For the second power, we peel off as many blocks of $100$ from the exponent as possible; each block collapses to $1$. Writing $909 = 9 \cdot 100 + 9$ and noticing that $99 \equiv -2 \pmod{101}$,

$$\begin{align*} 99^{909} &= \left(99^{100}\right)^{9} \cdot 99^{9} \\ &\equiv 1^{9} \cdot 99^{9} \pmod{101} \\ &\equiv (-2)^{9} \pmod{101} \\ &\equiv -512 \pmod{101} \\ &\equiv -512 + 6 \cdot 101 \pmod{101} \\ &\equiv 94 \pmod{101}. \end{align*}$$

Therefore, $99^{909} \bmod 101 = 94$. Notice how switching $99$ for $-2$ turned an impossible-looking power into something you can do by hand.

Reducing Exponents Modulo a Prime#

The "peel off blocks of $p-1$" trick from the last example is worth stating as a theorem in its own right.

Proof. By the division theorem, write $k = q(p-1) + r$ where $r = k \bmod (p-1)$, so $0 \leq r < p - 1$. Then

$$\begin{align*} a^{k} &= a^{q(p-1) + r} \\ &= \left(a^{p-1}\right)^{q} \cdot a^{r} \\ &\equiv 1^{q} \cdot a^{r} \pmod p, \text{ (by Fermat's Little Theorem, as } p \nmid a\text{)} \\ &\equiv a^{r} \pmod p. \qquad \blacksquare \end{align*}$$

Basically, when working modulo a prime $p$, the bases live in $\mathbb{Z}_p$ but the exponents live in $\mathbb{Z}_{p-1}$. It is important to remember that exponents get reduced modulo $p-1$, not modulo $p$; reducing an exponent mod $p$ is the classic exam mistake.

$$\boxed{p \nmid a \implies a^k \equiv a^{k \bmod (p-1)} \pmod p.}$$

Example. Find $3^{1000} \bmod 7$.
Here $7$ is prime and $7 \nmid 3$, so exponents can be reduced modulo $7 - 1 = 6$;

$$\begin{align*} 1000 &= 6 \cdot 166 + 4, \\ 3^{1000} &\equiv 3^{4} \pmod 7 \\ &\equiv 81 \pmod 7 \\ &\equiv 81 - 77 \pmod 7 \\ &\equiv 4 \pmod 7. \end{align*}$$

Therefore, $3^{1000} \bmod 7 = 4$.

Powers in Non-Prime Moduli#

Fermat's Little Theorem is strictly about prime moduli. To see what breaks otherwise, here is the power table for $\mathbb{Z}_9$:

We can observe some familiar patterns, and one new pathology:

• A $1$ eventually appears in every row except $0^k$, $3^k$ and $6^k$.
• Column $6$ is mostly $1$'s, and column $7$ is similar to column $1$.
• The first $1$ in each row appears in column $1, 2, 3$ or $6$.
• The rows for $3$ and $6$ collapse to $0$ and never recover.

The rows that die are exactly the elements sharing a factor with $9$; indeed $3^2 = 9 \equiv 0$, and once you hit $0$ you stay there. The rows that do return to $1$ are exactly the units of $\mathbb{Z}_9$, and there are $6$ of them — which explains why column $6$ plays the role that column $p - 1$ played in the prime tables. What we need is a function that counts these "good" elements for an arbitrary modulus.

Euler's Totient Function#

Recall from Modular Rings and Units that $a \in \mathbb{Z}_n^* \iff \gcd(a,n) = 1$; so $\phi(n)$ is exactly the number of units in $\mathbb{Z}_n$,

$$\boxed{\phi(n) = |\mathbb{Z}_n^*|.}$$

Basically, $\phi(n)$ counts how many residues mod $n$ you are allowed to divide by; equivalently, how many rows of the power table will eventually return to $1$.

Example. Find the following values.

• $\phi(7) = 6$; since $7$ is prime, all of $1, 2, 3, 4, 5, 6$ are coprime with it.
• $\phi(9) = 6$; we only delete the multiples of $3$, leaving $\{1,2,4,5,7,8\}$ — matching the six "surviving" rows in the $\mathbb{Z}_9$ table above.
• $\phi(12) = 4$; the survivors are $\{1, 5, 7, 11\}$.
• $\phi(15) = 8$; the survivors are $\{1, 2, 4, 7, 8, 11, 13, 14\}$.
• For any prime number $p$, we have $\phi(p) = p - 1$; every one of $1, 2, \dots, p-1$ is coprime with $p$.

Notice that the $p - 1$ in Fermat's Little Theorem was really $\phi(p)$ in disguise; this is the observation that Euler generalised.

Totients of Prime Powers#

Computing $\phi(n)$ straight from the definition means checking a gcd for every single $a \leq n$, which is hopeless for large $n$. The following two results reduce the whole computation to knowing the prime factorisation of $n$.

Proof. The only prime factor of $p^k$ is $p$, so $\gcd(a, p^k) > 1$ if and only if $p \mid a$. Hence we take all $p^k$ integers in $1, 2, \dots, p^k$ and delete the multiples of $p$, which are

$$p, \; 2p, \; 3p, \; \dots, \; p^{k-1} \cdot p;$$

there are exactly $p^{k-1}$ of them. Everything remaining is coprime with $p^k$, so $\phi(p^k) = p^k - p^{k-1}$. $\blacksquare$

Basically, exactly $1$ in every $p$ consecutive integers is a multiple of $p$, so a prime power keeps a $\left(1 - \frac{1}{p}\right)$ share of its residues as units.

Example. Find $\phi(8)$ and $\phi(125)$.

$$\begin{align*} \phi(8) = \phi(2^3) &= 2^3 - 2^2 \\ &= 8 - 4 \\ &= 4, \\ \phi(125) = \phi(5^3) &= 5^3 - 5^2 \\ &= 125 - 25 \\ &= 100. \end{align*}$$

As a sanity check for the first one, the odd residues $\{1, 3, 5, 7\}$ are precisely the units of $\mathbb{Z}_8$; there are indeed $4$ of them. Therefore, $\phi(8) = 4$ and $\phi(125) = 100$.

The Totient is Multiplicative#

Proof. First, notice that $\gcd(a, mn) = 1$ if and only if $\gcd(a,m) = 1$ and $\gcd(a,n) = 1$; any prime dividing both $a$ and $mn$ must divide $m$ or $n$, and conversely any common prime factor of $a$ and $m$ (or $n$) also divides $mn$.

Now write the integers $1, 2, \dots, mn$ in a grid with $m$ columns, so that column $c$ contains

$$c, \; m + c, \; 2m + c, \; \dots, \; (n-1)m + c.$$

Every entry of column $c$ is congruent to $c$ modulo $m$; so the columns containing numbers coprime with $m$ are exactly the columns with $\gcd(c, m) = 1$, and there are $\phi(m)$ of these.

Fix one such column and reduce its $n$ entries modulo $n$. They are pairwise distinct; if $im + c \equiv jm + c \pmod n$ then $n \mid (i - j)m$, and since $\gcd(m,n) = 1$ we get $n \mid i - j$, forcing $i = j$ as $|i-j| < n$. So the $n$ entries of the column hit every residue modulo $n$ exactly once, and hence exactly $\phi(n)$ of them are coprime with $n$.

Counting: $\phi(m)$ good columns, each contributing $\phi(n)$ entries coprime with both $m$ and $n$; i.e. coprime with $mn$. Therefore $\phi(mn) = \phi(m)\phi(n)$. $\blacksquare$

To see this concretely with $m = 3$ and $n = 4$, lay out $1$ to $12$:

Column $3$ is dead (everything shares the factor $3$), while columns $1$ and $2$ each contain every residue mod $4$ once, hence $\phi(4) = 2$ units each. That gives $\phi(3)\phi(4) = 2 \cdot 2 = 4$ units in total, and indeed $\mathbb{Z}_{12}^* = \{1, 5, 7, 11\}$.

It is important to note that $\phi$ is only multiplicative when $\gcd(m,n) = 1$; for instance $\phi(4) = 2$ but $\phi(2)\phi(2) = 1 \cdot 1 = 1$. Always split $n$ into coprime pieces (i.e. into distinct prime powers), never arbitrary factors.

Example. Find $\phi(360)$.
Factorising and splitting into pairwise coprime prime powers,

$$\begin{align*} 360 &= 2^3 \cdot 3^2 \cdot 5, \\ \phi(360) &= \phi(2^3) \, \phi(3^2) \, \phi(5) \\ &= (2^3 - 2^2)(3^2 - 3)(5 - 1) \\ &= 4 \cdot 6 \cdot 4 \\ &= 96. \end{align*}$$

Therefore, $\phi(360) = 96$; there are $96$ units in $\mathbb{Z}_{360}$.

Combining the two theorems gives a one-line formula:

Basically, each distinct prime factor independently deletes its own $\frac{1}{p}$ share of the residues. Notice that the exponents in the factorisation never appear in the product; only which primes divide $n$ matters, with the exponents hiding inside the leading factor of $n$.

Example. Find $\phi(1000)$.

$$\begin{align*} 1000 &= 2^3 \cdot 5^3, \\ \phi(1000) &= 1000 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) \\ &= 1000 \cdot \frac{1}{2} \cdot \frac{4}{5} \\ &= 400. \end{align*}$$

Therefore, $\phi(1000) = 400$.

Euler's Theorem#

We can now generalise Fermat's Little Theorem to any modulus, with $\phi(n)$ stepping into the role of $p - 1$.

Setting $n = p$ prime recovers Fermat's Little Theorem exactly, since $\phi(p) = p - 1$ and $\gcd(a, p) = 1$ is the same condition as $p \nmid a$. Basically, the units of $\mathbb{Z}_n$ all return to $1$ after $\phi(n)$ steps — which is why column $6$ worked in the $\mathbb{Z}_9$ table ($\phi(9) = 6$) even though $9$ is not prime. Unlike Fermat's Little Theorem, there is no "first form" here: if $\gcd(a,n) \neq 1$ then Euler's Theorem says nothing at all about $a$.

The proof is the same permutation trick as before, but run over the units instead of over all nonzero residues.

Proof. Let $r_1, r_2, \dots, r_{\phi(n)}$ be the elements of $\mathbb{Z}_n^*$; by definition of $\phi$ there are exactly $\phi(n)$ of them. Since $\gcd(a,n) = 1$, $a$ is itself a unit, and products of units are units, so each $ar_i \in \mathbb{Z}_n^*$. Moreover the $ar_i$ are pairwise distinct in $\mathbb{Z}_n$; if $ar_i \equiv ar_j \pmod n$, multiplying both sides by $a^{-1}$ (which exists as $a$ is a unit) gives $r_i \equiv r_j$, so $i = j$. Hence $ar_1, ar_2, \dots, ar_{\phi(n)}$ is just $r_1, r_2, \dots, r_{\phi(n)}$ rearranged. Multiplying everything together,

$$\begin{align*} (ar_1)(ar_2) \cdots (ar_{\phi(n)}) &\equiv r_1 r_2 \cdots r_{\phi(n)} \pmod n, \\ a^{\phi(n)} \, R &\equiv R \pmod n, \text{ (where } R = r_1 r_2 \cdots r_{\phi(n)}\text{)}. \end{align*}$$

Since $R$ is a product of units, it is itself a unit; multiplying both sides by $R^{-1}$ gives

$$a^{\phi(n)} \equiv 1 \pmod n. \qquad \blacksquare$$

For a concrete instance of the shuffle, take $n = 15$ and $a = 7$; the units of $\mathbb{Z}_{15}$ are $\{1, 2, 4, 7, 8, 11, 13, 14\}$, and multiplying each by $7$ gives

$$\{7, \; 14, \; 13, \; 4, \; 11, \; 2, \; 1, \; 8\} \pmod{15},$$

the same set shuffled.

Example. Find $7^{89} \bmod 15$.
First, $\gcd(7, 15) = 1$, so Euler's Theorem applies, and

$$\phi(15) = \phi(3)\phi(5) = 2 \cdot 4 = 8,$$

so $7^8 \equiv 1 \pmod{15}$. Reducing the exponent,

$$\begin{align*} 89 &= 8 \cdot 11 + 1, \\ 7^{89} &= \left(7^{8}\right)^{11} \cdot 7^{1} \\ &\equiv 1^{11} \cdot 7 \pmod{15} \\ &\equiv 7 \pmod{15}. \end{align*}$$

Therefore, $7^{89} \bmod 15 = 7$.

Example. Find $5^{44} \bmod 18$ and $5^{77} \bmod 18$.
Here $\gcd(5, 18) = 1$ and

$$\phi(18) = \phi(2)\phi(9) = 1 \cdot 6 = 6,$$

so $5^6 \equiv 1 \pmod{18}$ and exponents can be reduced modulo $6$. For the first power, $44 = 6 \cdot 7 + 2$, so

$$\begin{align*} 5^{44} &\equiv 5^{2} \pmod{18} \\ &\equiv 25 \pmod{18} \\ &\equiv 7 \pmod{18}. \end{align*}$$

For the second, $77 = 6 \cdot 12 + 5$, so $5^{77} \equiv 5^5 \pmod{18}$. Rather than grinding out $5^5 = 3125$, notice that $5^3 = 125 = 126 - 1 \equiv -1 \pmod{18}$;

$$\begin{align*} 5^{77} &\equiv 5^{5} \pmod{18} \\ &\equiv 5^{3} \cdot 5^{2} \pmod{18} \\ &\equiv (-1) \cdot 7 \pmod{18} \\ &\equiv -7 \pmod{18} \\ &\equiv 11 \pmod{18}. \end{align*}$$

Therefore, $5^{44} \bmod 18 = 7$ and $5^{77} \bmod 18 = 11$. Spotting a power congruent to $-1$ is one of the best shortcuts available; it halves the effective cycle length.

Example. Find $2^{100} \bmod 12$.
The tempting move is: $\phi(12) = 4$ and $100 \equiv 0 \pmod 4$, "so" $2^{100} \equiv 2^0 = 1 \pmod{12}$. This is wrong; $\gcd(2, 12) = 2 \neq 1$, so Euler's Theorem does not apply and you are not allowed to reduce the exponent. Indeed every positive power of $2$ is even, so none of them can possibly be congruent to $1$ modulo $12$.

The correct approach is to split $12$ into coprime pieces, $12 = 4 \cdot 3$, and study each separately;

$$\begin{align*} 2^{100} &\equiv 0 \pmod 4, \text{ (since } 4 = 2^2 \mid 2^{100}\text{)}, \\ 2^{100} &\equiv (-1)^{100} \pmod 3 \\ &\equiv 1 \pmod 3. \end{align*}$$

Now we need the unique $x$ with $0 \leq x < 12$ satisfying $x \equiv 0 \pmod 4$ and $x \equiv 1 \pmod 3$; checking the candidates $0, 4, 8$, only $x = 4$ works. Therefore, $2^{100} \bmod 12 = 4$. Notice that Euler was still useful on the coprime piece (as $\gcd(2,3)=1$); the trick is to quarantine the shared factor first.

Finding Inverses with Euler's Theorem#

Euler's Theorem also hands us a formula for inverses. Since

$$a \cdot a^{\phi(n) - 1} = a^{\phi(n)} \equiv 1 \pmod n,$$

we immediately get

$$\boxed{\gcd(a,n) = 1 \implies a^{-1} \equiv a^{\phi(n)-1} \pmod n.}$$

This is an alternative to the extended Euclidean algorithm from Bezouts Identity and the Extended Euclidean Algorithm; it is usually slower by hand, but it is a one-line formula, which makes it useful in proofs (and in RSA-style computations later).

Example. Use Euler's Theorem to find $7^{-1}$ in $\mathbb{Z}_{30}$.
We have $\gcd(7, 30) = 1$ and

$$\phi(30) = \phi(2)\phi(3)\phi(5) = 1 \cdot 2 \cdot 4 = 8,$$

so $7^{-1} \equiv 7^{7} \pmod{30}$. Computing by squaring,

$$\begin{align*} 7^{2} &= 49 \equiv 19 \pmod{30}, \\ 7^{4} &\equiv 19^{2} \pmod{30} \\ &\equiv 361 \pmod{30} \\ &\equiv 1 \pmod{30}, \\ 7^{7} &= 7^{4} \cdot 7^{2} \cdot 7 \\ &\equiv 1 \cdot 19 \cdot 7 \pmod{30} \\ &\equiv 133 \pmod{30} \\ &\equiv 13 \pmod{30}. \end{align*}$$

Check: $7 \cdot 13 = 91 = 3 \cdot 30 + 1 \equiv 1 \pmod{30}$. Therefore, $7^{-1} = 13$ in $\mathbb{Z}_{30}$.

Reducing Exponents in General#

Just as with primes, the real day-to-day use of Euler's Theorem is collapsing huge exponents.

Proof. By the division theorem, write $k = q\,\phi(n) + r$ where $r = k \bmod \phi(n)$, so $0 \leq r < \phi(n)$. Then