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

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

  2. #include
    int hcf(int,int);
    int tota(int ,int);
    int main()
    {int a,s;
    printf(“ENTER A NO TO FIND ITS TOTATIVE\n”);
    scanf(“%d”,&a);
    s=tota(1,a);
    printf(“TOTATIVE OF NO IS =%d”,s);
    return 0;

    }
    int tota(int a ,int b)
    {int t,l;
    if(a>b)
    return 0;
    else{

    t=tota(a+1,b);
    l=hcf(a,b);
    if(l==1)
    return (1+t);
    else
    return t;

    }
    }

    int hcf(int a,int b)
    {int l;
    if(a>b)
    {
    int t;
    t=a;
    a=b;
    b=t;
    }
    if((b%a)==0)
    return a;
    else
    {
    l=hcf(b%a,a);
    return l;
    }

    }

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