On this page
If you are studying for JEE Advanced or a maths olympiad, you often need to find how many integers share no common factors with a given number. This sounds like a tedious counting problem, but it has a direct mathematical shortcut. Knowing how to count these numbers quickly helps you solve probability questions and complex algebraic proofs without writing out every possibility by hand.
What does coprime to n mean?
Two positive integers are coprime (or relatively prime) if their greatest common divisor (GCD) is 1. This means they share no prime factors. For example, 8 and 15 are coprime because the prime factor of 8 is 2, while the prime factors of 15 are 3 and 5. The only factor they share is 1. Because their only common divisor is 1, a fraction like 8/15 cannot be simplified any further.
Another important rule to remember is that consecutive integers are always coprime. For instance, 14 and 15 are coprime, just as 99 and 100 are. They will never share a prime factor. This small trick can save you precious minutes during competitive exams when you need to quickly evaluate whether two adjacent numbers have any common divisors.
What is Euler's totient function?
To find the number of positive integers up to n that are relatively prime to n, mathematicians use Euler's totient function, written as φ(n) (the Greek letter phi). The function was introduced by Leonhard Euler in 1763, while the standard notation φ(n) was added by Carl Friedrich Gauss in 1801 (Wikipedia). This function has become a cornerstone of modern number theory and cryptography, including the RSA encryption algorithm that secures internet communications today.
The calculation is based on Euler's product formula. Instead of testing every number up to n, you break n into its distinct prime factors. For every unique prime factor p, you multiply n by the fraction (1 - 1/p).
The formula is written as: φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ...
It only depends on the unique prime factors of n. If the same prime appears multiple times in the prime factorisation (like 2³), you only use it once in the product formula. The power of the prime does not change the fractions in the brackets, because the function only checks whether a prime factor is present, not how many times it divides the number.
If you are revising number theory and find gaps in your understanding of prime factorisation or modular arithmetic, the Fermi Concept Library has every concept in physics, chemistry, biology, mathematics and computing, each with its own lesson and its place in the map.
How does Euler's totient formula work for 36 and 100?
Before you can apply the formula, you need the prime factorisation. If you are not sure where to begin, brushing up on How to check if a number is prime: test only up to √n or exploring The Sieve of Eratosthenes: finding primes interactively are good starting points.
Let's find the number of positive integers coprime to 36.
Find the prime factors of 36. Since 36 = 2² × 3², its distinct prime factors are 2 and 3.
Apply the formula: φ(36) = 36 × (1 - 1/2) × (1 - 1/3)
Simplify the brackets: φ(36) = 36 × (1/2) × (2/3)
Multiply the terms: φ(36) = 36 × (2/6) = 12.
There are exactly 12 positive integers less than 36 that are coprime to 36.
Now, let's calculate φ(100).
The prime factorisation of 100 is 2² × 5². The distinct prime factors are 2 and 5.
Apply the formula: φ(100) = 100 × (1 - 1/2) × (1 - 1/5)
Simplify the brackets: φ(100) = 100 × (1/2) × (4/5)
Multiply the terms: φ(100) = 100 × (4/10) = 40.
There are 40 numbers less than 100 that are coprime to 100. This is much faster than listing all 100 numbers and crossing out the even numbers and multiples of 5.
How do you count coprimes by hand for small n?
For small numbers, you can verify your formula by counting directly. Let's find φ(12) using both methods.
The formula method: Write 12 as a product of its prime factors: 12 = 2² × 3. The unique prime factors are 2 and 3. φ(12) = 12 × (1 - 1/2) × (1 - 1/3) φ(12) = 12 × (1/2) × (2/3) = 4.
The counting method: List all positive integers up to 12: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.
Remove all numbers that share a prime factor with 12 (meaning they are divisible by 2 or 3).
Numbers divisible by 2: 2, 4, 6, 8, 10, 12.
Numbers divisible by 3: 3, 6, 9, 12.
The integers left are 1, 5, 7, and 11. These are the exactly four numbers coprime to 12, confirming our formula's result of 4.
For more advanced applications, totients are often paired with How to find the remainder of large powers: JEE methods to simplify large modulo calculations using Euler's theorem. Once you master the totient function, number theory problems become much more predictable.
