Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

Prove that:$$\sum_{d\mid n} \varphi(d)=n$$

Where $\varphi(n)$ denotes the number of positive integers $m$ less than or equal to $n$ such that $\gcd(m,n)=1$

I am lost here, any help would be appreciated.

share|cite|improve this question

marked as duplicate by Martin Sleziak, Claude Leibovici, Shuchang, bwv869, Eric Stucky Mar 22 '14 at 9:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

If you know that $\phi$ is multiplicative, and you know that this kind of sum of a multiplicative function is multiplicative, all you have to do is prove it in the case $n$ is prime. – Gerry Myerson Mar 17 '14 at 8:18
@GerryMyerson In case $n$ is prime, the sum is $\varphi(1)+\varphi(n)$ right? – Sabyasachi Mar 17 '14 at 8:20
Yes --- do you know what $\phi(1)$ is? what $\phi(n)$ is, if $n$ is prime? – Gerry Myerson Mar 17 '14 at 8:20
@GerryMyerson oooh. never mind. stupid question. thanks a lot. – Sabyasachi Mar 17 '14 at 8:21
@GerryMyerson Do you mean prime or prime power? – Erick Wong Mar 17 '14 at 8:36
up vote 5 down vote accepted

Consider the cyclic group $C_n$. Then, for every $g\in C_n$, $o(g)$ divides $|C_n|=n$. Moreover, for any $d|C_n$, $\exists g\in C_n:o(g)=d$. Thereofore, if $A_k$ is the set of all the elements of $C_n$ with order $k$, $A_k \neq \emptyset \Longleftrightarrow k | n$. Therefore, $\{A_k : k | n\}$ is a partition of $C_n$. So:

$$|C_n|= n = \displaystyle{\sum _{g \in C_n}} 1 = \displaystyle{\sum _{d|n} |A_d|} = \displaystyle{\sum _{d|n} \varphi(d)}$$

Since the number of elements of order $d$ in $C_n$ is $\varphi(d)$.

share|cite|improve this answer

Here is my proof, based on counting arguments.

Consider the fractions $$\frac1{n},\frac{2}{n},\frac{3}{n},\cdots,\frac{n}{n}$$

Obviously there are $n$ such fractions.

Now consider these fractions, simplified to their lowest terms.

In each of these fractions, the denominator has to be a divisor of $n$. The number of fractions, in which the denominator is still equal to $n$, is the number of fractions whose numerator was originally relatively prime to $n$, i.e, $\varphi(n)$.

Similarly, for any given $d$, where $d$ is a divisor of $n$, there will be $\varphi(d)$ such fractions where the denominator is equal to $d$. Adding all these $\varphi(d)$ thus returns the total number of fractions, $n$.

So we arrive at the equality,

$$\sum_{d\mid n}\varphi(d)=n$$

share|cite|improve this answer
The last parraph's argument isn't clear to me: there could possibly be fractions for which $\;\frac kd=\frac{k'}{d'}\;$ , for two different divisors $\;d,d'\;$ of $\;n\;$ , and thus apparently your method would count these ones twice... – DonAntonio Mar 17 '14 at 13:16
@DonAntonio lowest terms – Sabyasachi Mar 17 '14 at 13:19
What sticks in my craw about this argument is that fractions are really inessential to the problem; they get brought in only because they come with a built-in, widely recognized "simplified to lowest terms" operation. IOW, fractions show up in this theorem only as, basically, a cute hack, and IMO they obscure what's really happening in the theorem, namely that (1) every $m \in \def\nset{\{1,\dots,n\}}\nset$ can be written uniquely as the product $du$ where $d\mid n$ and $\gcd(u, n/d) = 1$, and (2) every such product $du$ belongs to $\nset$. $\;\;\dots$ – kjo Mar 17 '14 at 13:50
@kjo i never said my solution was elegant it just worked for me. – Sabyasachi Mar 17 '14 at 13:52
FWIW I think this proof is very elegant. – 6005 Mar 17 '14 at 14:08

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