Euler's totient function¶
In number theory, Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as φ(n) or ϕ(n), and may also be called Euler's phi function. In other words, it is the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) is equal to 1.Since a number less than or equal to and relatively prime to a given number is called a totative, the totient function phi(n) can be simply defined as the number of totatives of n.
So this was a brief introduction to the concept of Euler's totient function. Now let's try to understand this concept in more details using a simple example
Let's take the example of n = 24 and we are supposed to calculate phi(n) First we need to calculate a list of co-prime numbers less than or equal to n:
1, 5, 7, 11, 13, 17, 19, and 23
this list consist of 8 totatives so phi(n) = phi(24) = 8 Wasn't this simple ? Now let's dive into some properties of phi or the Euler's totient function
1. φ(1) = 1 since for n = 1 the only integer in the range from 1 to n is 1 itself, and gcd(1, 1) = 1 2. For any prime p, phi(p) can be calculated as p-1 phi(p) = p-1 3. Suppose we have a number n = p * q then phi is defined as the product of phi of p and phi of q and d / phi(d) where d is defined as the gcd of p and q phi(pq) = phi(p) * phi(q) * (d/phi(d)) where d = gcd(p,q) 4. For any a and n which are relative primes then a^phi(n) = 1 mod(n)