Maths Olympiad Prep

Library / /91 of 520

Number theory Difficulty 5.6 AIME, harder Prove it

14. Two arithmetic functions ff and gg may be multiplied using the Dirichlet product which is defined by
(fg)(n)=dnf(d)g(n/d)(f * g)(n)=\sum_{d \mid n} f(d) g(n / d)
a) Show that fg=gff^{*} g=g^{*} f.
b) Show that (fg)h=f(gh)\left(f^{*} g\right) * h=f *\left(g^{*} h\right).
c) Show that if ι\iota is the multiplicative function defined by
(n)={1 if n=10 if n>1(n)=\left\{\begin{array}{ll} 1 & \text { if } n=1 \\ 0 & \text { if } n>1 \end{array}\right.
then ιf=fι=f\iota^{*} f=f^{*} \iota=f for all arithmetic functions ff.
d) The arithmetic function gg is said to be the inverse of the arithmetic function ff if fg=gf=ιf^{*} g=g^{*} f=\iota. Show that the arithmetic function ff has an inverse if and only if f(1)0f(1) \neq 0. Show that if ff has an inverse it is unique. (Hint: When f(1)0f(1) \neq 0, find the inverse f1f^{-1} of ff by calculating f(n)f(n) recursively, using the fact that ι(n)=dnf(d)f1(n/d).)\left.\iota(n)=\sum_{d \mid n} f(d) f^{-1}(n / d).\right)

Solution

None

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.