Maths Olympiad Prep

Library / /202 of 462

Number theory Difficulty 5.7 AIME, harder Prove it Ireland

Find the smallest prime number which divides n23n+13n^2 - 3n + 13 for some integer nn.

Solution

We define f(x)=x23x+13f(x) = x^2 - 3x + 13 and note that f(x)=(x3)x+13=13x(3x)f(x) = (x-3)x + 13 = 13 - x(3-x) from which we easily discover that f(3x)=f(x)f(3-x) = f(x) for all xx. Calculating f(0)=13f(0) = 13 and f(1)=11f(1) = 11, we see that the smallest prime pp that divides f(n)f(n) for some nn is at most 1111. We may finish in two different ways.

Way 1. Because f(n)f(m)(modp)f(n) \equiv f(m) \pmod{p} when nm(modp)n \equiv m \pmod{p}, it is sufficient to calculate f(n)(modp)f(n) \pmod{p} for pp consecutive values of nn. We only need to do this for p{2,3,5,7}p \in \{2, 3, 5, 7\} in order to determine whether 1111 is the smallest prime we are looking for. Because f(3n)=f(n)f(3-n) = f(n), we have f(2)=f(1)=11f(2) = f(1) = 11, f(3)=f(0)=13f(3) = f(0) = 13 and f(4)=f(1)=17f(4) = f(-1) = 17. Finally, f(2)=23f(-2) = 23 and we see that f(n)11f(n) \ge 11 is a prime for each of the seven consecutive values n=2,1,0,1,2,3,4n = -2, -1, 0, 1, 2, 3, 4. Hence, the smallest prime number that divides f(n)f(n) for at least one nn is p=11p = 11.

Way 2. For each p{2,3,5,7}p \in \{2, 3, 5, 7\} we discuss f(n)(modp)f(n) \pmod{p} separately.
f(n)=n23n+13n2n+11(mod2) f(n) = n^2 - 3n + 13 \equiv n^2 - n + 1 \equiv 1 \pmod{2}
because n2n(mod2)n^2 \equiv n \pmod{2} for all integers nn by Fermat's Little Theorem.
f(n)=n23n+13n22≢0(mod3) f(n) = n^2 - 3n + 13 \equiv n^2 - 2 \not\equiv 0 \pmod{3}
because squares of integers can only be congruent to 00 or 11 modulo 33.
f(n)=n23n+13n2+2n+3(n+1)2+2≢0(mod5) f(n) = n^2 - 3n + 13 \equiv n^2 + 2n + 3 \equiv (n+1)^2 + 2 \not\equiv 0 \pmod{5}
because squares of integers can only be congruent to 00 or ±1\pm 1 modulo 55.
f(n)=n23n+13n2+4n+6(n+2)2+2≢0(mod7) f(n) = n^2 - 3n + 13 \equiv n^2 + 4n + 6 \equiv (n+2)^2 + 2 \not\equiv 0 \pmod{7}
because squares of integers can only be congruent to 00, 11, 22 or 44 modulo 77. Hence, for no integer nn is f(n)f(n) divisible by 22, 33, 55 or 77. The smallest prime number that divides f(n)f(n) for at least one nn therefore is p=11p = 11.

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.