# Understanding Gauss Theorem:$n=\sum_{d|n}\phi(d)$

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)?

## 1 Answer

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\}$

• I'm really lacking concept to be comfortable with the first bullet, please explain it in easiest way (elementary way). – mnulb Jan 3 '17 at 5:12
• @Ayushakj does my edit make sense? – Stella Biderman Jan 3 '17 at 5:17
• ....ok, $S_d$ have $m's\leq n$, and let $gcd(m,n)=d$, now if we divide $n$ by $d$, then there is no comman factor between $m's$ and $n/d$, hence $gcd(m's,n/d)=1$, $S_d$ contains all such $m's$ which satisfy previous condition. So number of integers is $\phi(n/d)$. Is it correct? – mnulb Jan 3 '17 at 5:54
• @Ayushakj yes, that is correct – Stella Biderman Jan 3 '17 at 6:15