Maths Olympiad Prep

Library / /47 of 73

Number theory Difficulty 8.4 Shortlist Prove it Turkey

For a polynomial QQ with integer coefficient and prime pp, we say that QQ excludes pp if there is no integer nn for which pQ(n)p \mid Q(n). Does there exist a polynomial of degree 55 with integer coefficients having no rational roots which excludes exactly one prime?

Solution

Answer: Yes, for example Q(x)=(2x3+1)(x2x+1)Q(x) = (2x^3 + 1)(x^2 - x + 1).
Clearly Q(x)Q(x) has no rational roots. We will show that the only prime excluded by Q(x)Q(x) is p=2p=2.

Observation 1: For any prime pp satisfying p1(mod3)p \equiv 1 \pmod 3 there exists an integer nn such that n2n+10(modp)n^2 - n + 1 \equiv 0 \pmod p.
Proof. Let ω\omega be a primitive root modulo pp and n=ω(p1)/3n = -\omega^{(p-1)/3}. Then n31(modp)n^3 \equiv -1 \pmod p and n≢1(modp)n \not\equiv -1 \pmod p. Now since n3+1=(n+1)(n2n+1)n^3 + 1 = (n+1)(n^2 - n + 1) we get n2n+10(modp)n^2 - n + 1 \equiv 0 \pmod p.

Observation 2: For any odd prime pp satisfying p2(mod3)p \equiv 2 \pmod 3 there exists an integer nn such that 2n3+10(modp)2n^3 + 1 \equiv 0 \pmod p.
Proof. Let aa be an integer satisfying 2a+10(modp)2a+1 \equiv 0 \pmod p. Since 3p23 \mid p-2 we get 32p13 \mid 2p-1. Then for the integer n=a(2p1)/3n = a^{(2p-1)/3} by Fermat's little theorem we have n3a2p1a(modp)n^3 \equiv a^{2p-1} \equiv a \pmod p.

Therefore, 2n3+12a+10(modp)2n^3 + 1 \equiv 2a + 1 \equiv 0 \pmod{p}.
Q(x)Q(x) does not exclude p=3p=3 since 3Q(2)3 \mid Q(2). By Observation 1 any prime p1(mod3)p \equiv 1 \pmod 3 is not excluded by Q(x)Q(x). By Observation 2 any odd prime p2(mod3)p \equiv 2 \pmod 3 is not excluded by Q(x)Q(x). Since both 2n3+12n^3 + 1 and n2n+1n^2 - n + 1 are always odd numbers p=2p=2 is excluded by Q(x)Q(x). We are done.

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.