gauss'theorem

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)}