(related to Proposition: Sum of Euler Function)

- Let $n\ge 1$ be a natural number.
- If we calculated for all numbers $k=1,2,\ldots, n,$ the greatest common divisor $d_k=\gcd(k,n)$, then the relation $k\sim l:=d_k=d_l$ is an equivalence relation and we can group all these numbers by those having the same greatest common divisor $d_k.$
- For each equivalence class $d_k$, we have by the proposition and the proposition that $k\perp\frac{n}{d_k}$ (co-prime) and $0 < k\cdot d_k\le n.$
- From this, it follows that the count of numbers $k$ being co-prime to $\frac{n}{d_k}$ with $0 < k\le\frac{n}{d_k}$ is exactly equal the Euler function $\phi\left(\frac{n}{d_k}\right),$ by definition.
- Because all classes $d_k$ are disjoint, we can sum up all counts and get $$\sum_{d_k\mid n}\phi\left(\frac{n}{d_k}\right)=n.$$
- Note that with $\frac{n}{d_k}$ also the complementary divisor $d_k$ takes all possible values.
- Therefore, we get the required result
$$\sum_{d_k\mid n}\phi(d_k)=\sum_{d\mid n}\phi(d)=n.$$∎