Evaluating arithmetic sum using prime factorization [duplicate]

Please help! I have no idea how to start this problem / what to do to evaluate this.

For m>0 , let f(m) = $\sum_{r=1}^{m} \frac{m}{gcd(m,r)}$ . Evaluate f(m) in terms of the prime factorization of m.

• Hint: it's the sum of the orders of all elements in the cyclic group of order $m$.
– lhf
Apr 11 '15 at 23:46
• I would do this one but if it's going to be closed it's not worth typesetting the answer. Apr 11 '15 at 23:48
• @lhf I'm not exactly sure what that is.. We haven't discussed that in our number theory class and this is the only advanced math class I have had so far other than intro to advanced ( basic proofing ) . Apr 11 '15 at 23:49
• @MarkoRiedel I would appreciate any help at all you could give.. This problem is worth a project grade for my class and I really need to do good on it. Apr 11 '15 at 23:50
• @JonathanSeeman The answer is there. I'm not sure of the proceedings if your question gets closed. I will try to re-open if it does. I think this is a fair question and my answer leaves enough material for you to work on. Apr 12 '15 at 1:03

To start, you should verify that if the prime factorization of $m$ is equal to $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_i^{\alpha_i}$, then $f(m) = f(p_1^{\alpha_1}) \times f(p_2^{\alpha_2})\times \dots \times f(p_i^{\alpha_i})$. In other words, $f$ is what is termed a multiplicative function in number theory. Use the Chinese remainder theorem for this.

Suppose we have $$f(n) = \sum_{r=1}^n \frac{n}{\gcd(n,r)} = n \sum_{r=1}^n \frac{1}{\gcd(n,r)}.$$

This is $$n \sum_{d|n} \sum_{r=1, \atop \gcd(n,r)=d}^n \frac{1}{d} = n \sum_{d|n} \frac{1}{d} \sum_{r=1, \atop \gcd(n/d,r)=1}^{n/d} 1 \\ = n \sum_{d|n} \frac{1}{d} \phi(n/d) = n \sum_{d|n} \frac{1}{n/d} \phi(d) = \sum_{d|n} d\phi(d).$$

Now since $\sum_{d|n} \phi(d) = n$ we have $$\zeta(s) \sum_{n\ge 1}\frac{\phi(n)}{n^s} = \sum_{n\ge 1} \frac{n}{n^s} \quad\text{and hence}\quad \sum_{n\ge 1}\frac{\phi(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)}.$$

and $$\sum_{n\ge 1}\frac{\phi(n)}{n^{s-1}} = \sum_{n\ge 1}\frac{n \phi(n)}{n^{s}} = \frac{\zeta(s-2)}{\zeta(s-1)}.$$

It follows that $$\sum_{n\ge 1}\frac{f(n)}{n^{s}} = \zeta(s) \frac{\zeta(s-2)}{\zeta(s-1)}.$$

This gives the Euler product $$\prod_p \frac{1}{1-1/p^s} \frac{1}{1-1/p^{s-2}} (1-1/p^{s-1}).$$

This has two contributions which emerge from the nonfractional term.

The first is $$\frac{1}{1-z}\frac{1}{1-p^2z} = \frac{p^2}{p^2-1}\frac{1}{1-p^2z} + \frac{1}{1-p^2}\frac{1}{1-z}.$$

This gives for the coefficient on $p^v$ the contribution $$\frac{p^2}{p^2-1} p^{2v} + \frac{1}{1-p^2}.$$

The second is $$\frac{p^3}{p^2-1}\frac{z}{1-p^2z} + \frac{p}{1-p^2}\frac{z}{1-z}.$$

This gives for the coefficient on $p^v$ the contribution $$\frac{p^3}{p^2-1} p^{2v-2} + \frac{p}{1-p^2}.$$

Therefore we finally have $f(1)=1$ and $$f(p^v) = \frac{p^2}{p^2-1} p^{2v} + \frac{1}{1-p^2} - \frac{p^3}{p^2-1} p^{2v-2} - \frac{p}{1-p^2}.$$

This simplifies to $$\frac{(p-1)p^{1+2v} + p-1}{p^2-1} = \frac{p^{1+2v} + 1}{p+1}.$$