For a prime p and any integer a, Fermat's little theorem says ap≡a(modp)
Lesson 1 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
state Fermat's little theorem in both forms and prove it;
find the remainder of a huge power modulo a prime;
use ap−2 as an inverse, and know what the theorem does not say about composite numbers.
A pattern in a table
Work out a6 modulo 7 for a=1,2,…,6. You get 1,64,729,…, and every one of them leaves remainder 1. Try a10 modulo 11: again all 1. Try a11 modulo 12: the remainders are all over the place.
Pierre de Fermat noticed this in 1640. The pattern holds for every prime.
The theorem
Fermat's little theorem. Let p be a prime.
For every integer a: ap≡a(modp).
If p∤a: ap−1≡1(modp).
The first form follows from the second by multiplying by a. When p∣a, both sides of the first form are 0.
The proof
Take p∤a and look at the p−1 numbers
a,2a,3a,…,(p−1)a.
None is 0 modulo p. A prime dividing ka divides k or a, and it divides neither.
No two are equal modulo p. If ia≡ja, we may cancel a, since gcd(a,p)=1. So i≡j.
So they are 1,2,…,p−1 in some order. There are p−1 different non-zero remainders, and only p−1 exist.
Multiply them all.a⋅2a⋯(p−1)a≡1⋅2⋯(p−1), that is ap−1(p−1)!≡(p−1)!.
Cancel (p−1)!. It is coprime to p, so ap−1≡1(modp).
The simulation below shows step 3: the dots are a shuffle of the heights 1 to p−1.
Two rows of the numbers 1 to 6. The top row is 1, 2, 3, 4, 5, 6. Arrows lead from each number k down to the remainder of 3k on division by 7, in the bottom row: 1 goes to 3, 2 to 6, 3 to 2, 4 to 5, 5 to 1 and 6 to 4. Every number of the bottom row is hit exactly once. A note says that the product of the top row equals the product of the bottom row modulo 7, so 3 to the power 6 is congruent to 1 modulo 7.
Using the theorem
Cut the exponent. Find 52026 modulo 13. Here 512≡1, and 2026=12×168+10, so 52026≡510. Now 52=25≡−1, so 510=(52)5≡−1≡12.
Inverses. Since a⋅ap−2=ap−1≡1, the inverse of a modulo p is ap−2. For example the inverse of 3 modulo 11 is 39≡4, and indeed 3×4=12≡1.
Divisibility. For every integer n, n13−n is a multiple of 13, and n7−n is a multiple of 7. You do not need to try any case.
Several primes at once. To show n13−n is also a multiple of 7, note n13=n⋅(n6)2≡n when 7∤n, and both sides are 0 when 7∣n.
What the theorem does not say
The converse is false. A number n with 2n−1≡1(modn) need not be prime. The smallest such composite is 341=11×31. Such numbers are called pseudoprimes to base 2.
Worse, some composites pass the test for every base coprime to them. The smallest of these Carmichael numbers is 561=3×11×17. So a computer's quick primality test uses Fermat's theorem only as a first sieve.
Practise with new numbers
Try it in Python
The program shows the shuffle, the column of ones, the failure for the composite 12 and the cut exponent.
Common mistakes
Reducing the exponent modulo p. The exponent goes modulo p−1, the base goes modulo p.
Forgetting the condition p∤a.76≡0(mod7), not 1.
Using the theorem for a composite modulus.an−1≡1(modn) can fail for composite n, as 12 shows. Euler's theorem, in the next lesson, is the right tool.
Believing the converse. A pseudoprime passes the test but is composite.
Remember these
ap≡a(modp) for every a; ap−1≡1 when p∤a.
Proof: a,2a,…,(p−1)a is a shuffle of 1,…,p−1.
Reduce exponents modulo p−1.
ap−2 is the inverse of a modulo p.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Find the remainder of 250 on division by 7.
Find the remainder of 6100 on division by 11.
Use Fermat to find the inverse of 2 modulo 13.
Show that n5−n is a multiple of 5 for every integer n, in one line.
A student says that 314≡1(mod15) by Fermat. What is wrong?
References
David M. Burton, Elementary Number Theory, Chapter 5, Fermat's Theorem.
Enroll free in The Theorems of Fermat, Euler and Wilson
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.