Euler Phi's Function

Introduction

Euler’s Phi function (also known as totient function, denoted by $\phi$) is a function on natural numbers that gives the count of positive integers co-prime with the corresponding natural number, i.e., the numbers whose GCD (Greatest Common Divisor) with N is 1. So we can say the following:

$\phi$(1) = 1 because gcd(1, 1) is 1.

$\phi$(2) = 1 because gcd(1, 2) is 1, but gcd(2, 2) is 2.

$\phi$(3) = 2 because gcd(1, 3) is 1 and gcd(2, 3) is 1.

$\phi$(4) = 2 because gcd(1, 4) is 1 and gcd(3, 4) is 1.

$\phi$(5) = 4 because gcd(1, 5) is 1, gcd(2, 5) is 1, gcd(3, 5) is 1 and gcd(4, 5) is 1.

$\phi$(6) = 2 because gcd(1, 6) is 1 and gcd(5, 6) is 1.

Solution

The value $\phi$(n) can be obtained by Euler’s formula. It basically says that the value of $\phi$(n) is equal to n multiplied by product of (1 – $\frac{1}{p}$) for all prime factors p of n. For example, the value of $\phi$(6) = 6 * (1-$\frac{1}{2}$) * (1 – $\frac{1}{3}$) = 2.

Now, let us look at the implementation of this function.