HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
The Theorems of Fermat, Euler and Wilson
  1. 1Fermat's little theorem
  2. 2Euler's totient function and theorem
  3. 3Wilson's theorem and the order of a number
  1. Mathematics
  2. /The Theorems of Fermat, Euler and Wilson
  3. /Fermat's little theorem

Course 28.2·Lesson 1 of 3

Fermat's little theorem

For a prime ppp and any integer aaa, Fermat's little theorem says ap≡a(modp)a^p \equiv a \pmod pap≡a(modp)

Lesson 1 of 3Show all lessonsHide
The Theorems of Fermat, Euler and Wilson
  1. 1Fermat's little theorem
  2. 2Euler's totient function and theorem
  3. 3Wilson's theorem and the order of a number

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−2a^{p-2}ap−2 as an inverse, and know what the theorem does not say about composite numbers.

A pattern in a table

Work out a6a^6a6 modulo 777 for a=1,2,…,6a = 1, 2, \dots, 6a=1,2,…,6. You get 1,64,729,…1, 64, 729, \dots1,64,729,…, and every one of them leaves remainder 111. Try a10a^{10}a10 modulo 111111: again all 111. Try a11a^{11}a11 modulo 121212: 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 ppp be a prime.

  • For every integer aaa: ap≡a(modp)\quad a^p \equiv a \pmod pap≡a(modp).
  • If p∤ap \nmid ap∤a: ap−1≡1(modp)\quad a^{p-1} \equiv 1 \pmod pap−1≡1(modp).

The first form follows from the second by multiplying by aaa. When p∣ap \mid ap∣a, both sides of the first form are 000.

The proof

Take p∤ap \nmid ap∤a and look at the p−1p - 1p−1 numbers

a, 2a, 3a, …, (p−1)a.\displaystyle a,\ 2a,\ 3a,\ \dots,\ (p - 1)a.a, 2a, 3a, …, (p−1)a.
  1. None is 000 modulo ppp. A prime dividing kakaka divides kkk or aaa, and it divides neither.
  2. No two are equal modulo ppp. If ia≡jaia \equiv jaia≡ja, we may cancel aaa, since gcd⁡(a,p)=1\gcd(a, p) = 1gcd(a,p)=1. So i≡ji \equiv ji≡j.
  3. So they are 1,2,…,p−11, 2, \dots, p - 11,2,…,p−1 in some order. There are p−1p - 1p−1 different non-zero remainders, and only p−1p - 1p−1 exist.
  4. Multiply them all. a⋅2a⋯(p−1)a≡1⋅2⋯(p−1)a \cdot 2a \cdots (p - 1)a \equiv 1 \cdot 2 \cdots (p - 1)a⋅2a⋯(p−1)a≡1⋅2⋯(p−1), that is ap−1(p−1)!≡(p−1)!a^{p-1}(p - 1)! \equiv (p - 1)!ap−1(p−1)!≡(p−1)!.
  5. Cancel (p−1)!(p - 1)!(p−1)!. It is coprime to ppp, so ap−1≡1(modp)a^{p-1} \equiv 1 \pmod pap−1≡1(modp).

The simulation below shows step 3: the dots are a shuffle of the heights 111 to p−1p - 1p−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 520265^{2026}52026 modulo 131313. Here 512≡15^{12} \equiv 1512≡1, and 2026=12×168+102026 = 12 \times 168 + 102026=12×168+10, so 52026≡5105^{2026} \equiv 5^{10}52026≡510. Now 52=25≡−15^2 = 25 \equiv -152=25≡−1, so 510=(52)5≡−1≡125^{10} = (5^2)^5 \equiv -1 \equiv 12510=(52)5≡−1≡12.

Inverses. Since a⋅ap−2=ap−1≡1a \cdot a^{p-2} = a^{p-1} \equiv 1a⋅ap−2=ap−1≡1, the inverse of aaa modulo ppp is ap−2a^{p-2}ap−2. For example the inverse of 333 modulo 111111 is 39≡43^9 \equiv 439≡4, and indeed 3×4=12≡13 \times 4 = 12 \equiv 13×4=12≡1.

