2018 AIME I Problem 11

Below is the professionally curated solution for Problem 11 of the 2018 AIME I, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:multiplicative ordermodular arithmeticbinomial theoremleast common multiple

Difficulty rating: 2990

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.

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)k1+26k(mod169),3^{3k} = (1 + 26)^k \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 10Full ExamProblem 12

Problem 11 in Other Years