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. /Euler's totient function and theorem

Course 28.2·Lesson 2 of 3

Euler's totient function and theorem

Euler's totient φ(n)\varphi(n)φ(n) counts the numbers from 111 to nnn

Lesson 2 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

  • compute φ(n)\varphi(n)φ(n) from the prime factors of nnn;
  • use the facts that φ\varphiφ is multiplicative and that the totients of the divisors add up to nnn;
  • use Euler's theorem to find the last digits of a large power.

Fractions in lowest terms

Write the fractions 112,212,…,1212\dfrac{1}{12}, \dfrac{2}{12}, \dots, \dfrac{12}{12}121​,122​,…,1212​ in lowest terms. Which of them still have denominator 121212? Only 112,512,712,1112\dfrac{1}{12}, \dfrac{5}{12}, \dfrac{7}{12}, \dfrac{11}{12}121​,125​,127​,1211​, because 1,5,7,111, 5, 7, 111,5,7,11 share no factor with 121212.

Euler's totient function counts them:

φ(n)=the number of k with 1≤k≤n and gcd⁡(k,n)=1.\displaystyle \varphi(n) = \text{the number of } k \text{ with } 1 \le k \le n \text{ and } \gcd(k, n) = 1.φ(n)=the number of k with 1≤k≤n and gcd(k,n)=1.

So φ(12)=4\varphi(12) = 4φ(12)=4. Also φ(1)=1\varphi(1) = 1φ(1)=1, and φ(p)=p−1\varphi(p) = p - 1φ(p)=p−1 for a prime ppp. The Greek letter φ\varphiφ is read "phi".

A formula

Prime powers. From 111 to pkp^kpk, the numbers that share a factor with pkp^kpk are the multiples of ppp, and there are pk−1p^{k-1}pk−1 of them. So

φ(pk)=pk−pk−1=pk−1(p−1).\displaystyle \varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1).φ(pk)=pk−pk−1=pk−1(p−1).

Products. If gcd⁡(m,n)=1\gcd(m, n) = 1gcd(m,n)=1, then φ(mn)=φ(m)φ(n)\varphi(mn) = \varphi(m)\varphi(n)φ(mn)=φ(m)φ(n). The reason is the Chinese remainder theorem. A number modulo mnmnmn is a pair of remainders, one modulo mmm and one modulo nnn. It is coprime to mnmnmn exactly when both parts are coprime to their moduli. So we count φ(m)×φ(n)\varphi(m) \times \varphi(n)φ(m)×φ(n) pairs.

Together. If n=p1k1p2k2⋯prkrn = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}n=p1k1​​p2k2​​⋯prkr​​, then

φ(n)=n(1−1p1)(1−1p2)\displaystyle \varphi(n) = n\left(1 - \dfrac{1}{p_1}\right)\left(1 - \dfrac{1}{p_2}\right)φ(n)=n(1−p1​1​)(1−p2​1​)
⋯(1−1pr).\displaystyle \cdots\left(1 - \dfrac{1}{p_r}\right).⋯(1−pr​1​).

For example φ(100)=100×12×45=40\varphi(100) = 100 \times \tfrac12 \times \tfrac45 = 40φ(100)=100×21​×54​=40, and φ(36)=36×12×23=12\varphi(36) = 36 \times \tfrac12 \times \tfrac23 = 12φ(36)=36×21​×32​=12.

The divisor sum

Split the fractions 112,…,1212\dfrac{1}{12}, \dots, \dfrac{12}{12}121​,…,1212​ by the denominator they have in lowest terms. Denominator ddd appears exactly φ(d)\varphi(d)φ(d) times, and every ddd is a divisor of 121212. So

∑d∣nφ(d)=n.\displaystyle \sum_{d \mid n} \varphi(d) = n.d∣n∑​φ(d)=n.

For n=12n = 12n=12: φ(1)+φ(2)+φ(3)+φ(4)+φ(6)+φ(12)=1+1+2+2+2+4=12\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12φ(1)+φ(2)+φ(3)+φ(4)+φ(6)+φ(12)=1+1+2+2+2+4=12.

A bar chart of phi(n) for n from 1 to 30. The bars for the primes 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29 are orange and reach n - 1, the highest possible. The other bars are blue and lower, for example phi(12) = 4, phi(24) = 8 and phi(30) = 8. A dashed line shows y = n - 1.

Euler's theorem

Euler's theorem. If gcd⁡(a,n)=1\gcd(a, n) = 1gcd(a,n)=1, then

aφ(n)≡1(modn).\displaystyle a^{\varphi(n)} \equiv 1 \pmod n.aφ(n)≡1(modn).

The proof copies Fermat's. Let r1,…,rφ(n)r_1, \dots, r_{\varphi(n)}r1​,…,rφ(n)​ be the numbers from 111 to nnn coprime to nnn. Multiplying each by aaa only shuffles them. Multiply them all, and cancel the product of the rir_iri​. For a prime n=pn = pn=p this is Fermat's theorem, since φ(p)=p−1\varphi(p) = p - 1φ(p)=p−1.

Last digits

The last two digits of a number are its remainder modulo 100100100, and φ(100)=40\varphi(100) = 40φ(100)=40.

