Maths Olympiad Prep

Library / /47 of 53

Number theory Difficulty 7.2 National olympiad, round 2 Prove it China

Find the number of polynomials f(x)=ax3+bxf(x) = a x^3 + b x that satisfy the following conditions:
(1) a,b{1,2,,2013}a, b \in \{1, 2, \dots, 2013\};
(2) the difference of any two numbers among f(1)f(1), f(2)f(2), \dots, f(2013)f(2013) is not a multiple of 20132013.

Solution

2013 is factorized as 2013=3×11×612013 = 3 \times 11 \times 61. Let p1=3p_1 = 3, p2=11p_2 = 11, p3=61p_3 = 61. We denote by aia_i the residue of aa modulo pip_i, by bib_i the residue of bb modulo pip_i (i=1,2,3i = 1, 2, 3), a,b{1,2,,2013}a, b \in \{1, 2, \dots, 2013\}. By the Chinese Remainder Theorem, we have a bijection of (a,b)(a, b) with (a1,a2,a3,b1,b2,b3)(a_1, a_2, a_3, b_1, b_2, b_3).

Now, let fi(x)=aix3+bixf_i(x) = a_i x^3 + b_i x, i=1,2,3i = 1, 2, 3. We call a polynomial "good modulo nn" if the residues of f(0),f(1),,f(n1)f(0), f(1), \dots, f(n-1) modulo nn are all distinct.

If f(x)=ax3+bxf(x) = a x^3 + b x is not good modulo 20132013, then there exists x1≢x2(mod2013)x_1 \not\equiv x_2 \pmod{2013} such that f(x1)f(x2)(mod2013)f(x_1) \equiv f(x_2) \pmod{2013}. Suppose x1≢x2(modpi)x_1 \not\equiv x_2 \pmod{p_i}. Let u1u_1 and u2u_2 be the residues of x1x_1 and x2x_2 modulo pip_i, respectively. Then u1≢u2(modpi)u_1 \not\equiv u_2 \pmod{p_i} and fi(u1)fi(u2)(modpi)f_i(u_1) \equiv f_i(u_2) \pmod{p_i}, so fi(x)f_i(x) is not good modulo pip_i.

If f(x)=ax3+bxf(x) = a x^3 + b x is good modulo 20132013, then for every ii, fi(x)f_i(x) is good modulo pip_i. The reason is as follows. For any distinct pair r1,r2{0,1,,pi1}r_1, r_2 \in \{0, 1, \dots, p_i - 1\}, there exist x1,x2{1,2,,2013}x_1, x_2 \in \{1, 2, \dots, 2013\} such that x1r1(modpi)x_1 \equiv r_1 \pmod{p_i} and x2r2(modpi)x_2 \equiv r_2 \pmod{p_i} and x2x2(mod2013pi)x_2 \equiv x_2 \pmod{\frac{2013}{p_i}}. Now f(x1)f(x2)(mod2013pi)f(x_1) \equiv f(x_2) \pmod{\frac{2013}{p_i}}, but f(x1)≢f(x2)(mod2013)f(x_1) \not\equiv f(x_2) \pmod{2013}, so f(r1)≢f(r2)(modpi)f(r_1) \not\equiv f(r_2) \pmod{p_i}.

Hence, we need to determine the number of good polynomials fi(x)f_i(x) modulo pip_i.

For p1=3p_1 = 3, by Fermat's theorem, a good polynomial
f1(x)a1x3+b1x(a1+b1)x(mod3) f_1(x) \equiv a_1 x^3 + b_1 x \equiv (a_1 + b_1) x \pmod{3}
is equivalent to say that a1+b1a_1 + b_1 is not divisible by 33. There are in total six such f1(x)f_1(x).

For i=2,3i = 2, 3, if fi(x)f_i(x) is good modulo pip_i, then for any uu and v≢0(modpi)v \not\equiv 0 \pmod{p_i}, fi(u+v)≢fi(uv)(modpi)f_i(u + v) \not\equiv f_i(u - v) \pmod{p_i}, i.e.,
fi(u+v)fi(uv)=2v[ai(3u2+v2)+bi] f_i(u + v) - f_i(u - v) = 2v[a_i(3u^2 + v^2) + b_i]
is not divisible by pip_i. If ai0a_i \neq 0, the residues modulo pip_i of elements in the sets A={3aiu2u=0,1,,pi12}A = \{3a_i u^2 \mid u = 0, 1, \dots, \frac{p_i-1}{2}\} and B={(biaiv2)v=1,2,,pi12}B = \{(-b_i - a_i v^2) \mid v = 1, 2, \dots, \frac{p_i-1}{2}\} do not coincide, and A+B=pi|A| + |B| = p_i. So ABA \cup B forms a complete residue system modulo pip_i. Their sum must be a multiple of pip_i, i.e.,
u=0pi123aiu2+v=1pi12(biaiv2)0(modpi). \sum_{u=0}^{\frac{p_i-1}{2}} 3a_i u^2 + \sum_{v=1}^{\frac{p_i-1}{2}} (-b_i - a_i v^2) \equiv 0 \pmod{p_i}.
Now, 12+22++(pi12)2=16pi12pi+12pi1^2 + 2^2 + \dots + \left(\frac{p_i-1}{2}\right)^2 = \frac{1}{6} \cdot \frac{p_i-1}{2} \cdot \frac{p_i+1}{2} \cdot p_i is a multiple of pip_i, so pi12bi-\frac{p_i-1}{2} \cdot b_i is also a multiple of pip_i. Hence, bib_i is divisible by pip_i, i.e., exactly one of aia_i, bib_i is 00.

If ai=0,bi0a_i = 0, b_i \neq 0, then fi(x)=bixf_i(x) = b_i x is obviously good. There are pi1p_i - 1 such good polynomials.

If ai0,bi=0a_i \neq 0, b_i = 0, then fi(x)=aix3f_i(x) = a_i x^3. For p2=11p_2 = 11, by Fermat's theorem, (x3)7=x21x(mod11)(x^3)^7 = x^{21} \equiv x \pmod{11}, so for x1x2(mod11)x_1 \neq x_2 \pmod{11} and x13x23(mod11)x_1^3 \neq x_2^3 \pmod{11}, f2(x)=a2x3f_2(x) = a_2 x^3 is good. There are in total 1010 such polynomials.

For p3=61p_3 = 61, as 43=64125=53(mod61)4^3 = 64 \equiv 125 = 5^3 \pmod{61}, f3(x)=a3x3f_3(x) = a_3 x^3 cannot be good.

Therefore, the total number that we are looking for is 6×(10+10)×60=72006 \times (10 + 10) \times 60 = 7200. \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.