Free CAT library

Euler’s Totient Function phi(N) & Co-prime Counting

Master Euler's Totient function to count the number of co-primes less than a number, find their sum, and unlock advanced modular arithmetic shortcuts.

1. The Story & Mental Model

Imagine a grand party hosted by King NN. He wants to invite all integers less than himself, from 11 to N−1N-1. But the King is paranoid; he refuses to invite anyone who shares any common trait (prime factor) with him. If the King is 12 (made of 22s and 33s), he will ban anyone who is even (shares a 22) or a multiple of 3 (shares a 33).

The guests who actually make it to the party are the "co-primes" of NN. Their greatest common divisor with NN is 1. Leonhard Euler found a beautiful way to count these guests without checking the list one by one. You start with the total population (NN), and successively remove the fraction of people who share prime traits with the King. This elegant counting mechanism is Euler's Totient Function, ϕ(N)\phi(N).

2. The CAT Question Blueprint

Euler's totient function is a stealth weapon. The exam setters won't explicitly say "Find phi(N)". Instead, they will:

  • Ask you for the number of positive integers less than NN and co-prime to it.

  • Ask for the sum of all integers less than NN that are co-prime to it.

  • Use it as a backdoor to solve massive remainders (Fermat-Euler Theorem).

  • Frame it as fractions: "How many irreducible proper fractions can be formed with NN as the denominator?" (This is exactly ϕ(N)\phi(N)).

3. Core Concepts, Formulae & Derivations

A. Definition of Co-primes

Two numbers aa and bb are co-prime (or relatively prime) if their greatest common divisor gcd⁡(a,b)=1\gcd(a, b) = 1. Note: they don't have to be prime themselves! (e.g., 8 and 9 are co-prime, even though neither is prime).

B. Euler's Totient Function ϕ(N)\phi(N)

If the prime factorization of NN is p1a×p2b…p_1^a \times p_2^b \dots

Then the number of integers less than NN and co-prime to NN is given by:

ϕ(N)=N(1−1p1)(1−1p2)…\phi(N) = N \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\dots

Derivation logic: If N=12N=12 (22×312^2 \times 3^1), we start with 12 numbers. Half of them are multiples of 2, so we multiply by (1−1/2)(1 - 1/2). Now 6 numbers remain. One-third of those remaining are multiples of 3, so we multiply by (1−1/3)=2/3(1 - 1/3) = 2/3. 6×(2/3)=46 \times (2/3) = 4. The four numbers are 1, 5, 7, 11.

C. Sum of Co-primes

The sum of all integers less than NN and co-prime to NN is:

Sum=N2×ϕ(N)\text{Sum} = \frac{N}{2} \times \phi(N)

Derivation logic: Co-primes always occur in symmetric pairs that sum to NN. For N=12N=12, the co-primes are 1,5,7,111, 5, 7, 11. Notice that 1+11=121+11 = 12 and 5+7=125+7 = 12. There are ϕ(N)/2\phi(N)/2 such pairs.

D. Prime Totient

If PP is a prime number, it shares no factors with anything smaller than itself.

ϕ(P)=P−1\phi(P) = P - 1

4. Common Pitfalls & Speed Shortcuts

  • Pitfall: Applying the formula to composite bases without prime factorizing first. For ϕ(36)\phi(36), do NOT use (1−1/6)(1 - 1/6). Break 36 down to 22×322^2 \times 3^2, then use (1−1/2)(1−1/3)(1 - 1/2)(1 - 1/3).

  • Shortcut: If you are asked to find the number of ways NN can be expressed as a product of two co-prime factors, the answer is always 2k−12^{k-1}, where kk is the number of distinct prime factors of NN. Don't calculate ϕ(N)\phi(N) for this specific question!

Formulas

Euler's Totient phi(N)

ϕ(N)=N∏(1−1pi)\phi(N) = N \prod \left(1 - \frac{1}{p_i}\right)

p_i are the unique prime factors of N. The exponents don't matter in the parenthesis.
Sum of Co-primes to N

Sum=N2×ϕ(N)\text{Sum} = \frac{N}{2} \times \phi(N)

Valid for N > 2.
Totient of a Prime

ϕ(P)=P−1\phi(P) = P - 1

Every number less than a prime is co-prime to it.

Traps and tips

  • The exponents in prime factorization do not appear inside the (1 - 1/p) brackets.
  • 1 is considered co-prime to every integer.
  • Co-primes less than N always sum to N when paired symmetrically from ends (k and N-k).

Solved examples

The Guest List Count

How many positive integers less than 120120 are co-prime to 120120?

Show solution

This is a direct application of Euler's Totient Function, ϕ(120)\phi(120).

First, find the prime factorization of 120.

120=12×10=(22×3)×(2×5)=23×31×51120 = 12 \times 10 = (2^2 \times 3) \times (2 \times 5) = 2^3 \times 3^1 \times 5^1.

The distinct prime factors are 2,32, 3, and 55.

Apply the formula:

ϕ(120)=120×(1−12)×(1−13)×(1−15)\phi(120) = 120 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) \times \left(1 - \frac{1}{5}\right)

ϕ(120)=120×(12)×(23)×(45)\phi(120) = 120 \times \left(\frac{1}{2}\right) \times \left(\frac{2}{3}\right) \times \left(\frac{4}{5}\right)

Simplify the fraction multiplication:

ϕ(120)=120×830\phi(120) = 120 \times \frac{8}{30}

ϕ(120)=4×8=32\phi(120) = 4 \times 8 = 32.

There are 32 integers less than 120 that share no common factors with 120.

Takeaway: The totient function only cares about the unique prime bases, not their exponents. Just multiply N by (1 - 1/p) for each unique prime.

Irreducible Fractions

How many proper fractions with a denominator of 9090 cannot be further simplified?

Show solution

A proper fraction is of the form N/90N/90 where N<90N < 90.

For the fraction to be irreducible (in its simplest form), the numerator NN and the denominator 9090 must not share any common factors other than 1.

This means NN must be co-prime to 9090.

So, the question is simply asking for ϕ(90)\phi(90).

Prime factorize 90:

90=9×10=32×2×590 = 9 \times 10 = 3^2 \times 2 \times 5.

ϕ(90)=90×(1−12)×(1−13)×(1−15)\phi(90) = 90 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) \times \left(1 - \frac{1}{5}\right)

=90×12×23×45= 90 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5}

=90×830=3×8=24= 90 \times \frac{8}{30} = 3 \times 8 = 24.

There are 24 proper fractions with a denominator of 90 that cannot be reduced.

Takeaway: Questions asking for 'irreducible proper fractions' are disguised Euler Totient problems.

The Sum of the Excluded

Find the sum of all positive integers less than 6060 that are co-prime to 6060.

Show solution

We use the formula for the sum of co-primes: Sum=N2×ϕ(N)\text{Sum} = \frac{N}{2} \times \phi(N).

First, find ϕ(60)\phi(60).

60=4×15=22×31×5160 = 4 \times 15 = 2^2 \times 3^1 \times 5^1.

ϕ(60)=60×(1−12)×(1−13)×(1−15)\phi(60) = 60 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) \times \left(1 - \frac{1}{5}\right)

=60×12×23×45= 60 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5}

=60×830=16= 60 \times \frac{8}{30} = 16.

Now, calculate the sum:

Sum=602×16\text{Sum} = \frac{60}{2} \times 16

=30×16=480= 30 \times 16 = 480.

The sum of those 16 integers is 480.

Takeaway: Co-primes come in pairs that sum to N. Therefore, their total sum is simply the number of pairs (phi(N) / 2) multiplied by N.

Totient of a Power

If ϕ(N)=40\phi(N) = 40 and N=pkN = p^k where pp is a prime, find the smallest possible value of NN.

Show solution

Let's apply the totient formula for N=pkN = p^k.

ϕ(N)=pk(1−1p)=pk(p−1p)=pk−1(p−1)\phi(N) = p^k \left(1 - \frac{1}{p}\right) = p^k \left(\frac{p - 1}{p}\right) = p^{k-1}(p - 1).

We are given ϕ(N)=40\phi(N) = 40. So, pk−1(p−1)=40p^{k-1}(p - 1) = 40.

We need to find a prime pp such that (p−1)(p-1) is a factor of 40, and 40/(p−1)40 / (p-1) is a power of pp.

