Gauss. For each positive integer $n\geq1$,$$n=\sum_{d|n}\phi(d)$$the sum being extended over all positive divisors of $n$.
Proof of this:
I need to understand all highlighted parts i.e.:
- Why number of integer in $S_d$ equal to number of positive integers not exceeding $n/d$ and relatively prime to $n/d$?
- And how that formula came (highlighted one)?
The first bullet holds because $f(x)=x/d$ is a bijection between $S_d$ and the set of integers relatively prime to $n/d$ and not exceeding it.
The second bullet follows by considering
$$n=\sum_{d|n}|S_d|=\sum_{d|n}\phi(n/d)$$
where the first equality holds because the collection of $S_d$'s is a partition of $\{1,\ldots,n\}$