Eulers Totient Function

By Sudheer S

Introduction

Continuing with the series of posts on number theory and cryptograpy, let us take a look at the Euler’s Totient Function.

Euler’s Totient Function, denoted as ϕ(n), is a function that counts the number of positive integers less than or equal to n that are relatively prime to n. Two numbers are relatively prime (or coprime) if their greatest common divisor (GCD) is 1.

Prerequisites

  • Familarity with the Inclusion-Exclusion principle
  • Familarity with the modular arithmetic

Definition

For any positive integer n, the Euler’s Totient Function ϕ(n) is defined as:

ϕ(n) = Number of integers k such that 1 ≤ k ≤ n and gcd⁡(k,n)=1

Example Calculations

n=1:

The only positive integer less than or equal to 1 is 1 itself, and gcd⁡(1,1)=1.

Therefore, ϕ(1)=1.

n=5:

The integers less than or equal to 5 are 1, 2, 3, 4, and 5.

The GCDs are:

gcd⁡(1,5)=1gcd(1,5)=1 gcd⁡(2,5)=1gcd(2,5)=1 gcd⁡(3,5)=1gcd(3,5)=1 gcd⁡(4,5)=1gcd(4,5)=1 gcd⁡(5,5)=5gcd(5,5)=5

So, the integers 1, 2, 3, and 4 are relatively prime to 5.

Therefore, ϕ(5)=4.

n=12:

The integers less than or equal to 12 are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12. After calculating, the integers relatively prime to 12 are 1, 5, 7, and 11.

Therefore, ϕ(12)=4.

Proof

To prove the formula for Euler’s Totient Function ϕ(n), we’ll consider the general case where n is a product of distinct prime factors.

Theorem

If

$$ n = p_1^{k1} \times p_2^{k2} \times p_m^{km} $$

where p1,p2,…,pm​ are distinct primes, then:

$$ \phi(n) = n \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \times \ldots \times \left(1 - \frac{1}{p_m}\right) $$

Step 1: Counting numbers not divisible by a prime factor

Let

$$ n = p_1^{k1} \times p_2^{k2} \times p_m^{km} $$

and consider the total number of integers from 1 to n, which is n itself.

The function ϕ(n) counts the number of integers less than or equal to n that are relatively prime to n. To find ϕ(n), we can subtract the numbers that are divisible by any of the prime factors p1,p2,…,pm​ from the total count n.

Step 2: Applying the Principle of Inclusion-Exclusion The number of integers less than or equal to n divisible by a prime pi​ is n/pi​. The number of integers divisible by both pi​ and pj​ (for distinct i and j) is n/(pi×pj)​, and so on.

By the Principle of Inclusion-Exclusion (PIE), the number of integers divisible by at least one of the primes p1,p2,…,pm​ is:

$$ ( \frac{n}{p_1} + \frac{n}{p_2}+ ... + \frac{n}{p_m} ) − ( \frac{n}{p_1 \times p_2} + ... ) + ... + (-1)^{m+1} \times \frac{n}{p_1 \times p_2 ... \times p_m} $$

Simplifying, this becomes:

$$ n ( \sum_{i=1}^{m} \frac{1}{p_i} - \sum_{1 \le i < j \le m} \frac{1}{p_i p_j} + ... + (-1)^{m+1} \frac{1}{p_1 p_2 ... p_m} )$$

Step 3: Subtracting from the Total Count

Subtracting this from the total count n, the number of integers relatively prime to n is:

$$ \phi{(n)} = n \times ( 1 - (\frac{1}{p_1} + \frac{1}{p_2} + ... + \frac{1}{p_m} ) + (\frac{1}{p_1 p_2} + ... ) - ... + (-1)^{m} \frac{1}{p_1 p_2 ... p_m}) $$

The above expression simplifies into the product form:

Special Cases

When n is a prime p:

$$ \phi{(p)} = p \times (1 - \frac{1}{p}) = p \times \frac{p-1}{p} = p - 1$$

This makes sense, as the only number not coprime with p is p itself.

When n=p1×p2: For two distinct primes p1​ and p2​, the formula gives:

$$ \phi{(p_1 \times p_2)} = (p_1 \times p_2 ) \times (1 - \frac{1}{p_1} ) \times (1 - \frac{1}{p_2}) = (p_1 - 1)(p_2 - 1) $$

This concludes the proof of the general formula for Euler’s Totient Function.

Python Program To Implement The Euler’s Totient Function

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def find_prime_factors(n):
    factors = set()
    divisor = 2
    while n > 1:
        if n % divisor == 0:
            factors.add(divisor)
            while n % divisor == 0:
                n //= divisor
        divisor += 1
    return factors

def euler_totient(n):
    if n == 1:
        return 1
    prime_factors = find_prime_factors(n)
    result = n
    for p in prime_factors:
        result *= (1 - 1/p)
    return int(result)

# Example usage:
n = 36  # You can change this value to any positive integer
print(f"Euler's Totient function for {n} is: {euler_totient(n)}")

References