Euler's totient function (pronounced to rhyme with 'quotient') is a unary function on positive integers. It is written as a lowercase phi letter, φ. φ(n) is the number of positive integers less than n and relatively prime to n (including 1).

The totient of a prime p is always (p - 1), because every positive integer less than p is prime relative to p. The totient of the power of a prime, n = pi, is (n - p(i - 1)) = (pi - p(i - 1)) = (n * (1 - (1 / p))) because there are p(i - 1) positive integers less than n which have a factor of p, and so are not relatively prime to n. The totient of the product of a set of relatively prime numbers is equal to the product of the totients of each element. This can be seen by taking any pair of relatively prime numbers, x and y. There is a set of positive integers, x1, x2, …, xa which are all prime relative to x, and φ(x) = a. Likewise there is a set of numbers y1, y2, …, yb which are all prime relative to y, and φ(y) = b. Consider the set of numbers {(xi * y) + (yj : 0 < i ≤ φ(x); 0 < j ≤ φ(y)}. It is easy to see that the size of the set is (φ(x) * φ(y)), and that each element of the set is less than (x * y). It is not so easy to see that each element is prime relative to (x * y), and that every positive integer less than (x * y) and prime relative to it is included in the set, but it is true. So the general formula for φ, using Eindhoven notation, is:
φ(n) = n * (* : (p is prime) ∧ (p is a factor of n) : 1 - (1 / p))

Log in or register to write something here or to contact authors.