Recently, I was going through segment tree problems list and encountered this problem

It introduced me to the Euler's Totient Formula and it took multiple attempts for me to understand the concept, because of the mathematical notations and terms used. So I thought of creating of this resource for me to understand the formula in a more intutive way, and hope it will help other beginners also.

I have started from the core prime number concepts and have built up to the final formula.

I hope this is helpful.

Prime Numbers

Integers > 1 with exactly two divisors.
Used in: divisibility, coprimality, modular arithmetic.

Coprime numbers

Two numbers are coprime if:
They do not share any prime factor.

Examples:

gcd(8, 15) = 1 8 = 2³ 15 = 3 × 5 → No common prime → coprime

• gcd(12, 18) = 6 12 = 2² × 3 18 = 2 × 3² → Both share prime 2 and 3 → not coprime

So “coprime” simply means: No prime number divides both.

• Two numbers are are coprime if: gcd(a, b) = 1

• All numbers are coprime with 1 by definition

Prime Factorization

Every integer can be uniquely written as product of prime numbers.
Examples:

• 12 = 2 × 2 × 3 = 2² × 3¹

• 18 = 2 × 3 × 3 = 2¹ × 3²

• 20 = 2 × 2 × 5 = 2² × 5¹

• 15 = 3 × 5 = 3¹ × 5¹

• 7 = 7¹ (just prime)

Why is this important?
Because prime numbers act like the building blocks of integers.

Euler's Totient function φ(n)

φ(n) counts how many numbers from 1 to n are coprime to n. In other words:
count numbers ≤ n that share NO prime with n

Example: n = 12
prime factors = {2, 3}

numbers 1 to 12:
  1 2 3 4 5 6 7 8 9 10 11 12

remove numbers sharing prime 2:
  2,4,6,8,10,12

remove numbers sharing prime 3:
  3,6,9,12

remaining:
  1, 5, 7, 11

so φ(12) = 4.

Key Idea

A number is bad if it is divisible by any prime dividing n.

Take n = 12 = 2² × 3¹

Primes: 2, 3

• If x divisible by 2 → x not coprime

• If x divisible by 3 → x not coprime

This is the only reason. Nothing else makes a number non-coprime.

So everything reduces to:
Check divisibility by prime factors of n.

This is why prime factorization and φ(n) are directly connected.

Derivation for euler's formula

We can observe that, for the range 1 to n, there will be n/x multiples of x.

so suppose there are two prime factors x, y

Then, Euler(n) = n(1 - 1/x)(1 - 1/y)

How?

(n — n/x) => numbers which are not multiple of x. Let these leftover numbers be called n2

from these n2, we want to remove the multiples of y

so, n2 * ( 1 - 1 / y) are left over numbers. Let this be called n3.

n3 reperesents all the number which does not have prime numbers x and y as factors

suppose there was one more factor z

then we would do n4 = n3 * (1 - 1 / z)

Thus we arrive at the final answer when we expand this equation

Euler(n) = n3 * (1 - 1/z)

= n2 * (1 - 1/ y) * (1 - 1/z)

= (n - n / x) * (1 - 1 / y) * (1 - 1 / z)

= n * (1 - 1 / x) * (1 - 1 / y) * (1 - 1 / z)

Like this, if we want to find Euler(n) where n = x1^a1 * x2^a2 * x3^a3 .... * xn^bn

where, x1, x2, xn are prime numbers and a1, a2, a3 are the powers to which they are raised,

We can say that:

Euler(n) = n *(1 - 1 / x1) * (1 - 1 / x2) * ... (1 - 1 / xn)