The Sum of Totients of Divisors of n is n

This is a surprising factoid:

Σ φ(d) = n
^d|n

Proof:

We will prove this sum-of-totients-of-divisors theorem by partitioning the set {1,2,3,...,n} into subsets according to each element's greatest common divisor with n.  Each subset of {1,2,3,...,n} will be called Q(g), the set of all integers between 1 and n inclusive, such that gcd(x,n) = g.  The Q(g) sets don't overlap, and their union is {1,2,3,...,n}, so the sum of the cardinality of the Q(g) sets is n.  Also, there is a one-to-one correspondence between the elements of Q(g) and the "proper coprimes" of n/g, which completes the proof.

For example, if n=12, then the set {1,2,3,4,5,6,7,8,9,10,11,12} is partitioned into these sets:

Q(1) = {1,5,7,11}
Q(2) = {2,10}
Q(3) = {3,9}
Q(4) = {4,8}
Q(6) = {6}
Q(12) = {12}

(All other Q(g) are empty sets)

These "Q" sets have the following three properties:

Q(g) is nonempty if and only if g divides n.  (If g weren't a divisor of n, then it could never be the greatest common divisor of n and some other number).

If x belongs to Q(g) for a given g, then it can't belong to another Q(h) where h≠g, because it wouldn't be possible for gcd(x,n)=g and gcd(x,n)=h.

For all x between 1 and n inclusive, there exists a g such that gcd(x,n) = g

Put together, these three properties imply that the union of all the Q(g) sets (for each g a divisor of n), which are pairwise mutually exclusive, is the set {1,2,3,...,n}.  And therefore, the sum of the cardinalities of each Q(g) equals n.

Now consider the set Q(g)/g, which is the set obtained by dividing each element of Q(g) by g.  You know all the elements of Q(g)/g are integers, because g is a divisor of every element of Q(g).  Let's look at our example, where n=12, again:

Now we will show that Q(g)/g is the set of "proper coprimes" of n/g.  By "proper coprimes" I mean positive numbers coprime to n that don't exceed n.  Keep in mind that the set of proper coprimes of n/g contains φ(n/g) elements, so by showing that Q(g)/g is the set of proper coprimes of n/g, we will show that |Q(g)|  = φ(n/g).  Also, since the set {n/g | g divides n} is equal to the set {d | d divides n}, and the union of the Q(g) sets is {1,2,3,...,n}, the result will follow, and the proof will be complete.

Suppose x is an element of Q(g)/g.  That means gx is an element of Q(g), so gcd(gx,n)=g, so gcd(x,n/g)=1, which means x is a coprime of n/g.  gx does not exceed n, so x does not exceed n/g, which means x is a proper coprime of n/g.

Now suppose x is a proper coprime of n/g.  gcd(x,n/g)=1, so gcd(gx,n)=g, so x is an element of Q(g)/g.

Therefore, |Q(g)| = φ(n/g).  The proof is complete.

Now, let's take one more look at our example, filling in the part about φ(n/g):

Internet References

Related Pages in this website

Squares.

Fermat's Theorems -- Fermat's Little Theorem, in particular.

Group - definition of a "group", which has properties closure, associativity, identity, and inverse.

The proof that primes of the form 4k+3 can be expressed as the sum of four squares uses Fermat's Little Theorem.

A bunch of Ring Theory theorems and definitions.

Proof that there is no solution to the Diophantine equation A⁴+B⁴=C², which means Fermat's last theorem is true 

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]