Back to the on-screen lesson ·
Why the power $p-1$ returns every residue to one, the rule for reducing exponents that follows, and why the converse is nearly but not quite true.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state both forms of Fermat's little theorem with the hypothesis each needs, prove the first by rearranging the multiples of the base, reduce an exponent modulo $p-1$ to compute a large power modulo a prime, obtain an inverse as the power $p-2$, and say why passing the Fermat primality test is evidence of primality rather than proof of it.
Lesson 6 established that congruences multiply, so $a \equiv b$ gives $a^k \equiv b^k$ for every $k$. That reduces the base of a power freely.
What it says nothing about is the exponent. $2^{13} \bmod 5$ is not $2^{3} \bmod 5$ for any reason yet given, and in fact the two happen to agree only because of the theorem this lesson proves. Reducing exponents requires knowing that some power of the base returns to $1$, and lesson 7's table of units is where that first became visible: the powers of $3$ modulo $7$ ran $3, 2, 6, 4, 5, 1$ and came home.
Fermat's little theorem is $a^{p-1} \equiv 1 \pmod p$ for prime $p$ with $p \nmid a$; the little distinguishes it from Fermat's last theorem, which is unrelated.
In a primality test, the number $a$ being raised to a power is the base, and the number being tested is the modulus.
A composite $n$ with $a^{n-1} \equiv 1 \pmod n$ for a particular base $a$ is a Fermat pseudoprime to base $a$ — it passes a test it should have failed. A composite that does this for every base coprime to it is a Carmichael number; $561 = 3 \cdot 11 \cdot 17$ is the smallest, and there are infinitely many.
Fermat's little theorem. Let $p$ be prime. If $p \nmid a$ then $$a^{p-1} \equiv 1 \pmod p.$$ For every $a$ whatever, $a^{p} \equiv a \pmod p$.
The second form follows from the first by multiplying through by $a$, and it covers the case $p \mid a$, where both sides are $0$. It is the more quotable statement and the first is the more useful one.
The proof. Consider $a \cdot 1, a \cdot 2, \ldots, a \cdot (p-1)$ modulo $p$. None is $0$, since $p$ is prime and divides neither factor. No two are equal, since $ai \equiv aj$ would force $p \mid (i-j)$ after cancelling the unit $a$. So the list is a permutation of $1, 2, \ldots, p-1$. Multiplying both lists: $$a^{p-1}(p-1)! \equiv (p-1)! \pmod p,$$ and $(p-1)!$ is a product of units, so it cancels.
What it is for: reducing exponents. Since $a^{p-1} \equiv 1$, any block of $p-1$ factors may be discarded, so $$a^{k} \equiv a^{k \bmod (p-1)} \pmod p.$$ The modulus for the exponent is $p-1$; the modulus for the value is $p$. These are different numbers and keeping them apart is most of the discipline of the subject.
A second use: inverses. $a \cdot a^{p-2} \equiv a^{p-1} \equiv 1$, so $a^{p-2}$ is an inverse of $a$ modulo $p$. One exponentiation replaces a run of the extended Euclidean algorithm.
A third: primality testing. If $a^{n-1} \not\equiv 1 \pmod n$ for some $a$ coprime to $n$, then $n$ is definitely composite — with no factor found. This is the Fermat test, and its weakness is that the converse fails: $2^{340} \equiv 1 \pmod{341}$ while $341 = 11 \cdot 31$.
Another way: steps
Another way: example
$3^{100} \bmod 7$. The modulus is prime and $7 \nmid 3$, so exponents reduce modulo $6$: $100 = 16 \cdot 6 + 4$, so $3^{100} \equiv 3^{4}$. And $3^2 = 9 \equiv 2$, so $3^4 \equiv 4$. Answer $4$ — from a hundred multiplications down to three.
Fermat's theorem says every prime passes a test. The tempting reading is that only primes pass it, and that reading is false — but it is nearly true, and the gap between nearly and exactly is where a whole subject lives.
The test. To test $n$, pick a base $a$ coprime to $n$ and compute $a^{n-1} \bmod n$. If the answer is not $1$, then $n$ is composite, and this is a proof: the theorem would have forced $1$ otherwise. Notice what has been learned and what has not — that $n$ is composite, with no factor of $n$ produced. $a$ is then called a witness to the compositeness of $n$.
The failure. If the answer is $1$, nothing is proved. $341 = 11 \cdot 31$ satisfies $2^{340} \equiv 1 \pmod{341}$, so base $2$ is fooled. Trying base $3$ exposes it: $3^{340} \not\equiv 1 \pmod{341}$. Usually a couple of extra bases settle the matter, and for most composites the great majority of bases are witnesses.
The real obstruction. A few composites have no witnesses at all among the bases coprime to them. These are the Carmichael numbers, the smallest being $561 = 3 \cdot 11 \cdot 17$. They satisfy $a^{n-1} \equiv 1$ for every $a$ coprime to $n$, so the Fermat test can never expose them however many bases are tried, and it was proved in 1994 that there are infinitely many. Korselt's criterion says exactly which numbers they are: $n$ is Carmichael when it is squarefree and $p - 1 \mid n - 1$ for every prime $p$ dividing $n$. Check $561$: it is $3 \cdot 11 \cdot 17$, and $2, 10, 16$ all divide $560$.
The repair. The Miller–Rabin test strengthens the condition by using a second fact: modulo a prime, the only square roots of $1$ are $\pm 1$. Writing $n - 1 = 2^s d$ with $d$ odd and examining the chain $a^d, a^{2d}, a^{4d}, \ldots$ catches every composite for at least three quarters of the bases, Carmichael numbers included. A composite therefore survives $k$ random bases with probability at most $4^{-k}$, and that is the test every cryptographic library actually runs.
Reducing the exponent modulo $p$. The exponent reduces modulo $p-1$. Modulo $5$: $2^{5} \equiv 2$, while reducing the exponent modulo $5$ would give $2^{0} = 1$. Two moduli are in play and they are one apart.
Using it for a composite modulus. $2^{3} = 8 \equiv 2 \pmod 4$, not $1$. Composite moduli need Euler's theorem, and the exponent there is $\varphi(n)$, which is not $n-1$.
Forgetting $p \nmid a$ for the first form. If the prime divides the base, every power is $0$ and never $1$. The second form, $a^p \equiv a$, is the one that needs no hypothesis on $a$.
Treating a pass as a proof of primality. The converse is false, and Carmichael numbers make it false for every base at once. A pass is evidence, and the number of bases tried is what turns evidence into confidence.
Expecting $p-1$ to be the first return to $1$. It is a return, not necessarily the first. Modulo $7$, $2^3 = 8 \equiv 1$ already. The first one is the order of the base, and it divides $p-1$ — which is lesson 16.
Find $7^{1000} \bmod 13$. The modulus is prime and does not divide $7$, so the exponent reduces modulo $12$.
Name the two moduli before starting.
$1000 = 83 \cdot 12 + 4$, so $7^{1000} \equiv 7^{4} \pmod{13}$.
A thousand factors down to four.
$7^2 = 49 \equiv 10$, and $7^4 \equiv 10^2 = 100 \equiv 9 \pmod{13}$. So the answer is $9$.
Square and reduce rather than multiplying up.
Is $15$ prime? Test base $2$: compute $2^{14} \bmod 15$.
The test needs one exponentiation and no trial division.
$2^4 = 16 \equiv 1 \pmod{15}$, so $2^{14} = 2^{12} \cdot 2^{2} \equiv 1 \cdot 4 = 4$.
Reduce as you go.
$4 \ne 1$, so $15$ is composite — proved, with no factor of $15$ produced by the argument. That is the characteristic shape of a Fermat-style test, and it is why such tests are fast on numbers nothing can factorise.
Compositeness without a factorisation.
$42 = 2 \cdot 3 \cdot 7$, all prime and pairwise coprime, so it is enough to prove divisibility by each.
Split the modulus into primes first.
By the second form of the theorem, $n^{7} \equiv n \pmod 7$ for every $n$, so $7 \mid (n^7 - n)$. Modulo $3$: $n^{3} \equiv n$, so $n^{7} = (n^{3})^{2} \cdot n \equiv n^{2} \cdot n = n^{3} \equiv n$. Modulo $2$: $n^{2} \equiv n$, and the same reduction applies.
The second form needs no hypothesis on $n$, which is why it suits this.
All three primes divide $n^7 - n$, and they are pairwise coprime, so their product $42$ does.
Working modulo $23$, give the first four powers of $4$.
| Least residue | |
|---|---|
| $4^{1}$ | |
| $4^{2}$ | |
| $4^{3}$ | |
| $4^{4}$ |
What is $5^{25}$ modulo $23$?
Answer:
Is this true: $a^{p-1} \equiv 1 \pmod p$ requires $p$ to be prime?
Build the proof that $2^{p-1} \equiv 1 \pmod p$ for a prime $p$ not dividing $2$.
This task has no paper form; do it on a device.
Working modulo $13$, give $5^{13}$ and $5^{12}$, both as least residues.
the power p a, the power p minus one c
Mark the inverse of $16$ modulo $17$, computed as $16^{15}$. The line runs from $0$ to $17$.
0 |——————————| 17
Mark the position with a cross, then write the value:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Working modulo $17$, give the first four powers of $9$.
| Least residue | |
|---|---|
| $9^{1}$ | |
| $9^{2}$ | |
| $9^{3}$ | |
| $9^{4}$ |
You can compute any power modulo a prime by reducing its exponent, and you can use the theorem to produce an inverse. Say in your own words which modulus the exponent reduces by and why it is not the same as the modulus of the number. Next: counting the residues the theorem applies to.
9. Your turn: show that $n^{7} - n$ is divisible by $42$ for every integer $n$, step 3