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