# Euler Totient Function

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)).

```
- 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.

# Number Theoretic Algorithms – Factorization

In the following series of posts, I will write about some of the number theoretic algorithms that one encounters in most of competitive programming. These are fundamental algorithms which most computer scientist should know.

In this post I will post an algorithm and a corresponding JAVA code to perform prime factorization of a give number.

The algorithm to perform prime factorization is a very trivial algorithm and mostly encountered by everyone atleast once in their high school.

```
- Iterate for i from 2 to sqrt(n)
- While i|n, divide n by i. Report i as a prime factor of n
- After the iteration of i from 2 to sqrt(n),
if n is a number greater than 1, report that also as a prime factor

```

The key observation is that, this algorithm runs in O(square root (n) ).

We are able to iterate only upto sqrt(n) since, we can claim one of the following:

1) n is a prime number

or

2) If n has a prime factor p greater than sqrt(n), then there exists a corresponding prime factor p’ lesser than or equal to sqrt(n), such that

p*p’ = n

If (1) doesn’t hold, it implies that n is a composite number. And Let us assume (2) doesnt hold.

This implies for a prime p such that p|n, there is no p’ <= sqrt(n) such that p’|n.

In particular n/p > sqrt(n) . And since p>sqrt(n)

=> 1/p < 1/sqrt(n)

=> n/p <n/sqrt(n) = sqrt(n).

This provides the contradiction. Hence the claim above proves the correctness of the algorithm.

Link to a JAVA implementation of the above factorization.