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.

References:
http://en.wikipedia.org/wiki/Euler%27s_totient_function

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);
    }
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation