How to Calculate Euler’s Totient from Prime Factorization

Euler’s totient function can be calculated directly from the prime factorization of a positive integer. Once the distinct prime factors are known, the calculation does not require listing every integer below the number or checking each one individually for coprimality.

Euler’s Totient Function

For a positive integer n, Euler’s totient function φ(n) counts the integers from 1 through n that are coprime to n. Two integers are coprime when their greatest common divisor is 1.

Totient Formula from Prime Factorization

Suppose the prime factorization of n is written as:

Prime Factorization Form

n = p₁^a₁ × p₂^a₂ × ··· × p_k^a_k

Here, p₁, p₂, …, p_k are the distinct prime factors of n. Euler’s totient is then:

Product Formula

φ(n) = n(1 − 1/p₁)(1 − 1/p₂) ··· (1 − 1/p_k)

Each distinct prime factor appears once in the product. Its exponent in the factorization does not create additional copies of the same fraction.

Equivalent Prime-Power Formula

The same result can be written as φ(n) = p₁^a₁−1(p₁−1) × ··· × p_k^a_k−1(p_k−1).

Why the Formula Works

An integer is not coprime to n when it shares at least one prime factor with n. For a prime factor p, the fraction 1/p of the integers in a complete residue range are divisible by p. The factor 1 − 1/p keeps the fraction that is not divisible by that prime.

Applying this adjustment for every distinct prime divisor removes the integers that share any prime factor with n. The resulting count is φ(n).

Prime Factor

A prime number that divides n exactly.

Distinct Factor

A prime divisor counted once, regardless of its exponent.

Coprime Integer

An integer whose greatest common divisor with n is 1.

Example: Calculate φ(72)

The prime factorization of 72 is:

Factorization of 72

72 = 2³ × 3²

The distinct prime factors are 2 and 3, so the product formula becomes:

Totient Calculation

φ(72) = 72(1 − 1/2)(1 − 1/3)

φ(72) = 72 × 1/2 × 2/3 = 24

Therefore, 24 integers from 1 through 72 are coprime to 72.

Example with Three Distinct Prime Factors

For 360, the prime factorization is:

Factorization of 360

360 = 2³ × 3² × 5

The distinct prime factors are 2, 3, and 5:

Totient of 360

φ(360) = 360(1 − 1/2)(1 − 1/3)(1 − 1/5)

φ(360) = 360 × 1/2 × 2/3 × 4/5 = 96

The repeated powers of 2 and 3 affect the value of 360, but the fractions for 2 and 3 are each applied only once.

Prime Powers Have a Shorter Formula

When n is a power of one prime, such as n = p^a, the totient formula simplifies to:

Prime-Power Totient

φ(p^a) = p^a − p^a−1 = p^a−1(p − 1)

For example, 49 = 7². Every seventh integer is divisible by 7, so:

Totient of 49

φ(49) = 7²⁻¹(7 − 1) = 7 × 6 = 42

When n itself is prime, the exponent is 1. This gives φ(p) = p − 1, since every positive integer below a prime is coprime to it.

Totient Values from Known Factorizations

Examples of Euler’s totient calculated from distinct prime factors.
Number	Prime Factorization	Totient Calculation	φ(n)
8	2³	8(1 − 1/2)	4
12	2² × 3	12(1 − 1/2)(1 − 1/3)	4
18	2 × 3²	18(1 − 1/2)(1 − 1/3)	6
45	3² × 5	45(1 − 1/3)(1 − 1/5)	24
100	2² × 5²	100(1 − 1/2)(1 − 1/5)	40
210	2 × 3 × 5 × 7	210(1 − 1/2)(1 − 1/3)(1 − 1/5)(1 − 1/7)	48

Distinct Prime Factors Must Be Used Once

Common Mistake

For 72 = 2³ × 3², the factors (1 − 1/2) and (1 − 1/3) are each used once. Repeating the factor for 2 three times or the factor for 3 twice produces an incorrect result.

The exponents remain important because they determine the original value of n. They simply do not change the list of distinct primes used in the product.

Using the Equivalent Product Form

The prime-power version can make some calculations cleaner. For 72 = 2³ × 3²:

Alternative Calculation

φ(72) = 2³⁻¹(2 − 1) × 3²⁻¹(3 − 1)

φ(72) = 2² × 1 × 3 × 2 = 24

Both formulas always give the same value. The first starts with n and applies fractional adjustments. The second evaluates each prime-power component separately.

Special Cases

When n Is Prime

If n = p, then φ(p) = p − 1.

When n = 1

By convention, φ(1) = 1. The number 1 has no prime factorization.

When n Is a Prime Power

If n = p^a, then φ(n) = p^a−1(p − 1).

When Factors Are Coprime

If gcd(a, b) = 1, then φ(ab) = φ(a)φ(b).

Connection to Coprime Factorization

Euler’s totient function is multiplicative. When two positive integers share no prime factor, their totients multiply:

Multiplicative Property

gcd(a, b) = 1 ⇒ φ(ab) = φ(a)φ(b)

For example, 8 and 9 are coprime. Since φ(8) = 4 and φ(9) = 6:

Coprime Product Example

φ(72) = φ(8 × 9) = φ(8)φ(9) = 4 × 6 = 24

This property follows naturally from the prime-factor formula because coprime integers have separate sets of prime divisors.

Related Number Theory Concepts

Frequently Asked Questions

What Is the Fastest Formula for φ(n) from Prime Factors?

For n = p₁^a₁ ··· p_k^a_k, use φ(n) = n∏(1 − 1/p), where the product includes each distinct prime divisor once.

Do Repeated Prime Factors Appear More Than Once?

No. A prime such as 2 contributes one factor of (1 − 1/2), even when the factorization contains 2⁵ or another higher power.

What Is φ(p) When p Is Prime?

For any prime p, φ(p) = p − 1. Every integer from 1 through p − 1 is coprime to p.

Can φ(n) Be Calculated Without Prime Factorization?

Yes. Small values can be found by counting integers whose greatest common divisor with n is 1. For larger numbers, a known prime factorization usually makes the calculation much shorter.