// NUMBER THEORY · ADVANCED

Euler's Totient Function

φ(n) counts the numbers that share no common factor with n. It is the bridge from Fermat to RSA.

Count Coprimes Play Counter
Advanced·22 min·Mathematics · Number Theory
Reviewed by CodeTikki Academic Team

Prerequisites: Prime factorization · GCD · Modular arithmetic

// VISUALIZER

Count numbers that share no factor with n

Enter n and watch the sieve. Green cells are coprime to n; red cells share a factor. The total green count is φ(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Total

24

Coprime

0

φ(n)

8

Press PLAY to highlight numbers coprime to n in green.

// MINI GAME

Totient Counter

Select every number from 1 to n that is coprime to n. Submit when you think you have found all φ(n) numbers.

Loading numbers...

// FLOWCHART

Algorithm flow

// FLOWCHART · Euler's Totient Function
Count and compute φ(n)
StartRead nFind distinctprime factors of nφ(n) = n × Π(1 − 1/p)Output φ(n)End

Press PLAY to trace the algorithm through the flowchart.

0 / 6

// PSEUDOCODE

Trace the code

// PSEUDOCODE · Euler's Totient Function
Compute φ(12)
n = 12
1function totient(n):
2 result = n
3 for p = 2 to √n:
4 if n mod p == 0:
5 while n mod p == 0:
6 n = n / p
7 result = result - result / p
8 if n > 1:
9 result = result - result / n
10 return result

Press PLAY to step through the algorithm line by line.

0 / 11

// TUTORIAL QUIZZES

Test your mastery

From counting coprimes to the product formula and RSA.

// PRACTICE & ASSESS

Test your understanding

Now that you've learned the concept, put it into practice. Solve coding problems and take quizzes to reinforce what you've learned.

💻

Coding Problems

The Totient Counter: Compute φ(n)L4The Coprime Pair: Count Coprime NumbersL5The RSA Key: Find φ(n)L6The Euler's Theorem: Reduce Big ExponentsL7The Multiplicative Totient: Solve φ(ab)L8

// REFERENCES

Sources & further reading

  1. [1]
    Introductio in analysin infinitorumLeonhard Euler — introduced the totient function
  2. [2]
    Disquisitiones ArithmeticaeCarl Friedrich Gauss — number-theoretic foundations
  3. [3]
    Introduction to Algorithms (CLRS)T. H. Cormen et al. — number-theoretic algorithms
  4. [4]
    A Course in Number Theory and CryptographyNeal Koblitz — RSA and Euler totient

// READY?

Six number-theory tutorials are live

From GCD to Euler's Totient, each page has animations, games, quizzes, and full SEO. Dive into the hub to explore them all.

Browse Tutorials Fermat's Theorem