Divisibility. For every integer nnn, n13−nn^{13} - nn13−n is a multiple of 131313, and n7−nn^7 - nn7−n is a multiple of 777. You do not need to try any case.

Several primes at once. To show n13−nn^{13} - nn13−n is also a multiple of 777, note n13=n⋅(n6)2≡nn^{13} = n \cdot (n^6)^2 \equiv nn13=n⋅(n6)2≡n when 7∤n7 \nmid n7∤n, and both sides are 000 when 7∣n7 \mid n7∣n.

What the theorem does not say

The converse is false. A number nnn with 2n−1≡1(modn)2^{n-1} \equiv 1 \pmod n2n−1≡1(modn) need not be prime. The smallest such composite is 341=11×31341 = 11 \times 31341=11×31. Such numbers are called pseudoprimes to base 222.

Worse, some composites pass the test for every base coprime to them. The smallest of these Carmichael numbers is 561=3×11×17561 = 3 \times 11 \times 17561=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 121212 and the cut exponent.

Read it first. Then run it. Which line shows that 121212 is not prime?

1. Change p = 13 to p = 17 and a = 5 to a = 6. Is the sorted row still 111 to p−1p - 1p−1?

2. Change n = 12 to n = 561. Print pow(2, 560, 561). What do you see?

Common mistakes

  • Reducing the exponent modulo ppp. The exponent goes modulo p−1p - 1p−1, the base goes modulo ppp.
  • Forgetting the condition p∤ap \nmid ap∤a. 76≡0(mod7)7^6 \equiv 0 \pmod 776≡0(mod7), not 111.
  • Using the theorem for a composite modulus. an−1≡1(modn)a^{n-1} \equiv 1 \pmod nan−1≡1(modn) can fail for composite nnn, as 121212 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)a^p \equiv a \pmod pap≡a(modp) for every aaa; ap−1≡1a^{p-1} \equiv 1ap−1≡1 when p∤ap \nmid ap∤a.
  • Proof: a,2a,…,(p−1)aa, 2a, \dots, (p - 1)aa,2a,…,(p−1)a is a shuffle of 1,…,p−11, \dots, p - 11,…,p−1.
  • Reduce exponents modulo p−1p - 1p−1.
  • ap−2a^{p-2}ap−2 is the inverse of aaa modulo ppp.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. Find the remainder of 2502^{50}250 on division by 777.
  1. Find the remainder of 61006^{100}6100 on division by 111111.
  1. Use Fermat to find the inverse of 222 modulo 131313.
  1. Show that n5−nn^5 - nn5−n is a multiple of 555 for every integer nnn, in one line.
  1. A student says that 314≡1(mod15)3^{14} \equiv 1 \pmod{15}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.
No payment. You can leave at any time.

Problems (3)

A coding club sets two remainders as a warm-up…Hard · High School (11–12) · by StemPy Lab
Prove that n⁷ - n is a multiple of 42 for every integer n…Advanced · High School (11–12) · by StemPy Lab
A quick primality test says: if aⁿ⁻¹ not≡ 1 pmod n for some a coprime to n, then n is composite…Advanced · High School (11–12) · by StemPy Lab
Next: lesson 2Euler's totient function and theorem
← The Theorems of Fermat, Euler and Wilson
← PreviousEuler's totient function and theorem →

Discussion (0)

Log in to join the discussion.

Loading…

; when
ppp
does not divide
aaa
, this becomes
ap−1≡1(modp)a^{p-1} \equiv 1 \pmod pap−1≡1(modp)
. The proof multiplies
1,2,…,p−11, 2, \dots, p - 11,2,…,p−1
by
aaa
and sees that only the order changes. With it, an exponent can be reduced modulo
p−1p - 1p−1
, and
ap−2a^{p-2}ap−2
is the inverse of
aaa
.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.