2018 AIME I Problem 11

Attempt Problem 11 of the 2018 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2018 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

11.

Find the least positive integer nn such that when 3n3^n is written in base 143,143, its two right-most digits in base 143143 are 01.01.

Answer: 195
Concepts:multiplicative ordermodular arithmeticbinomial theoremleast common multiple
Difficulty rating: 2990
Solution:

The last two base-143143 digits are 0101 exactly when 3n1(mod1432),3^n \equiv 1 \pmod{143^2}, and since 1432=112132,143^2 = 11^2 \cdot 13^2, this holds exactly when 3n13^n \equiv 1 modulo both 11211^2 and 132.13^2.

Modulo 121:121: 35=243=2121+11,3^5 = 243 = 2 \cdot 121 + 1 \equiv 1, and since 55 is prime and 3≢1,3 \not\equiv 1, the order of 33 is exactly 5.5. Modulo 169:169: the order of 33 modulo 1313 is 3,3, so the order modulo 169169 is a multiple of 3.3. Writing 33=27=1+263^3 = 27 = 1 + 26 and noting 262=41690(mod169),26^2 = 4 \cdot 169 \equiv 0 \pmod{169}, the binomial theorem gives 33k=(1+26)k3^{3k} = (1 + 26)^k 1+26k(mod169),\equiv 1 + 26k \pmod{169}, which is 11 exactly when 13k.13 \mid k. So the order of 33 modulo 169169 is 39.39.

Therefore nn must be a common multiple of 55 and 39,39, and the least is lcm(5,39)=195.\operatorname{lcm}(5, 39) = 195.

← Problem 10#10
Full Exam

Problem 11 in Other Years