Let's test primes:

  • If p=2p = 2: 2k−1(2−1)=40  ⟹  2k−1=402^{k-1}(2 - 1) = 40 \implies 2^{k-1} = 40. But 40 is not a power of 2. Reject.

  • If p=3p = 3: 3k−1(3−1)=40  ⟹  3k−1×2=40  ⟹  3k−1=203^{k-1}(3 - 1) = 40 \implies 3^{k-1} \times 2 = 40 \implies 3^{k-1} = 20. Not a power of 3. Reject.

  • If p=5p = 5: 5k−1(5−1)=40  ⟹  5k−1×4=40  ⟹  5k−1=105^{k-1}(5 - 1) = 40 \implies 5^{k-1} \times 4 = 40 \implies 5^{k-1} = 10. Not a power of 5. Reject.

  • If p=41p = 41: 41k−1(41−1)=40  ⟹  41k−1×40=40  ⟹  41k−1=141^{k-1}(41 - 1) = 40 \implies 41^{k-1} \times 40 = 40 \implies 41^{k-1} = 1. This means k−1=0k-1 = 0, so k=1k = 1.

So p=41p=41 and k=1k=1 works.

N=411=41N = 41^1 = 41.

Indeed, 41 is prime, so ϕ(41)=40\phi(41) = 40.

The smallest (and only) value is N=41N = 41.

Takeaway: The equation phi(p^k) = p^(k-1) (p-1) is powerful for reverse-engineering unknown numbers from their totient value.

Nested Totients

Calculate the value of ϕ(ϕ(250))\phi(\phi(250)).

Show solution

This is a two-step process.

Step 1: Find ϕ(250)\phi(250)

250=2×125=21×53250 = 2 \times 125 = 2^1 \times 5^3.

ϕ(250)=250×(1−12)×(1−15)\phi(250) = 250 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{5}\right)

=250×12×45= 250 \times \frac{1}{2} \times \frac{4}{5}

=250×410=100= 250 \times \frac{4}{10} = 100.

So, the problem becomes finding ϕ(100)\phi(100).

Step 2: Find ϕ(100)\phi(100)

100=22×52100 = 2^2 \times 5^2.

ϕ(100)=100×(1−12)×(1−15)\phi(100) = 100 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{5}\right)

=100×12×45= 100 \times \frac{1}{2} \times \frac{4}{5}

=100×410=40= 100 \times \frac{4}{10} = 40.

The final answer is 40.

Takeaway: Nested functions just require inside-out sequential calculation. Factorize afresh at each new step.

Two Co-prime Factors Revisit

In how many ways can 47254725 be written as the product of two co-prime integers?

Show solution

Let's prime factorize 4725.

47254725 ends in 25, so it's divisible by 25.

4725/25=1894725 / 25 = 189.

189189 is 9×21=9×3×7=33×79 \times 21 = 9 \times 3 \times 7 = 3^3 \times 7.

So, 4725=33×52×714725 = 3^3 \times 5^2 \times 7^1.

The number of distinct prime factors k=3k = 3 (which are 3, 5, and 7).

The number of ways to express NN as a product of two co-prime factors is always 2k−12^{k-1}.

Ways =23−1=22=4= 2^{3-1} = 2^2 = 4.

(We don't need to calculate ϕ(4725)\phi(4725) for this specific product-splitting question!).

Takeaway: Don't confuse 'number of co-primes less than N' with 'expressing N as a product of two co-primes'. The latter relies strictly on the number of distinct prime bases, 2^(k-1).

Practice questions

Question 1 · CAT Level

For how many positive integers n≤100n \le 100 is Euler’s totient value ϕ(n)\phi(n) an integral power of 22 (i.e., ϕ(n)=2k\phi(n) = 2^k for some integer k≥0k \ge 0)?

  1. A

    22

  2. B

    24

  3. C

    26

  4. D

    28

Show answer and explanation

Answer: (C) 26

For ϕ(n)=n∏p∣np−1p=∏piai−1(pi−1)\phi(n) = n \prod_{p|n} \frac{p-1}{p} = \prod p_i^{a_i - 1}(p_i - 1) to be a power of 22, every odd prime factor pip_i must satisfy two conditions:

1)1) ai=1a_i = 1 (since if ai≥2a_i \ge 2, the factor piai−1p_i^{a_i - 1} is an odd prime >1> 1).

