I have been give a project for number theory: 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$.
So far, I have found a formula for $f(p)$ for when $p$ is prime, and $f(p^2)$ for a prime $p$. They are, $f(p)=p^2-p+1$ and $f(p^2)= p^4-p^3+p^2-p+1$.
All I have left is to show that when $gdc(m,n)=1$, $f(m)*f(n)= f(mn)$ . How would I go about proving this?
On
We will partition all integers $r$ according to the value $k=\gcd(r,m)$. Notice that each g.c.d. is a divisor of $m$. We have $$f(m)=\sum_{k|m}\frac{m}{k}\sum_{r}1,$$ where the inner sum is over integers $1\leq r \leq m$ with $\gcd(r,m)=k$. These integers are divisible by $k$ and are therefore of the shape $r=r'k$ for some integer $r'$ in the range $1\leq r'\leq m/k$ and with $\gcd(r',m/k)=1$. The last equality is derived by substituting $r=kr'$ in $\gcd(m,r)=k$. Notice that the number of the integers $r'$ is $\phi(m/k)$ where $\phi(.)$ is the Euler totient function. Hence $f(m)$ equals $$\sum_{k|m}\frac{m}{k}\phi(\frac{m}{k}).$$ Now notice that the set of number $m/k$ as $k$ runs through the divisors of $m$ is the same set of numbers assumed by $k$, this leads to the expression $$f(m)=\sum_{k|m}k\phi(k)$$ and therefore the factorisation expression you asked for is $$f(m)=\sum_{p^a\|m}\left(1+\frac{p}{p+1} (p^{2a}-1)\right).$$
I would first look at the product of two distinct primes: let $p,q$ be distinct primes. WLOG let $p>q$, and set $r = p-q>0$.
Then $f(qp) = \sum_{r=1}^{pq} \frac{pq}{(pq,r)}= (pq-r-1)\cdot pq+p+(r-1)\cdot q+1$.
Now make sure that this is in fact $f(p)\cdot f(q)$.
More generally, if $n=p^k$, then $f(p^k) = \phi(p^k)p^k + \phi(p^{k-1})p^{k-1}+\ldots +\phi(p)p+1$, where $\phi$ is the Euler $\phi$ function.
Prove this to yourself before moving on... With the formula for $\phi$, you should be able to work something nice out for $f(p^k)$.
General multiplicativity should follow from understanding the role of the multiplicative $\phi$ in the behavior of $f$.