Maths Olympiad Prep

Library / /421 of 520

Number theory Difficulty 6.7 National olympiad Prove it

Theorem 6.7. If ff is a multiplicative function, then the arithmetic function F(n)=dnf(d)F(n)=\sum_{d \mid n} f(d) is also multiplicative.

Solution

Proof. To show that FF is a multiplicative function, we must show that if mm and nn are relatively prime positive integers, then F(mn)=F(m)F(n)F(m n)=F(m) F(n). So let us assume that (m,n)=1(m, n)=1. We have
F(mn)=dmnf(d)F(m n)=\sum_{d \mid m n} f(d)

By Lemma 2.5 , since (m,n)=1(m, n)=1, each divisor of mnm n can be written uniquely as the product of relatively prime divisors d1d_{1} of mm and d2d_{2} of nn, and each pair of divisors d1d_{1} of mm and d2d_{2} of nn corresponds to a divisor d=d1d2d=d_{1} d_{2} of mnm n. Hence, we can write
F(mn)=d1md2nf(d1d2)F(m n)=\sum_{\substack{d_{1}\left|m \\ d_{2}\right| n}} f\left(d_{1} d_{2}\right)

Since ff is multiplicative and since (d1,d2)=1\left(d_{1}, d_{2}\right)=1, we see that
F(mn)=d1nd2nf(d1)f(d2)=d1mf(d1)d2nf(d2)=F(m)F(n)\begin{aligned} F(m n) & =\sum_{\substack{d_{1}\left|n \\ d_{2}\right| n}} f\left(d_{1}\right) f\left(d_{2}\right) \\ & =\sum_{d_{1} \mid m} f\left(d_{1}\right) \sum_{d_{2} \mid n} f\left(d_{2}\right) \\ & =F(m) F(n) \end{aligned}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.