Maths Olympiad Prep

Library / /22 of 86

Number theory Difficulty 5.4 AIME, harder Prove it Estonia

Prove that a2020+10a1010+1001a^{2020} + 10a^{1010} + 1001 is prime for no integers aa.

Solution

Note that 1001=11911001 = 11 \cdot 91. If 11a11 \mid a then also 11a2020+10a1010+100111 \mid a^{2020} + 10a^{1010} + 1001. Otherwise, consider a5a^5 modulo 1111. A case study shows that if aa is congruent to 11, 33, 44, 55, or 99, then a5a^5 is congruent to 11, and in all other cases, a5a^5 is congruent to 1-1. Hence a101(mod11)a^{10} \equiv 1 \pmod{11} whenever 11a11 \nmid a. This implies that a10101(mod11)a^{1010} \equiv 1 \pmod{11} and a20201(mod11)a^{2020} \equiv 1 \pmod{11} because a1010=(a10)101a^{1010} = (a^{10})^{101} (mod11)\pmod{11} and a2020=(a10)202a^{2020} = (a^{10})^{202}. Consequently, 10a101010(mod11)10a^{1010} \equiv 10 \pmod{11}, implying that a2020+10a1010+10010(mod11)a^{2020} + 10a^{1010} + 1001 \equiv 0 \pmod{11}. Thus a2020+10a1010+1001a^{2020} + 10a^{1010} + 1001 cannot be prime since obviously a2020+10a1010+10011001>11a^{2020} + 10a^{1010} + 1001 \ge 1001 > 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 and solution reproduced as published; topic and difficulty added by this site.