# Euler's Totient Function Calculator

φ(n)

*(Totient of n):*

Euler's Totient Theorem

public static int totient(int num){ //euler's totient function calculator. returns totient

int count=0;

for(int a=1;a<num;a++){ //definition of totient: the amount of numbers less than num coprime to it

if(GCD(num,a)==1){ //coprime

count++;

}

}

return(count);

}

public static int GCD(int a, int b){ //faster euclidean algorithm-see GCD for explanation

int temp;

if(a<b){

temp=a;

a=b;

b=temp;

}

if(a%b==0){

return(b);

}

return(GCD(a%b,b));

}

The Euler Totient function, denoted phi(n) or totient(n), is the amount of numbers less than n relatively prime, or coprime to it. It has many uses, particularly Euler's Totient Theorem that for all

int count=0;

for(int a=1;a<num;a++){ //definition of totient: the amount of numbers less than num coprime to it

if(GCD(num,a)==1){ //coprime

count++;

}

}

return(count);

}

public static int GCD(int a, int b){ //faster euclidean algorithm-see GCD for explanation

int temp;

if(a<b){

temp=a;

a=b;

b=temp;

}

if(a%b==0){

return(b);

}

return(GCD(a%b,b));

}

The Euler Totient function, denoted phi(n) or totient(n), is the amount of numbers less than n relatively prime, or coprime to it. It has many uses, particularly Euler's Totient Theorem that for all

*a*coprime to*n*. There is also other ways to calculate totient(n), but they were slower than my implementation. It works by looping through 2->num, because 1 is always relatively prime to all numbers, we account for that and start at 2. We check if GCD(num,i) is 1, which shows they are relatively prime. The Euclidean algorithm provides a quick recursive way to do this (see GCD page), and I sped it up considerably by implementing the fast Euclidean algorithm. The Javascript totient calculator implementation is above, using the exact same Java algorithm.Provided by website-hit-counters.com site. |