IMO 1989 LL THA99

Origin: THA

Problem

An arithmetic function is a real-valued function whose do- main 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) =  ij=n f(i)g(i), and f ⋆k = f ⋆f ⋆\cdot \cdot \cdot ⋆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) =  i,j aijxiyj with real coefficients such that P(f, g) =  i,j aijf ⋆i ⋆g⋆j = 0, and say that they are independent if they are not dependent. Let p and q be two distinct primes and set f1(n) = .1 if n = p, 0 otherwise; f2(n) = .1 if n = q, 0 otherwise. Prove that f1 and f2 are independent.