Find the last two digits of 312343^{1234}31234.

  1. Euler. gcd⁡(3,100)=1\gcd(3, 100) = 1gcd(3,100)=1, so 340≡1(mod100)3^{40} \equiv 1 \pmod{100}340≡1(mod100).
  2. Cut the exponent. 1234=40×30+341234 = 40 \times 30 + 341234=40×30+34, so 31234≡3343^{1234} \equiv 3^{34}31234≡334.
  3. Work it out. 35=243≡433^5 = 243 \equiv 4335=243≡43, 310≡432=1849≡493^{10} \equiv 43^2 = 1849 \equiv 49310≡432=1849≡49, 320≡492=2401≡13^{20} \equiv 49^2 = 2401 \equiv 1320≡492=2401≡1. So 334=320⋅310⋅34≡49×81=3969≡693^{34} = 3^{20} \cdot 3^{10} \cdot 3^4 \equiv 49 \times 81 = 3969 \equiv 69334=320⋅310⋅34≡49×81=3969≡69.

The last two digits are 696969. Notice that 3203^{20}320 was already 111: Euler gives an exponent that always works, but a smaller one may work too. The next lesson names the smallest one, the order.

Towers. For 7777^{7^7}777 modulo 101010: φ(10)=4\varphi(10) = 4φ(10)=4, so we need 777^777 modulo 444. Since 7≡−1(mod4)7 \equiv -1 \pmod 47≡−1(mod4), 77≡−1≡37^7 \equiv -1 \equiv 377≡−1≡3. So 777≡73=343≡3(mod10)7^{7^7} \equiv 7^3 = 343 \equiv 3 \pmod{10}777≡73=343≡3(mod10).

Practise with new numbers

Try it in Python

The program computes φ(n)\varphi(n)φ(n) by counting and by the formula, then uses Euler's theorem for a last-two-digits question.

Read it first. Then run it. Do the two columns agree?

1. Add 360 and 1024 to the list of numbers. Predict φ\varphiφ of each first.

2. Find the last two digits of 3 ** 1234 with pow. Does it match the lesson?

Common mistakes

  • Multiplying totients of numbers that share a factor. φ(4)≠φ(2)φ(2)\varphi(4) \ne \varphi(2)\varphi(2)φ(4)=φ(2)φ(2): it is 222, not 111.
  • Using Euler without gcd⁡(a,n)=1\gcd(a, n) = 1gcd(a,n)=1. 240≢1(mod100)2^{40} \not\equiv 1 \pmod{100}240≡1(mod100), since 2402^{40}240 is even.
  • Writing φ(pk)=pk−1\varphi(p^k) = p^k - 1φ(pk)=pk−1. The multiples of ppp must all go: φ(pk)=pk−pk−1\varphi(p^k) = p^k - p^{k-1}φ(pk)=pk−pk−1.
  • Reducing a tower's exponent modulo nnn. In abca^{b^c}abc modulo nnn, the exponent bcb^cbc goes modulo φ(n)\varphi(n)φ(n).

Remember these

  • φ(pk)=pk−1(p−1)\varphi(p^k) = p^{k-1}(p - 1)φ(pk)=pk−1(p−1), and φ(mn)=φ(m)φ(n)\varphi(mn) = \varphi(m)\varphi(n)φ(mn)=φ(m)φ(n) when gcd⁡(m,n)=1\gcd(m, n) = 1gcd(m,n)=1.
  • φ(n)=n∏(1−1p)\varphi(n) = n\prod(1 - \frac{1}{p})φ(n)=n∏(1−p1​).
  • ∑d∣nφ(d)=n\sum_{d \mid n}\varphi(d) = n∑d∣n​φ(d)=n.
  • 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.

Check yourself

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

  1. Find φ(45)\varphi(45)φ(45).
  1. How many fractions k50\dfrac{k}{50}50k​ with 1≤k≤501 \le k \le 501≤k≤50 are already in lowest terms?
  1. Find the last digit of 9519^{51}951.
  1. Check the divisor sum for n=10n = 10n=10.
  1. Find the remainder of 71007^{100}7100 on division by 151515.

References

  • David M. Burton, Elementary Number Theory, Chapter 7, Euler's Generalization of 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 (4)

A music teacher divides a 360-beat cycle into fractions k/360 for k = 1, 2, …, 359…Hard · High School (11–12) · by StemPy Lab
Find the last two digits of 13²⁰²⁶, that is, its remainder on division by 100…Hard · High School (11–12) · by StemPy Lab
Prove that Σ_(d mid n)φ(d) = n for every positive integer n, by sorting the fractions 1/n, 2/n, ……Advanced · High School (11–12) · by StemPy Lab
Next: lesson 3Wilson's theorem and the order of a number
← The Theorems of Fermat, Euler and Wilson
← Fermat's little theoremWilson's theorem and the order of a number →

Discussion (0)

Log in to join the discussion.

Loading…

that share no factor with
nnn
. It is multiplicative,
φ(pk)=pk−pk−1\varphi(p^k) = p^k - p^{k-1}φ(pk)=pk−pk−1
, so
φ(n)=n∏(1−1p)\varphi(n) = n\prod(1 - \frac{1}{p})φ(n)=n∏(1−p1​)
over the primes
ppp
dividing
nnn
, and the totients of the divisors of
nnn
add up to
nnn
. Euler's theorem says
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
.
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.

Find every positive integer n with φ(n) = 12…Advanced · High School (11–12) · by StemPy Lab

Python Labs (1)

Euler's totient two waysPython Lab · by StemPy Lab