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
  1. Notes
  2. /Fermat, Euler and Wilson: Quick Revision
Mathematics

Fermat, Euler and Wilson: Quick Revision

A brief note on Fermat's little theorem, Euler's totient and theorem, last digits, Wilson's theorem and orders, with a worked example, practice, a program and questions.

StemPy LabWritten by StemPy Lab
Log in to save

A brief note on Fermat, Euler and Wilson. Read it before a test. Try each question at the end before you open its answer.

The three theorems

  • Fermat: ap≡a(modp)a^p \equiv a \pmod pap≡a(modp) for a prime ppp; ap−1≡1a^{p-1} \equiv 1ap−1≡1 when p∤ap \nmid ap∤a.
  • Euler: aφ(n)≡1(modn)a^{\varphi(n)} \equiv 1 \pmod naφ(n)≡1(modn) when gcd⁡(a,n)=1\gcd(a, n) = 1gcd(a,n)=1.
  • Wilson: (p−1)!≡−1(modp)(p - 1)! \equiv -1 \pmod p(p−1)!≡−1(modp) exactly when ppp is prime.

The totient

  • Prime power: φ(pk)=pk−1(p−1)\varphi(p^k) = p^{k-1}(p - 1)φ(pk)=pk−1(p−1).
  • Product: φ(mn)=φ(m)φ(n)\varphi(mn) = \varphi(m)\varphi(n)φ(mn)=φ(m)φ(n) when gcd⁡(m,n)=1\gcd(m, n) = 1gcd(m,n)=1.
  • Formula: φ(n)=n∏(1−1p)\varphi(n) = n\prod(1 - \frac{1}{p})φ(n)=n∏(1−p1​) over the primes p∣np \mid np∣n.
  • Divisor sum: ∑d∣nφ(d)=n\sum_{d \mid n}\varphi(d) = n∑d∣n​φ(d)=n.

Orders

  • Order: the least k≥1k \ge 1k≥1 with ak≡1(modn)a^k \equiv 1 \pmod nak≡1(modn).
  • Divides: am≡1a^m \equiv 1am≡1 exactly when the order divides mmm; so the order divides φ(n)\varphi(n)φ(n).
  • Decimals: the period of 1p\frac{1}{p}p1​ is the order of 101010 modulo ppp.
  • Minus one: x2≡−1(modp)x^2 \equiv -1 \pmod px2≡−1(modp) is solvable for p=2p = 2p=2 and for p≡1(mod4)p \equiv 1 \pmod 4p≡1(mod4) only.

A worked example

Find 51235^{123}5123 modulo 363636.

  1. Euler. φ(36)=12\varphi(36) = 12φ(36)=12, and gcd⁡(5,36)=1\gcd(5, 36) = 1gcd(5,36)=1.
  2. Cut. 123=12×10+3123 = 12 \times 10 + 3123=12×10+3, so 5123≡53=1255^{123} \equiv 5^3 = 1255123≡53=125.
  3. Reduce. 125=3×36+17125 = 3 \times 36 + 17125=3×36+17, so the remainder is 171717.

Practice with new numbers

A program to try

The program checks each theorem on one small case.

Read it first. Then run it. Does each line print what the theorem predicts?

1. Change p, n = 11, 20 to p, n = 12, 21. Which line breaks, and why?

Mistakes to avoid

  • Reducing an exponent modulo ppp instead of p−1p - 1p−1.
  • Using Euler when gcd⁡(a,n)>1\gcd(a, n) > 1gcd(a,n)>1.
  • Using Wilson or Fermat for a composite modulus.
  • Losing a sign when peeling factors near ppp: p−1≡−1p - 1 \equiv -1p−1≡−1, p−2≡−2p - 2 \equiv -2p−2≡−2.

Check yourself

  1. Find φ(84)\varphi(84)φ(84).
  1. Find the remainder of 4514^{51}451 on division by 777.
  1. Find 18!18!18! modulo 191919.
  1. What is the order of 333 modulo 777?

Sources

  • David M. Burton, Elementary Number Theory, Chapters 5 and 7.
← All Notes
← Congruences and the Chinese Remainder Theorem: Quick RevisionDiophantine Equations and Pythagorean Triples: Quick Revision →
More onNumber Theory

Discussion (0)

Log in to join the discussion.

Loading…

On this page

  1. The three theorems
  2. The totient
  3. Orders
  4. A worked example
  5. Practice with new numbers
  6. A program to try
  7. Mistakes to avoid
  8. Check yourself
  9. Sources

Goes with the lesson

  1. Wilson's theorem and the order of a numberThe Theorems of Fermat, Euler and Wilson

More notes on this topic

  1. Diophantine Equations and Pythagorean Triples: Quick Revision
  2. Congruences and the Chinese Remainder Theorem: Quick Revision
  3. Factorials, Irrational Numbers, Digits and the Floor Function: Quick Revision
  4. Common Factors, the Euclidean Algorithm and Divisors: Quick Revision
  5. Division, Divisibility Rules and Primes: Quick Revision
All notes on this topic →