Maths Olympiad Prep

Library / /3 of 6

Algebra Difficulty 5.5 AIME, harder Prove it Brazil

Find all real-valued functions on the positive integers such that f(x+1019)=f(x)f(x+1019) = f(x) for all integer xx, and f(xy)=f(x)f(y)f(xy) = f(x)f(y) for all integers x,yx, y.

Solution

The condition f(x+1019)=f(x)f(x + 1019) = f(x) allows to make all computations modulo 10191019, which is a prime number. Hence the problem asks the number of multiplicative functions in Z/1019Z\mathbb{Z}/1019\mathbb{Z}.

Two such functions are f(x)1(mod1019)f(x) \equiv 1 \pmod{1019} and f(x)0(mod1019)f(x) \equiv 0 \pmod{1019}. From now on suppose ff is different from these two functions.

Substituting y=0y = 0, f(0)=f(x)f(0)f(0)=0f(0) = f(x)f(0) \Leftrightarrow f(0) = 0; substituting y=1y = 1, f(x)=f(x)f(1)f(1)=1f(x) = f(x)f(1) \Leftrightarrow f(1) = 1. By Euler-Fermat's theorem, xϕ(1019)1(mod1019)x^{\phi(1019)} \equiv 1 \pmod{1019} so f(x)ϕ(1019)=f(xϕ(1019))=f(1)=1f(x)=±1f(x)^{\phi(1019)} = f(x^{\phi(1019)}) = f(1) = 1 \Leftrightarrow f(x) = \pm 1.

Now let gg be a primitive root of 10191019 (that is, gg such that the least positive integer dd such that gd1(mod1019)g^d \equiv 1 \pmod{1019} is ϕ(1019)\phi(1019)). So every xx in Z/1019Z\mathbb{Z}/1019\mathbb{Z} can be written as gkg^k for some kk. Then f(x)=(f(g))kf(x) = (f(g))^k. If f(g)=1f(g) = 1 then f(x)=0f(x) = 0 if 10191019 divides xx and 11 otherwise; if f(g)=1f(g) = -1 then f(x)=0f(x) = 0 if 10191019 divides xx, f(x)=1f(x) = 1 if xx is a quadratic residue modulo 10191019 (such residues are 1,g2,g4,,g10161, g^2, g^4, \dots, g^{1016}) and f(x)=1f(x) = -1 otherwise.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.