Proof Verification (Reverse of Multiplicative Theorem)

54 Views Asked by At

Show that if $F(n) = \sum_{d|n} f(n)$ is multiplicative, so is f(n).

Following is my proof. Could someone verify if it's valid? Thank you!

Proof:

Suppose integers m, n are coprime. $F(n) = \sum_{d|n} f(n)$ is multiplicative.

Consider F(mn) = F(m)*F(n).

$LHS = \sum_{d|mn} f(d) = \sum_{d1|m, d2|n} f(mn)$.

$RHS = \sum_{d1|m} f(m) * \sum_{d2|n} f(n) = \sum_{d1|m, d2|n} f(m)*f(n)$

Therefore, f(mn) = f(m) * f(n). i.e. f(n) is multiplicative.

2

There are 2 best solutions below

0
On

Things are just required to a bit more rigorous. I think you are considering the function $F(n)=\sum_{d|n}f(d)$. Let $m,n\in \mathbb{N}$ such that $(m,n)=1$. Any divisor of $mn$ can be $\textit{uniquely}$ written as $d=d_1d_2$, where $d_1|m$ and $d_2|n$. By using Mobius inversion formula, $$f(mn)=\sum_{d|mn}\mu(d)F\Big(\frac{mn}{d}\Big)=\sum_{d_1|m,\,d_2|n}\mu(d_1d_2)F\Big(\frac{mn}{d_1d_2}\Big)$$ $$=\sum_{d_1|m,\,d_2|n}\mu(d_1)\mu(d_2)F\Big(\frac{m}{d_1}\Big)F\Big(\frac{n}{d_2}\Big)=\sum_{d_1|m}\mu(d_1)F\Big(\frac{m}{d_1}\Big)\cdot\sum_{d_2|n}\mu(d_2)F\Big(\frac{n}{d_2}\Big)=f(m)\cdot f(n)$$

0
On

To avoid Möbius inversion as you tried in your question, let $k= nm$ be the least integer such that $f(nm) \ne f(n)f(m)$ where $ (n,m)=1$.

Then $$F(k)=F(n)F(m)= \sum_{l | n} \sum_{r | m}f(l) f(r) = ( \sum_{l | n} \sum_{r | m}f(rl))+f(n)f(m)-f(nm)\\=f(n)f(m)-f(nm) + \sum_{d | k} f(d) = f(n)f(m)-f(nm) +F(k)$$

whence $f(n)f(m) -f(nm)=0$, a contradiction.