\[\sum_{d | n} \phi (d)=n\]
where \[\phi\]
is Euler's totient function and \[d\]
is a divisor of \[n\]
.Proof
Define
\[S_d=\{m:1 \lt m \lt n, \; gcd)m, n)=d \}\]
.\[gcd(m,n)=d\]
if and only if \[\frac{m}{d}, \; \frac{n}{d}\]
satisfy \[gcd(\frac{m}{d}, \; \frac{n}{d})=1\]
. The number of elements in \[S\]
is equal to the number of positive integers not exceeding \[\frac{n}{d}\]
which are relatively prime to \[\frac{n}{d}\]
, so \[| S_d | = \phi )\frac{n}{d} )\]
.Each of the integers
\[1, \; 2, \; 3,..., \; n\]
lies in exactly one \[S_d\]
and there is one class corresponding to each divisor of \[n\]
, \[n=\sum_{d | n} \phi (\frac{n}{d})=\sum_{d | n} \phi (d)\]
.