How is Euler's totient function $φ(n)$ defined?

Conditions

• $n$ is a positive integer.
• The counting range is from 1 to $n$ inclusive.
• Coprimality is determined by the greatest common divisor being 1.

Reasoning, step by step

1. Identify the range of integers to check: from 1 to $n$.
2. For each integer $a$ in this range, calculate the greatest common divisor of $a$ and $n$, denoted as $\gcd(a, n)$.
3. Check if $\gcd(a, n) = 1$. If it is, $a$ is coprime to $n$.
4. Count the total number of integers $a$ that satisfy this condition.
5. The resulting count is the value of $\varphi(n)$.

Example

For $n=6$, the integers from 1 to 6 are 1, 2, 3, 4, 5, 6. The greatest common divisors with 6 are: $\gcd(1,6)=1$, $\gcd(2,6)=2$, $\gcd(3,6)=3$, $\gcd(4,6)=2$, $\gcd(5,6)=1$, $\gcd(6,6)=6$. Only 1 and 5 have a greatest common divisor of 1 with 6. Therefore, $\varphi(6) = 2$.

Common misconceptions

• Believing that $\varphi(n)$ counts the number of prime factors of $n$.
• Thinking that $\varphi(n)$ includes 0 in the counting range (the range is strictly 1 to $n$).
• Confusing coprime with prime; a number can be coprime to $n$ without being prime itself (e.g., 1 is coprime to 6 but is not prime).

Watch the explanation

Explore next

• How can we use the greatest common divisor to determine whether two numbers are coprime?
• Why does a prime number p satisfy $φ(p) = p - 1$?
• What is the general formula for Euler's totient function?