Maths Olympiad Prep

Library / /37 of 45

, 2009

Number theory Difficulty 8.9 Shortlist Prove it United States

Fix a prime number p>5p > 5. Let a,b,ca, b, c be integers no two of which have their difference divisible by pp. Let i,j,ki, j, k be nonnegative integers such that i+j+ki + j + k is divisible by p1p-1. Suppose that for all integers xx, the quantity
(xa)(xb)(xc)[(xa)i(xb)j(xc)k1] (x-a)(x-b)(x-c)[(x-a)^i(x-b)^j(x-c)^k - 1]
is divisible by pp. Prove that each of i,j,ki, j, k must be divisible by p1p-1.

Solution

We first prove that kk is congruent to one of 1,0,11, 0, -1 modulo (p1)(p-1). We rephrase the hypothesis in terms of modular arithmetic: If x≢a,b,c(modp)x \not\equiv a, b, c \pmod p, then
(xa)i(xb)j(xc)k(modp). (x - a)^i (x - b)^j \equiv (x - c)^{-k} \pmod{p}.
By Fermat's little theorem, there is no harm in shifting i,j,ki, j, k by multiples of p1p-1, so we may assume i,j,ki, j, -k are elements of the set {0,1,2,,p2}\{0, 1, 2, \dots, p-2\}. If i+jp2i + j \le p-2, then the condition i+j+k0(modp1)i + j + k \equiv 0 \pmod{p-1} forces k=i+j-k = i + j. In this case, the polynomial (xc)k(xa)i(xb)j(x-c)^{-k} - (x-a)^i(x-b)^j has degree at most k1-k-1 (since it is the difference of two monic polynomials of degree k-k), but modulo pp it has at least p3p-3 distinct roots (namely the values of xx other than a,b,ca, b, c). The only ways to avoid a contradiction are either to have i+j=k=p2i+j = -k = p-2 or to have the polynomial (xc)k(xa)i(xb)j(x-c)^{-k} - (x-a)^i(x-b)^j be identically zero modulo pp. The former gives k1(modp1)k \equiv 1 \pmod{p-1} and we are done. The latter forces i=j=k=0i = j = -k = 0 by unique factorization of polynomials modulo pp, so we are again done.

If on the other hand i+jp1i + j \ge p - 1, then we also have
(xa)p1i(xb)p1j(xc)k(modp) (x - a)^{p-1-i} (x - b)^{p-1-j} \equiv (x - c)^{k} \pmod{p}
for all xx not congruent to a,b,ca, b, c modulo pp. If k0(mod(p1))k \equiv 0 \pmod{(p-1)}, we are done; otherwise, the fact that i+jk≢0(mod(p1))i+j \equiv -k \not\equiv 0 \pmod{(p-1)} forces i+jpi+j \ge p, so (p1i)+(p1j)p2(p-1-i) + (p-1-j) \le p-2. Thus the previous paragraph implies either k0(mod(p1))k \equiv 0 \pmod{(p-1)} or k1(mod(p1))k \equiv -1 \pmod{(p-1)}.

By symmetry, each of ii, jj, kk is congruent to one of 1-1, 00, 11 modulo (p1)(p-1). Because i+j+k0i + j + k \equiv 0 (mod (p1)(p-1)) and p1>3p - 1 > 3, the only possibilities (up to permutations) are {i,j,k}{0,0,0}\{i, j, k\} \equiv \{0, 0, 0\} (mod (p1)(p-1)) or {i,j,k}{1,0,1}\{i, j, k\} \equiv \{1, 0, -1\} (mod (p1)(p-1)). However, the latter implies that xaxcx - a \equiv x - c (mod pp) for all xa,b,cx \ne a, b, c (mod pp), which is impossible as soon as there is at least one such xx (which is true since p>3p > 3). This contradiction leaves only the possibility {i,j,k}{0,0,0}\{i, j, k\} \equiv \{0, 0, 0\} (mod (p1)(p-1)), proving the desired result.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.