Euler's totient function
- Olympiad · IOQM
Euler's totient function φ(n) counts the whole numbers from 1 to n that share no factor with n other than 1.
It is also called Euler's phi function. Two numbers are co-prime when their HCF is 1. So φ(n) tells you how many numbers up to n have nothing in common with n.
For a prime p, every number from 1 to p - 1 is co-prime to p. So φ(p) = p - 1. For example, φ(7) = 6.
A small example
Find φ(12). Go through 1 to 12 and drop any number that shares a factor 2 or 3 with 12:
- Kept: 1, 5, 7, 11.
- Dropped: 2, 3, 4, 6, 8, 9, 10, 12.
- So φ(12) = 4.
Euler used it to widen Fermat's little theorem. If a is co-prime to n, then a raised to φ(n) leaves remainder 1 on division by n. Check it with a = 5 and n = 12. Here 5⁴ = 625, and 625 = 12 × 52 + 1. The remainder is 1, as the rule says.
Where it fits
This goes beyond the Class 10 board syllabus. HBCSE's syllabus for the Mathematical Olympiad names it under number theory. The Mathematics Teachers' Association (India), MTA(I), conducts IOQM, the first stage of the Mathematical Olympiad Programme that HBCSE organises for NBHM.
Sources
Facts last checked against these sources on 30 September 2026.
- Syllabus for Mathematical Olympiad (Number Theory) · HBCSE, TIFR
- Mathematical Olympiad 2026-2027: stages of selection · HBCSE, TIFR
- Brochure: Mathematical Olympiads 2026-2027 · HBCSE, TIFR
About the author
Chief Architect
An engineer (B.Tech, Computer Science) with over 20 years of preparing students for entrance exams, including as Dean at FIITJEE and Vice-President at Aakash. He is the chief architect of the TRUpreBoards evaluation engine.
Mohit Sardana on LinkedIn