We define $ f: \mathbb{N} \rightarrow \mathbb{N}$, $ f(n) = \sum_{k = 1}^{n}(k,n)$. a) Show that if $ \gcd(m,n)=1$ then we have $ f(mn)=f(m)\cdot f(n)$; b) Show that $ \sum_{d|n}f(d) = nd(n)$.
Problem
Source: iran2004(number theory exam)
Tags: number theory proposed, number theory
11.09.2004 11:11
a) We have $f(n)=\sum_{d|n}d\phi(\frac nd)$, so $\frac{f(n)}n=\sum_{d|n}\frac{\phi(d)}d$. It's a well-known fact that if $g$ is multiplicative, then so is $G(n)=\sum_{d|n}g(d)$, and since $g(n)=\frac{\phi(n)}n$ is multiplicative, then so is $G(n)=\frac{f(n)}n$, Q.E.D. (by multiplicative I mean $f(mn)=f(m)f(n)$ whenever $(m,n)=1$) b) Since we have established the multiplicativity of $f$, it's enough to show the conclusion holds for $n=p^k$, with $p$ prime. $f(p^i),\ i\ge 1$ is, however, equal to $(i+1)p^i-ip^{i-1}$. Now the conclusion follows easily (a very simple computation, since we have a telescopic sum).
23.08.2021 07:42
sam-n wrote: We define $ f: \mathbb{N} \rightarrow \mathbb{N}$, $ f(n) = \sum_{k = 1}^{n}(k,n)$. a) Show that if $ \gcd(m,n)=1$ then we have $ f(mn)=f(m)\cdot f(n)$; b) Show that $ \sum_{d|n}f(d) = nd(n)$. Well we can see that any divisor $d$ of $n$ is repeated $\phi(\frac{n}{d})$ times , so $$f(n)=\sum_{d|n} id \times \phi (\frac{n}{d})=id \bigstar \phi$$where $\bigstar$ denotes the Dirichlet convolution. After this everything follows serially