2)2) pi−1p_i - 1 must be a power of 22, which means pip_i must be a Fermat prime. The only Fermat primes ≤100\le 100 are 3,5,3, 5, and 1717.

Thus, nn must be of the form 2a×3b1×5b2×17b32^a \times 3^{b_1} \times 5^{b_2} \times 17^{b_3} where b1,b2,b3∈{0,1}b_1, b_2, b_3 \in \{0, 1\}.

Counting integers ≤100\le 100: powers of 22 give 77 values (202^0 to 262^6); products with 33 give 66; with 55 give 55; with 1717 give 33; with 1515 give 33; with 5151 gives 11; with 8585 gives 11.

Summing these disjoint cases: 7+6+5+3+3+1+1=267 + 6 + 5 + 3 + 3 + 1 + 1 = 26 integers.

Question 2 · CAT Level

How many positive integers n≤1200n \le 1200 are relatively prime to 12001200 and have their units digit equal to 77?

  1. A

    60

  2. B

    72

  3. C

    80

  4. D

    96

Show answer and explanation

Answer: (C) 80

The prime factorisation of 12001200 is 24×31×522^4 \times 3^1 \times 5^2, so gcd⁡(n,1200)=1\gcd(n, 1200) = 1 requires nn not to be divisible by 2,3,2, 3, or 55.

A number with units digit 77 is of the form n=10k+7n = 10k + 7, which is automatically not divisible by 22 or 55.

Thus, we only require 10k+7≢0(mod3)10k + 7 \not\equiv 0 \pmod 3, which reduces to k+1≢0(mod3)k + 1 \not\equiv 0 \pmod 3, so k≢2(mod3)k \not\equiv 2 \pmod 3.

Consider blocks of length lcm(10,3)=30\text{lcm}(10, 3) = 30. In each block of 3030, numbers ending in 77 are 10k+710k+7 for k∈{0,1,2}k \in \{0, 1, 2\}, namely {7,17,27}\{7, 17, 27\}.

Among these, 2727 is divisible by 33, while 77 and 1717 are not, giving exactly 22 valid integers per block of 3030.

Since 1200/30=401200 / 30 = 40 complete blocks exist up to 12001200, the total number of such integers is 40×2=8040 \times 2 = 80.

Question 3 · CAT Level

How many positive integers nn satisfy the equation ϕ(n)=20\phi(n) = 20, where ϕ\phi denotes Euler’s totient function?

  1. A

    3

  2. B

    4

  3. C

    5

  4. D

    6

Show answer and explanation

Answer: (C) 5

If prime p∣np | n, then (p−1)∣ϕ(n)=20(p-1) | \phi(n) = 20. Divisors of 2020 are {1,2,4,5,10,20}\{1, 2, 4, 5, 10, 20\}, so possible prime factors of nn are p∈{2,3,5,11}p \in \{2, 3, 5, 11\}.

If 11∣n11 | n, then since 112∤n11^2 \nmid n, ϕ(n)=ϕ(11)ϕ(m)=10ϕ(m)=20  ⟹  ϕ(m)=2\phi(n) = \phi(11) \phi(m) = 10 \phi(m) = 20 \implies \phi(m) = 2 with gcd⁡(m,11)=1\gcd(m, 11) = 1.

The solutions to ϕ(m)=2\phi(m) = 2 are m∈{3,4,6}m \in \{3, 4, 6\}, yielding n∈{33,44,66}n \in \{33, 44, 66\}.

If 11∤n11 \nmid n, primes dividing nn can only be {2,3,5}\{2, 3, 5\}. To have 5∣ϕ(n)5 | \phi(n), we must have 52∣n5^2 | n, so n=52m=25mn = 5^2 m = 25m.

Then ϕ(n)=ϕ(25)ϕ(m)=20ϕ(m)=20  ⟹  ϕ(m)=1\phi(n) = \phi(25) \phi(m) = 20 \phi(m) = 20 \implies \phi(m) = 1 with gcd⁡(m,5)=1\gcd(m, 5) = 1.

This yields m∈{1,2}m \in \{1, 2\}, giving n∈{25,50}n \in \{25, 50\}.

