MathDB

An arithmetic function is a real-valued function whose domain is the set of positive integers. Define the convolution product of two arithmetic functions

f

and

g

to be the arithmetic function

f * g

, where (f * g)(n) \equal{} \sum_{ij\equal{}n} f(i) \cdot g(j), and f^{*k} \equal{} f * f * \ldots * f (

k

times) We say that two arithmetic functions

f

and

g

are dependent if there exists a nontrivial polynomial of two variables P(x, y) \equal{} \sum_{i,j} a_{ij} x^i y^j with real coefficients such that P(f,g) \equal{} \sum_{i,j} a_{ij} f^{*i} * g^{*j} \equal{} 0, and say that they are independent if they are not dependent. Let

p

and

q

be two distinct primes and set f_1(n) \equal{} \begin{cases} 1 & \text{ if } n \equal{} p, \\ 0 & \text{ otherwise}. \end{cases} f_2(n) \equal{} \begin{cases} 1 & \text{ if } n \equal{} q, \\ 0 & \text{ otherwise}. \end{cases} Prove that

f_1

and

f_2

are independent.

Problem Statement