Number theoryDifficulty 5.3AIME, harderProve itIreland
Find the least positive integer a such that 2013 divides 94n+a⋅28n for some positive integer n.
Solution
Because 2013=3⋅11⋅61, the requirement 94n+a⋅28n≡0(mod2013) implies a+1≡0(mod3), 6n(a+1)≡0(mod11) and 28n((−1)n+a)≡0(mod61). Therefore a≡−1(mod3), a≡−1(mod11) and a≡(−1)n+1(mod61). Using the Chinese Remainder Theorem, we see that for n even the smallest positive integer a which satisfies these three congruences is 2012. For odd n, we need to solve 33k−1≡1(mod61). Using Euclid's Algorithm, we obtain 13⋅61−24⋅33=1, and we see that k≡−24⋅2≡13(mod61). This yields that the smallest possible a is equal to 33⋅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.