Euler’s Totient Function (denoted as φ(n)) is used to determine the number of positive integers less than n that are co-prime to n. Co-prime numbers are numbers that have no common factor with n other than 1.

The formula for Euler’s Totient Function, when n is a product of distinct prime numbers, is:

φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)

This formula is derived based on principles of probability and basic properties of prime numbers. Let’s break it down:

1. Identifying Reducible Fractions: Consider a fraction with n as the denominator and a number a (between 1 and n) as the numerator. This fraction is reducible if and only if a and n share a common factor other than 1. In other words, it is reducible if a is not co-prime with n.

2. Excluding Fractions Reducible by a Prime: If n is divisible by a prime number p, then 1/p of the numbers from 1 to n are also divisible by p (because every pth number will be divisible by p). This means 1/p of the fractions with n in the denominator are reducible by p.

3. Accounting for Multiple Prime Factors: If n has multiple distinct prime factors, we need to subtract the fractions of n that are reducible by each of these primes. But doing this might lead us to subtract some fractions more than once (those reducible by the least common multiple of two primes). So, we need to add back these fractions. This is based on the principle of inclusion and exclusion, a fundamental principle in combinatorics.

4. Principle of Inclusion an Exclusion The principle of inclusion and exclusion is a counting principle in combinatorics. Here’s a simplified explanation of that principle:

   • If you want to count the total number of objects in two sets, you add the number of objects in each set.
   • But, if some objects belong to both sets, you’ve counted them twice. To correct this, you subtract the number of objects that belong to both sets.

So how does this apply to Euler’s totient function?

Let’s take an example where n = p*q and p and q are distinct primes. We want to find φ(n), which is the count of numbers less than n that are co-prime to n.

1. Start with the number n. This is the total count of numbers less than n.
2. From this, subtract the count of numbers less than n that are divisible by p (which is n/p). We subtract these because these numbers share a factor with n and hence are not co-prime to n.
3. Also subtract the count of numbers less than n that are divisible by q (which is n/q).
4. But, we’ve subtracted too much! Some numbers are divisible by both p and q (specifically, the multiples of p*q ), and we’ve subtracted these numbers twice. So, to correct this, we add back the count of numbers less than n that are divisible by p*q (which is n/(p*q) ).

Therefore, applying the principle of inclusion and exclusion, the total count of numbers less than n that are co-prime to n is:

φ(n) = n - n/p - n/q + n/(p*q)

We can factor out n from each term to get Euler’s totient function formula:

φ(n) = n * (1 - 1/p) * (1 - 1/q)

This is the way the formula is derived when n has two distinct prime factors. The process is similar for numbers with more than two distinct prime factors.

References:

• Euler’s Totient Function
• Inclusion-Exclusion Principle