# Proof: 1620 BC

(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.$$

Thank you to the contributors under CC BY-SA 4.0!

Github: