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:

enter image description here

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


where the first equality holds because the collection of $S_d$'s is a partition of $\{1,\ldots,n\}$

  • $\begingroup$ I'm really lacking concept to be comfortable with the first bullet, please explain it in easiest way (elementary way). $\endgroup$ – mnulb Jan 3 '17 at 5:12
  • $\begingroup$ @Ayushakj does my edit make sense? $\endgroup$ – Stella Biderman Jan 3 '17 at 5:17
  • $\begingroup$ ....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? $\endgroup$ – mnulb Jan 3 '17 at 5:54
  • $\begingroup$ @Ayushakj yes, that is correct $\endgroup$ – Stella Biderman Jan 3 '17 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.