Euler's Totient Function

Euler's Totient Function

In number theory, Euler's totient or phi function, φ(n) is an arithmetic function that counts the number of positive integers less than or equal to n that are relatively prime to n. That is, if n is a positive integer, then φ(n) is the number of integers k in the range 1 ≤ k ≤ n for which gcd(n, k) = 1. The totient function is a multiplicative function, meaning that if two numbers m and n are relatively prime (to each other), then φ(mn) = φ(m)φ(n).

For example let n = 9. Then gcd(9, 3) = gcd(9, 6) = 3 and gcd(9, 9) = 9. The other six numbers in the range 1 ≤ k ≤ 9, that is, 1, 2, 4, 5, 7 and 8, are relatively prime to 9. Therefore, φ(9) = 6. As another example, φ(1) = 1 since gcd(1, 1) = 1.

The totient function is important mainly because it gives the order of the multiplicative group of integers modulo n (the group of units of the ring ). See Euler's theorem.
The totient function also plays a key role in the definition of the RSA encryption system.