Maths Olympiad Prep

Library / /1 of 22

Number theory Difficulty 4.6 AIME Prove it Czech-Polish-Slovak Mathematical Match

Prove that there exists a positive integer nn, such that for all integers kk the number k2+k+nk^2 + k + n has no prime divisors less than 20082008.

Solution

Let p<2008p < 2008 be a fixed prime number. There exists r=r(p)r = r(p) such that k2+kr(modp)k^2 + k \neq r \pmod{p} for any integer kk; this follows, for example, from the fact that if k0(modp1)k \equiv 0 \pmod{p-1} (mod pp), then k2+k0(modp)k^2 + k \equiv 0 \pmod{p}.

Now if {p1,p2,,pm}\{p_1, p_2, \dots, p_m\} is the set of all prime numbers not exceeding 20082008, we take nn satisfying
npjr(pj)(modpj),j=1,2,,m, n \equiv p_j - r(p_j) \pmod{p_j}, \quad j = 1, 2, \dots, m,
which exists due to the Chinese Remainder Theorem. This number has the desired property.

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.