# Euler’s Totient Function

Euler Function:

In number theory, Euler’s totient function (or Euler’s phi function), denoted as φ(n) or ϕ(n), is an arithmetic function that counts the positive integers less than or equal to n that are relatively prime to n , i.e., the numbers whose GCD (Greatest Common Divisor) with n is 1. (These integers are sometimes referred to as totatives of n.)

Example:

Φ(1) = 1
gcd(1, 1) is 1

Φ(2) = 1
gcd(1, 2) is 1, but gcd(2, 2) is 2.

Φ(3) = 2
gcd(1, 3) is 1 and gcd(2, 3) is 1

Φ(4) = 2
gcd(1, 4) is 1 and gcd(3, 4) is 1

Φ(5) = 4
gcd(1, 5) is 1, gcd(2, 5) is 1,
gcd(3, 5) is 1 and gcd(4, 5) is 1

Φ(6) = 2
gcd(1, 6) is 1 and gcd(5, 6) is 1,

Properties for Euler Function:

1) For a prime number p, Φ(p) is p-1. For example Φ(5) is 4, Φ(7) is 6 and Φ(13) is 12. This is obvious, gcd of all numbers from 1 to p-1 will be 1 because p is a prime.
2) For two numbers a and b, if gcd(a, b) is 1, then Φ(ab) = Φ(a) * Φ(b). For example Φ(5) is 4 and Φ(6) is 2, so Φ(30) must be 8 as 5 and 6 are relatively prime.
3) For any two prime numbers p and q, Φ(pq) = (p-1)*(q-1). This property is used in RSA algorithm.
4) If p is a prime number, then Φ(pk) = pk – pk-1. This can be proved using Euler’s product formula.

Implementation:
The simplest code that calculates the Euler function, factoring the number of elementary method :

```int phi (int n) {
int result = n;
for (int i=2; i*i<=n; ++i)
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
if (n > 1)
result -= result / n;
return result;
}
```

A key place for the calculation of the Euler function – is to find the factorization of numbers n.

### One Thought on “Euler’s Totient Function”

1. madHEYsia on October 12, 2016 at 4:38 pm said:

Java code: O(nlogn)

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static void main (String[] args)
{
Scanner in = new Scanner(System.in);
int n=in.nextInt();
int sum=0;
for(int i=1;i<n;++i)
if(gcd(i,n) ==1)++sum;
System.out.println(sum);
}
public static int gcd(int a, int b)
{
if(a==0) return b;
return gcd(b%a,a);
}
}