In this post I will explain yet another simple number theoretic function, called the Euler Totient Function. This is a simple function which is used indirectly in many problems in programming contests. The function is denoted as phi(n). phi(n) basically gives the number of integers greater than 0 and lesser than n+1 which are co-prime to the integer n. In other words, it is the cardinality of the set

S = { a: 1<a<n , gcd(a,n) = 1 }. To calculate this function, we will use a straight forward brute force approach. With a simple analysis, we can show

that the running time of this algorithm is O(sqrt(n)).

- Start with an estimate of the totient function as n - Iterate for i from 2 to sqrt(n) - If i | n , we know that all factors of i less than equal to n will have gcd with n as atleast i. Hence, they can never be in the set S. Hence remove them from the result. - While i|n, divide n by i. - After the iteration of i from 2 to sqrt(n), if n is a number greater than 1, remove all its multiples less than n also from the result

The analysis of this code is similar to the analysis for prime factorization. Essentially at the core of the algorithm, we are finding prime factors of n and removing all its multiples. Hence the numbers left are the ones that are co-prime to n.

Hence, both correctness and the running time analysis follows from the prime factorization algorithm.

Link to a java implementation.