Recently, I was going through [segment tree problems](https://mirror.codeforces.com/blog/entry/22616) list and encountered [this problem](https://mirror.codeforces.com/contest/594/problem/D)↵
↵
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.↵
↵
---↵
↵
## 1. Core Mathematical Concepts Involving Primes↵
↵
### Prime Numbers↵
Integers > 1 with exactly two divisors. ↵
Used in: divisibility, coprimality, modular arithmetic.↵
↵
### Coprime numbers↵
Two numbers are coprime if:<br>↵
**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.<br>↵
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?**<br>↵
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:<br>↵
**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:<br>↵
**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)↵
↵
~~~~
↵
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.↵
↵
---↵
↵
↵
Integers > 1 with exactly two divisors. ↵
Used in: divisibility, coprimality, modular arithmetic.↵
↵
### Coprime numbers↵
Two numbers are coprime if:<br>↵
**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.<br>↵
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?**<br>↵
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:<br>↵
**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:<br>↵
**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)↵
↵
~~~~
