(n)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 piki
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
(pk) = (p-1)(p(k-1))
for p prime
As an example, consider n = 53 = 125. This list may be broken into 52 = 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 pk 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
(pk) = [(p-1)/p](pk)
= (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 {pi} be the set of i prime factors of n. Then the number of integers less than n that are relatively prime to a particular pi will be:
# relatively prime to pi = n[(pi-1)/pi]
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 p1), then the above expression tells us that the set containing the numbers relatively prime to p1 is
# relatively prime to p1 = n[(p1-1)/p1]
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 p1), the number in this set will be:
# relatively prime to p1 and p2 = n[(p1-1)/p1][(p2-1)/p2]
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 5th 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) = nP[(pi-1)/pi]
(multiplied over all prime factors of n)