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
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);
}
}
#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;
}
}
What is wrong in this code? I am a beginner I C coding and I was trying to do it by my own and the consequence is not fruitful.
/*Phi function*/
#include
int main()
{
int i,n,k,r,a;
int gcd(int a,int b);
printf(“—————————————————-”);
printf(“\nEnter a positive integer: “);
scanf(“%d”,&a);
n=a;
k=0;
for(i=1;i<n;i++)
{
r=gcd(n,i);
if(r==1)
k=k+1;
else
continue;
}
printf("\nphi(%d)=%d\n",a,k);
printf("—————————————————-");
return 0;
}
int gcd(int a,int b)
{
int r;
while(r!=0)
{
r=a%b;
a=b;
b=r;
}
return a;
}
showing phi value of every integer is 1.