No other combinations exist, giving exactly 55 solutions: n∈{25,33,44,50,66}n \in \{25, 33, 44, 50, 66\}.

Question 4 · CAT Level

How many pairs of positive integers (x,y)(x, y) satisfy gcd⁡(x,y)=15\gcd(x, y) = 15, x<yx < y, and x+y=3150x + y = 3150?

  1. A

    20

  2. B

    24

  3. C

    28

  4. D

    32

Show answer and explanation

Answer: (B) 24

Let x=15ax = 15a and y=15by = 15b where gcd⁡(a,b)=1\gcd(a, b) = 1 and a<ba < b.

Substituting into the equation gives 15a+15b=3150  ⟹  a+b=21015a + 15b = 3150 \implies a + b = 210.

Notice that gcd⁡(a,b)=1  ⟺  gcd⁡(a,a+b)=1  ⟺  gcd⁡(a,210)=1\gcd(a, b) = 1 \iff \gcd(a, a+b) = 1 \iff \gcd(a, 210) = 1.

Furthermore, each valid a<105a < 105 pairs uniquely with b=210−a>105b = 210 - a > 105, which also satisfies gcd⁡(210−a,210)=1\gcd(210 - a, 210) = 1.

By symmetry, the number of such pairs (a,b)(a, b) is exactly ϕ(210)2\frac{\phi(210)}{2}.

Factoring 210=2×3×5×7210 = 2 \times 3 \times 5 \times 7, we obtain ϕ(210)=210(1−12)(1−13)(1−15)(1−17)=48\phi(210) = 210 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{5}\right)\left(1 - \frac{1}{7}\right) = 48.

Hence, the number of valid pairs is 482=24\frac{48}{2} = 24.

Question 5 · CAT Level

How many three-digit positive integers NN have the property that the ratio Nϕ(N)\frac{N}{\phi(N)} is an integer, where ϕ(N)\phi(N) is Euler’s totient function?

  1. A

    15

  2. B

    18

  3. C

    21

  4. D

    24

Show answer and explanation

Answer: (B) 18

The ratio is given by Nϕ(N)=∏p∣Npp−1\frac{N}{\phi(N)} = \prod_{p | N} \frac{p}{p-1}.

If pkp_k is the largest prime dividing NN, pkp_k cannot divide any pi−1p_i - 1 since pi−1<pkp_i - 1 < p_k.

Thus ∏(pi−1)\prod (p_i - 1) can divide prodpiprod p_i only if the prime factors of NN are restricted to {2}\{2\} or {2,3}\{2, 3\}.

If the prime factors are only {2}\{2\}, Nϕ(N)=2\frac{N}{\phi(N)} = 2. In three digits, powers 2k∈[100,999]2^k \in [100, 999] are 27=128,28=256,29=5122^7=128, 2^8=256, 2^9=512 (33 numbers).

If the prime factors are {2,3}\{2, 3\}, Nϕ(N)=21×32=3\frac{N}{\phi(N)} = \frac{2}{1} \times \frac{3}{2} = 3. We count N=2a3bN = 2^a 3^b with a,b≥1a, b \ge 1 in [100,999][100, 999].

Listing by powers of 33: for 313^1: 2a∈[34,333]  ⟹  a∈{6,7,8}2^a \in [34, 333] \implies a \in \{6, 7, 8\} (33); for 323^2: 2a∈[12,111]  ⟹  a∈{4,5,6}2^a \in [12, 111] \implies a \in \{4, 5, 6\} (33);

for 333^3: 2a∈[4,37]  ⟹  a∈{2,3,4,5}2^a \in [4, 37] \implies a \in \{2, 3, 4, 5\} (44); for 343^4: 2a∈[2,12]  ⟹  a∈{1,2,3}2^a \in [2, 12] \implies a \in \{1, 2, 3\} (33); for 353^5: 2a∈[1,4]  ⟹  a∈{1,2}2^a \in [1, 4] \implies a \in \{1, 2\} (22).

This yields 3+3+4+3+2=153 + 3 + 4 + 3 + 2 = 15 integers of the form 2a3b2^a 3^b. Total =3+15=18= 3 + 15 = 18 integers.

Study this concept with interactive practice in PrepSoc.

Open the concept library