Let $n$ be a positive integer. Then $$ \sum_{d|n} \phi(d) = n$$
Where $\phi$ is the euler totient function.
The first step in a proof of this is to define a set $S_d$, for each divisor $d$ of $n$; $S_d={\{1 \leq a \leq n : gcd(a,n) = d}\}$.
It then states that it is "obvious" that $\sum_{d|n} |S_d| = n$, however this isn't remotely obvious to me?
Could anyone explain it to me please?
This has been flagged for a duplicate but the duplicate question doesn’t specifically tackle the step in the proof that is troubling me.
Take an example: Let $n = 10$
The divisors of $n$ are $1,2,5,10$
$S_1 = {1,3,7,9}$
$S_2 = {2,4,6,8}$
$S_5 = {5}$
$S_{10} = {10}$
We have two prove two things: 1. All numbers from $\{1, \ldots, n\}$ are included and 2. there are no repeats.
All $a \in \{1, \ldots, n\}$ have a $gcd(a,n)$ equal to either $1,2,5,$ or $10$. (the divisors of $n$).
If a number $a$ is in two of the sets, this would imply it has two different $gcd(a,n)$. Violates the definition of $gcd(a,n)$.