 # EULER TOTIENT FUNCTION

Can anyone explain why and where we use Euler Totient Function. Please provide a pseudo-code or a code to compute it.

Thanks in advance. 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. (These integers are sometimes referred to as totatives of n.)

I hope this helps.

1 Like

problem on ETF

on other plateform

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1120

1 Like

Thanks for the help.
Can you suggest some problem statements for practice.

Thanks for the help.

Euler’s Totient Function or phi-function, phi(n). this function count the number of integer between 1 to n which are co-prime with n.

co-prime mean : suppose we have two number x and y. then x and y will be co-prime when there gcd(x, y) = 1 that means x and y this two number have common factor is 1.

phi(12) = 4. How it come 4???

Because, [ 2, 3, 4, 6, 8, 9, 10, 12 ] this eight number have factor with 12 is greater than 1.
Example : gcd(2, 12) = 2
gcd(3, 12) = 3
gcd(4, 12) = 4 …

But [ 1, 5, 7, 11] only this four number have factor with 12 is equal to 1. So phi(12) = 4.

Now we that how can we calculate it by mathematically…(running)

full code and explanation : Full Code explanation

Have a look at this link. It has explainations, code as well as some reference problems
https://cp-algorithms.com/algebra/phi-function.html