Maths Olympiad Prep

Library / /13 of 20

Number theory Difficulty 6.5 National olympiad Prove it China

Prove for any integer n4n \ge 4, there exists a polynomial of degree nn,
f(x)=xn+an1xn1++a1x+a0 f(x) = x^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0
with the following properties.
(1) a0,a1,,an1a_0, a_1, \dots, a_{n-1} are all positive integers;
(2) For any positive integer mm and arbitrary kk (k2k \ge 2) positive integers r1,r2,,rkr_1, r_2, \dots, r_k that are different from each other, we have
f(m)f(r1)f(r2)f(rk). f(m) \neq f(r_1)f(r_2)\cdots f(r_k).

Solution

Let
f(x)=(x+1)(x+2)(x+n)+2.1 f(x) = (x+1)(x+2)\cdots(x+n)+2. \qquad \textcircled{1}
Obviously, f(x)f(x) is a monic polynomial of degree nn with positive integer coefficients. We are going to prove that f(x)f(x) has property (2).
For any integer tt, since n4n \ge 4, we know that there exists definitely a multiple of 4 in any nn consecutive numbers t+1,t+2,,t+nt+1, t+2, \dots, t+n. Then from 1\textcircled{1}, we have f(t)2(mod4)f(t) \equiv 2 \pmod 4.
Then for any kk (k2k \ge 2) positive integers r1,r2,,rkr_1, r_2, \dots, r_k, we have
f(r1)f(r2)f(rk)2k0(mod4). f(r_1)f(r_2)\cdots f(r_k) \equiv 2^k \equiv 0 \pmod 4.
On the other hand, for any positive integer mm, we have
f(m)2(mod4)f(m) \equiv 2 \pmod{4}. Therefore,
f(m)≢f(r1)f(r2)f(rk)(mod4), f(m) \not\equiv f(r_1)f(r_2)\cdots f(r_k) \pmod{4},
which implies that f(m)f(r1)f(r2)f(rk)f(m) \neq f(r_1)f(r_2)\cdots f(r_k). We then find the required f(x)f(x) and complete the proof. \square

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.