Euler's totient φ(n) counts the numbers from 1 to n
Lesson 2 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
compute φ(n) from the prime factors of n;
use the facts that φ is multiplicative and that the totients of the divisors add up to n;
use Euler's theorem to find the last digits of a large power.
Fractions in lowest terms
Write the fractions 121,122,…,1212 in lowest terms. Which of them still have denominator 12? Only 121,125,127,1211, because 1,5,7,11 share no factor with 12.
Euler's totient function counts them:
φ(n)=the number of k with 1≤k≤n and gcd(k,n)=1.
So φ(12)=4. Also φ(1)=1, and φ(p)=p−1 for a prime p. The Greek letter φ is read "phi".
A formula
Prime powers. From 1 to pk, the numbers that share a factor with pk are the multiples of p, and there are pk−1 of them. So
φ(pk)=pk−pk−1=pk−1(p−1).
Products. If gcd(m,n)=1, then φ(mn)=φ(m)φ(n). The reason is the Chinese remainder theorem. A number modulo mn is a pair of remainders, one modulo m and one modulo n. It is coprime to mn exactly when both parts are coprime to their moduli. So we count φ(m)×φ(n) pairs.
Together. If n=p1k1p2k2⋯prkr, then
φ(n)=n(1−p11)(1−p21)
⋯(1−pr1).
For example φ(100)=100×21×54=40, and φ(36)=36×21×32=12.
The divisor sum
Split the fractions 121,…,1212 by the denominator they have in lowest terms. Denominator d appears exactly φ(d) times, and every d is a divisor of 12. So
d∣n∑φ(d)=n.
For n=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, then
aφ(n)≡1(modn).
The proof copies Fermat's. Let r1,…,rφ(n) be the numbers from 1 to n coprime to n. Multiplying each by a only shuffles them. Multiply them all, and cancel the product of the ri. For a prime n=p this is Fermat's theorem, since φ(p)=p−1.
Last digits
The last two digits of a number are its remainder modulo 100, and φ(100)=40.
Find the last two digits of 31234.
Euler.gcd(3,100)=1, so 340≡1(mod100).
Cut the exponent.1234=40×30+34, so 31234≡334.
Work it out.35=243≡43, 310≡432=1849≡49, 320≡492=2401≡1. So 334=320⋅310⋅34≡49×81=3969≡69.
The last two digits are 69. Notice that 320 was already 1: 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 777 modulo 10: φ(10)=4, so we need 77 modulo 4. Since 7≡−1(mod4), 77≡−1≡3. So 777≡73=343≡3(mod10).
Practise with new numbers
Try it in Python
The program computes φ(n) by counting and by the formula, then uses Euler's theorem for a last-two-digits question.
Common mistakes
Multiplying totients of numbers that share a factor.φ(4)=φ(2)φ(2): it is 2, not 1.
Using Euler without gcd(a,n)=1.240≡1(mod100), since 240 is even.
Writing φ(pk)=pk−1. The multiples of p must all go: φ(pk)=pk−pk−1.
Reducing a tower's exponent modulo n. In abc modulo n, the exponent bc goes modulo φ(n).
Remember these
φ(pk)=pk−1(p−1), and φ(mn)=φ(m)φ(n) when gcd(m,n)=1.
φ(n)=n∏(1−p1).
∑d∣nφ(d)=n.
aφ(n)≡1(modn) when gcd(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.
Find φ(45).
How many fractions 50k with 1≤k≤50 are already in lowest terms?
Find the last digit of 951.
Check the divisor sum for n=10.
Find the remainder of 7100 on division by 15.
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.