Maths Olympiad Prep

Library / /27 of 41

Number theory Difficulty 6.0 AIME, harder Prove it New Zealand

Problem:
Let pp be a prime and let f(x)=ax2+bx+cf(x) = a x^{2} + b x + c be a quadratic polynomial with integer coefficients such that 0<a,b,cp0 < a, b, c \leq p. Suppose f(x)f(x) is divisible by pp whenever xx is a positive integer. Find all possible values of a+b+ca + b + c.

Solution

Solution:
First substitute x=px = p, to get pap2+bp+cp \mid a p^{2} + b p + c so pcp \mid c. Therefore c=pc = p.

Next substitute x=1x = 1, to get pa+b+cp \mid a + b + c. Since c=pc = p, this gives us pa+bp \mid a + b.

Finally substitute x=p1x = p - 1, to get (p1)2a(p1)b+c0(p - 1)^{2} a - (p - 1) b + c \equiv 0 (mod pp). Thus ab+c0a - b + c \equiv 0 (mod pp), and since c=pc = p, we get pabp \mid a - b.

Adding and subtracting pa+bp \mid a + b and pabp \mid a - b we get
p(a+b)+(ab)=2aandp(a+b)(ab)=2b. p \mid (a + b) + (a - b) = 2a \qquad \text{and} \qquad p \mid (a + b) - (a - b) = 2b.
Now there are two cases: either p=2p = 2 or pp is odd.

Case 1 p=2p = 2

2ab2 \mid a - b means that either a=b=1a = b = 1 or a=b=2a = b = 2, i.e. the only two possibilities for (a,b,c)(a, b, c) are (1,1,2)(1, 1, 2) and (2,2,2)(2, 2, 2). So the only candidate polynomials are
x2+x+2and2x2+2x+2. x^{2} + x + 2 \qquad \mathrm{and} \qquad 2x^{2} + 2x + 2.
Now we check that these work. If f(x)=x2+x+2=2+x(x+1)f(x) = x^{2} + x + 2 = 2 + x(x + 1) which is always even because both 2 and x(x+1)x(x + 1) are even for all integers xx. If f(x)=2x2+2x+2=2(x2+x+1)f(x) = 2x^{2} + 2x + 2 = 2(x^{2} + x + 1) which is always even because it has a factor of 2.

Case 2 pp is an odd prime:

Since (2,p)=1(2, p) = 1, pap \mid a so a=pa = p. Also note that p2bp \mid 2b by subtracting aba - b from a+ba + b, so by a similar argument, b=pb = p. Thus, a+b+c=p+p+p=3pa + b + c = p + p + p = 3p

Combining the two cases, a+b+c=3pa + b + c = 3p for all pp and a+b+c=4a + b + c = 4 when p=2p = 2 are the only possible values of a+b+ca + b + c.

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.