Euler Totient Function

Hello Coders,

I am writing this blogpost after a very long time. I am really sorry for that. :(

This blogpost is related to a mathematical topic which is Euler Totient function and there are many problems which are based on this mathematical concept.

What is Euler Totient Function?
It is a function which takes the input an integer n and in return it gives the number of relatively prime numbers to n which are smaller than it.



What is a relatively prime number?
A number X is relatively prime to another number say Y if GCD(X, Y) is 1. Here GCD(X, Y) is greatest common factor of X and Y.

Let's take some examples and find their relatively smaller prime numbers(RSPN):
N = 2,
RSPN(2) = {1}
--------------------
N = 3
RSPN(3) =  {1, 2}
--------------------
N = 4
RSPN(4) = {1, 3}
--------------------
N = 5
RSPN(5) = {1, 2, 3, 4}
--------------------
N = 6
RSPN(6) = {1, 5}

and so on.....

Now let's see how euler totient give the number of relatively prime numbers to N which are smaller than it.

Formula:
EulerTotient(N) = N * (1 - 1/p1) * (1 - 1/p2) * (1 - 1/p3) .........
Note: Here p1, p2, p3.... are the prime factors of N.

Let's validate the formula now:
EulerTotient(6) = 6 * (1 - 1 / 2) * (1 - 1 / 3) = 6 * (1/2) * (2/3) = 2
Wow! You can see that 6 has only 2 RSPN which are {1, 5}.

Similarly you can test for other numbers also.

Proof of the formula:
For proof you can visit Wikipedia Page. 
Proof is very simple and it uses multiplicative property of Euler Totient Function, which means that: EulerTotient(X*Y) = EulerTotient(X) * EulerTotient(Y).

C++ Implementation of Euler Totient Function:

	int N; // Given Number
	vector<int> primes; // contains all the prime factors of N
	int phi(int N, vector<int>& primes){
	int ret = N;
	for(int i = 0 ; i < primes.size() ; i++){
	ret = ret - ret / primes[i];
	}
	return ret;
	}

view raw EulerTotientFunction.cpp hosted with ❤ by GitHub

Problems for practice:
Problem1 
Problem2 
Problem3 
You can see the solutions for above 3 problems on my another blog: Link

Thanks for reading this post!
Happy Coding!!


PS: You can comment if you find anything wrong or you have any doubt regarding this topic