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. :slight_smile:

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

For a detailed tutorial about it check this link.

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