Euler's totient formula, usually represented by the lowercase Greek letter
phi, is defined such that, given an argument *n*, it returns the number of
positive integers, *m*, less than and relatively prime to *n*. Hence

m = totient(n) = (n)

To find the actual expression for (n), let's first
note that, according to the fundamental theorem of arithmetic, any integer *n*
can be written uniquely as a product of prime factors:

n = P p_{i}^{k}i

If *n* is itself prime, then all positive integers less than *n* are
relatively prime to *n*. Hence,

(p) = (p-1) for p prime

If *n* is an integer power, *k*, of a prime number, then the
positive integers less or equal to *n* can be broken into *p*^{(k-1)}
groups of *p* numbers each and, within each group, all but one is
relatively prime to *p*. Hence

(p^{k}) = (p-1)(p^{(k-1)})
for p prime

As an example, consider n = 5^{3} = 125. This list may be broken into
5^{2} = 25 groups of 5 numbers each as follows:

{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15}...{121,122,123,124,125}

Within each group, only the last one shares a factor with n and hence all the
other (*p*-1) are relatively prime to *n*. Notice that we
have included *n* in our initial list, despite the fact that it is
technically not a candidate for final inclusion. However, we are guaranteed to remove it
and hence this causes no error in the end - it just makes the bookkeeping a bit
easier.

Notice that the above arrangement also allows us to see that we can split the
set of the first *p*^{k} positive integers into two sets, those
that are relatively prime to p and those that aren't. The fraction of the
integers that will be in the first set is (*p*-1)/*p* while the
fraction that will be in the second set is 1/*p*. Hence

(p^{k}) = [(p-1)/p](p^{k})
= (p-1)(p^{(k-1)}) for p prime

While, reassuringly, this is consistent with the result previously derived,
it also gives us the leverage needed to determine the totient of an arbitrary
positive integer. Let {*p*_{i}} be the set of *i* prime
factors of *n*. Then the number of integers less than *n* that are
relatively prime to a particular *p*_{i} will be:

# relatively prime to p_{i} = n[(p_{i}-1)/p_{i}]

If we split the set of the first n positive integers into two sets as we did
before, namely those that are and those that are not relatively prime to one of
the prime factors of *n*, (say *p*_{1}), then the above
expression tells us that the set containing the numbers relatively prime to *p*_{1}
is

# relatively prime to p_{1} = n[(p_{1}-1)/p_{1}]

If we now take this set and split it into two sets according to those that
are and those that aren't relatively prime to a different prime factor of *n*,
(say *p*_{1}), the number in this set will be:

# relatively prime to p_{1} and p_{2} = n[(p_{1}-1)/p_{1}][(p_{2}-1)/p_{2}]

Notice that this assertion is based on a pretty subtle claim. For instance,
let's say that *n* has as prime factors 2, 3, 5 and possible others. It is
true that 1/2 of the first n positive integers are relatively prime to 2, that
2/3 are relatively prime to 3, and that 4/5 are relatively prime to 5. But is it
true that exactly 2/3 of the ones that are relatively prime to 2 are also
relatively prime to 3? Is it true that exactly 4/5 of the ones that are
relatively prime to both 2 and 3 are also relatively prime to 5?

If there are only two prime factors, this is easy to prove by looking at the
set of integers that are not relatively prime to the two factors. For example,
let's say that *n* has as prime factors 3 and 5. Exactly (1/3) of the first
*n* positive integers are not relatively prime to 3, namely, {3,6,9,...,n}.
These are evenly spaced and every 5^{th} one is divisible by 5
(including *n*, the last one in the list). Hence (1/3) of the (1/5) of the
total number of integers in the overall set that are not relatively prime to 5
are in this set. The other (2/3) of them must be in the other set (the set that
is relatively prime to 3) and, once they are removed, the total number of
integers remaining in that set is reduced to (2/3) of (4/5) of the original
count.

Beyond this, a rigorous proof is best done by exploiting the Chinese Remainder Theorem, although the underlying concept is basically the same.

Continuing with this process for each of the prime factors of *n*
yields:

(n) = n_{P}[(p_{i}-1)/p_{i}]
(multiplied over all prime factors of n)