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 . He wants to invite all integers less than himself, from to . 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 s and s), he will ban anyone who is even (shares a ) or a multiple of 3 (shares a ).
The guests who actually make it to the party are the "co-primes" of . Their greatest common divisor with 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 (), and successively remove the fraction of people who share prime traits with the King. This elegant counting mechanism is Euler's Totient Function, .
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 and co-prime to it.
-
Ask for the sum of all integers less than 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 as the denominator?" (This is exactly ).
3. Core Concepts, Formulae & Derivations
A. Definition of Co-primes
Two numbers and are co-prime (or relatively prime) if their greatest common divisor . 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
If the prime factorization of is
Then the number of integers less than and co-prime to is given by:
Derivation logic: If (), we start with 12 numbers. Half of them are multiples of 2, so we multiply by . Now 6 numbers remain. One-third of those remaining are multiples of 3, so we multiply by . . The four numbers are 1, 5, 7, 11.
C. Sum of Co-primes
The sum of all integers less than and co-prime to is:
Derivation logic: Co-primes always occur in symmetric pairs that sum to . For , the co-primes are . Notice that and . There are such pairs.
D. Prime Totient
If is a prime number, it shares no factors with anything smaller than itself.
4. Common Pitfalls & Speed Shortcuts
-
Pitfall: Applying the formula to composite bases without prime factorizing first. For , do NOT use . Break 36 down to , then use .
-
Shortcut: If you are asked to find the number of ways can be expressed as a product of two co-prime factors, the answer is always , where is the number of distinct prime factors of . Don't calculate for this specific question!
Formulas
| Euler's Totient phi(N) | |
|---|---|
| Sum of Co-primes to N | |
| Totient of a Prime |
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 are co-prime to ?
Show solution
This is a direct application of Euler's Totient Function, .
First, find the prime factorization of 120.
.
The distinct prime factors are , and .
Apply the formula:
Simplify the fraction multiplication:
.
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 cannot be further simplified?
Show solution
A proper fraction is of the form where .
For the fraction to be irreducible (in its simplest form), the numerator and the denominator must not share any common factors other than 1.
This means must be co-prime to .
So, the question is simply asking for .
Prime factorize 90:
.
.
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 that are co-prime to .
Show solution
We use the formula for the sum of co-primes: .
First, find .
.
.
Now, calculate the sum:
.
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 and where is a prime, find the smallest possible value of .
Show solution
Let's apply the totient formula for .
.
We are given . So, .
We need to find a prime such that is a factor of 40, and is a power of .
Let's test primes:
-
If : . But 40 is not a power of 2. Reject.
-
If : . Not a power of 3. Reject.
-
If : . Not a power of 5. Reject.
-
If : . This means , so .
So and works.
.
Indeed, 41 is prime, so .
The smallest (and only) value is .
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 .
Show solution
This is a two-step process.
Step 1: Find
.
.
So, the problem becomes finding .
Step 2: Find
.
.
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 be written as the product of two co-prime integers?
Show solution
Let's prime factorize 4725.
ends in 25, so it's divisible by 25.
.
is .
So, .
The number of distinct prime factors (which are 3, 5, and 7).
The number of ways to express as a product of two co-prime factors is always .
Ways .
(We don't need to calculate 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 is Euler’s totient value an integral power of (i.e., for some integer )?
Show answer and explanation
Answer: (C) 26
For to be a power of , every odd prime factor must satisfy two conditions:
(since if , the factor is an odd prime ).
must be a power of , which means must be a Fermat prime. The only Fermat primes are and .
Thus, must be of the form where .
Counting integers : powers of give values ( to ); products with give ; with give ; with give ; with give ; with gives ; with gives .
Summing these disjoint cases: integers.
Question 2 · CAT Level
How many positive integers are relatively prime to and have their units digit equal to ?
Show answer and explanation
Answer: (C) 80
The prime factorisation of is , so requires not to be divisible by or .
A number with units digit is of the form , which is automatically not divisible by or .
Thus, we only require , which reduces to , so .
Consider blocks of length . In each block of , numbers ending in are for , namely .
Among these, is divisible by , while and are not, giving exactly valid integers per block of .
Since complete blocks exist up to , the total number of such integers is .
Question 3 · CAT Level
How many positive integers satisfy the equation , where denotes Euler’s totient function?
Show answer and explanation
Answer: (C) 5
If prime , then . Divisors of are , so possible prime factors of are .
If , then since , with .
The solutions to are , yielding .
If , primes dividing can only be . To have , we must have , so .
Then with .
This yields , giving .
No other combinations exist, giving exactly solutions: .
Question 4 · CAT Level
How many pairs of positive integers satisfy , , and ?
Show answer and explanation
Answer: (B) 24
Let and where and .
Substituting into the equation gives .
Notice that .
Furthermore, each valid pairs uniquely with , which also satisfies .
By symmetry, the number of such pairs is exactly .
Factoring , we obtain .
Hence, the number of valid pairs is .
Question 5 · CAT Level
How many three-digit positive integers have the property that the ratio is an integer, where is Euler’s totient function?
Show answer and explanation
Answer: (B) 18
The ratio is given by .
If is the largest prime dividing , cannot divide any since .
Thus can divide only if the prime factors of are restricted to or .
If the prime factors are only , . In three digits, powers are ( numbers).
If the prime factors are , . We count with in .
Listing by powers of : for : (); for : ();
for : (); for : (); for : ().
This yields integers of the form . Total integers.
Study this concept with interactive practice in PrepSoc.
Open the concept library