Course contentsShow
← Mathematics
Lesson 2746 of 3,12154. Number TheoryFree lesson

Euler's Totient Function φ(n)

Define φ(n) as the count of integers from 1 to n that are coprime to n, and compute φ for various n.

Euler's Totient Function φ(n)

What you'll learn: You'll understand how to count how many numbers less than or equal to n share no common factors with n.

The Core Idea

Euler's totient function, denoted φ(n) (read "phi of n"), counts the number of integers between 1 and n (inclusive) that are relatively prime to n — meaning they share no divisors with n except 1.

Think of it as a "compatibility counter": if you're working modulo n, φ(n) tells you how many numbers from 1 to n have modular inverses (the ones that are coprime to n).

Computing φ(n) by Inspection

For small n, you can list candidates and check:

Example 1: φ(8)

  • Integers from 1 to 8: {1, 2, 3, 4, 5, 6, 7, 8}
  • Which are coprime to 8? Check gcd(k, 8) = 1
    • gcd(1,8)=1 ✓, gcd(2,8)=2 ✗, gcd(3,8)=1 ✓, gcd(4,8)=4 ✗
    • gcd(5,8)=1 ✓, gcd(6,8)=2 ✗, gcd(7,8)=1 ✓, gcd(8,8)=8 ✗
  • Count: {1, 3, 5, 7} → φ(8) = 4

Example 2: φ(9)

  • Coprime to 9: {1, 2, 4, 5, 7, 8} (skip multiples of 3)
  • φ(9) = 6

Example 3: φ(7)

  • Since 7 is prime, all numbers 1 through 6 are coprime to 7
  • φ(7) = 6

Pattern for primes: If p is prime, then φ(p) = p − 1, because every smaller positive integer is coprime to a prime.

Key Takeaway: φ(n) counts integers from 1 to n that are relatively prime to n; for any prime p, φ(p) = p − 1.