We need to prove that \(\sum_{d|n, d>0} \phi(d) = n\). Let's use \(n=24\) as an example. We will first start by a set \(S_d\):
Let's use \(n=24\) as an example:
There are two things to notice here. Firstly, the integers in all these sets are only mentioned once and not repeated. This is true because the output of \(\gcd(m,n)\) cannot be two or more integers, so all the \(\gcd\)'s exist in only one set, and not multiple sets.
Secondly, all integers between 1 to \(n\) (inclusive) are mentioned. This is true because there will always be some \(k\), such that \(1\le k \le n\) and \(\gcd(m,n)=k\), so \(m\) would belong to \(S_k\).
If all the \(S_d\)'s contain integers from 1 to \(n\), and all the integers are only mentioned once, then the length of all these sets together should be \(n\):
Since \((m,n)=d\) implies \((\frac{m}{d}, \frac{n}{d})=1\), we can rewrite the definition of \(S_d\) as:
Let's define another set \(K_d\), where \(k=\frac{m}{d}\):
Let's see examples of this will \(n=24\):
Since \(K_d\) represents all the positive integers \(\le n\) that are coprime with \(\frac{n}{d}\), then, by definition, \(\phi \left( \frac{n}{d} \right) = | K_d |\).
Also, \(| K_d| = | S_d |\). This is true because if you divide all the elements in \(S_d\) by \(d\), you get \(K_d\). This is more clear if you see how we defined \(K_d\):
This means:
Let \(d_1\) and \(d_2\) be two integers that multiply to give \(n\). This means \(\frac{n}{d_1} = d_2\) and \(\frac{n}{d_2} = d_1\), which means dividing \(n\) by a divisor gives another divisor. Therefore, listing out all the values of \(\frac{n}{d}\), then you are listing out \(d\) in reverse:
Since \(\frac{n}{d_1}=d_2\), then \(\phi \left( \frac{n}{d_1} \right) = \phi(d_2) \). This also means:
Therefore: