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` =
`p`^{i}, is
(n - `p`^{(i - 1)}) =
(`p`^{i} -
`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, `x`_{1},
`x`_{2}, …,
`x`_{a} which are all prime relative to
`x`, and φ(`x`) = `a`. Likewise there is a set of numbers
`y`_{1},
`y`_{2}, …,
`y`_{b} which are all prime relative to
`y`, and φ(`y`) = `b`.
Consider the set of numbers {(`x`_{i} * `y`) +
(`y`_{j} : 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`))