Maths Olympiad Prep

Library / /127 of 462

Number theory Difficulty 5.3 AIME, harder Prove it Ireland

Find the least positive integer aa such that 20132013 divides 94n+a28n94^n + a \cdot 28^n for some positive integer nn.

Solution

Because 2013=311612013 = 3 \cdot 11 \cdot 61, the requirement 94n+a28n0(mod2013)94^n + a \cdot 28^n \equiv 0 \pmod{2013} implies a+10(mod3)a+1 \equiv 0 \pmod{3}, 6n(a+1)0(mod11)6^n(a+1) \equiv 0 \pmod{11} and 28n((1)n+a)0(mod61)28^n((-1)^n + a) \equiv 0 \pmod{61}. Therefore a1(mod3)a \equiv -1 \pmod{3}, a1(mod11)a \equiv -1 \pmod{11} and a(1)n+1(mod61)a \equiv (-1)^{n+1} \pmod{61}. Using the Chinese Remainder Theorem, we see that for nn even the smallest positive integer aa which satisfies these three congruences is 20122012. For odd nn, we need to solve 33k11(mod61)33k-1 \equiv 1 \pmod{61}. Using Euclid's Algorithm, we obtain 13612433=113 \cdot 61 - 24 \cdot 33 = 1, and we see that k24213(mod61)k \equiv -24 \cdot 2 \equiv 13 \pmod{61}. This yields that the smallest possible aa is equal to 33131=42833 \cdot 13 - 1 = 428.

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.