Gauss' Theorem
n = SUM(d|n) {phi(d)}
Proof:
Consider the integers, m, s.t. 1<=m<=n, and hcf (m,n)=d.
i.e. hcf (m/d, n/d) = 1, with m/d<=n/d.
For a particular d, there are therefore phi(n/d) such m.
As d runs over all the divisors of n, the number of all these m, in total, is simply, n [since 1<=m<=n]
Therefore n = SUM(d|n) {phi(n/d)} = SUM(d|n) {phi(d)}