2018 AIME I 第 11 题

先试着解答 2018 AIME I 第 11 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2018 AIME I 解答,或核对答案

所有题目均经美国数学协会(MAA)官方合法授权使用。

11.

求最小正整数 nn,使得 3n3^n 写成 143143 进制时,其最右边两位 143143 进制数字为 0101

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.

答案:195
知识点:乘法阶模运算二项式定理最小公倍数
难度评级:2990
小提示:

条件等价于 3n1(mod1432)3^n \equiv 1 \pmod{143^2};分别模 11211^213213^2 处理,并注意 35=243=2112+13^5 = 243 = 2 \cdot 11^2 + 1

The condition says 3n1(mod1432);3^n \equiv 1 \pmod{143^2}; work modulo 11211^2 and 13213^2 separately, noting 35=243=2112+13^5 = 243 = 2 \cdot 11^2 + 1

大提示:

由于 33=1+2133^3 = 1 + 2 \cdot 13,二项式定理给出 33k1+26k(mod132)3^{3k} \equiv 1 + 26k \pmod{13^2};确定何时它为 11,再取最小公倍数

Since 33=1+213,3^3 = 1 + 2 \cdot 13, the binomial theorem gives 33k1+26k(mod132);3^{3k} \equiv 1 + 26k \pmod{13^2}; determine when this is 1,1, then take an lcm

解答:

最后两个 143143 进制数字为 0101,恰好等价于 3n1(mod1432)3^n \equiv 1 \pmod{143^2}。由于 1432=112132143^2 = 11^2 \cdot 13^2,这又等价于 3n13^n \equiv 1 在模 11211^2 与模 13213^2 下同时成立。

12112135=243=2121+113^5 = 243 = 2 \cdot 121 + 1 \equiv 1,且由于 55 是质数、3≢13 \not\equiv 133 的阶恰为 55。模 169169331313 的阶为 33,所以模 169169 的阶是 33 的倍数。写 33=27=1+263^3 = 27 = 1 + 26,并注意 262=41690(mod169)26^2 = 4 \cdot 169 \equiv 0 \pmod{169},二项式定理给出 33k=(1+26)k3^{3k} = (1 + 26)^k 1+26k(mod169)\equiv 1 + 26k \pmod{169},它等于 11 当且仅当 kk1313 的倍数。所以 33169169 的阶为 3939

因此 nn 必须是 553939 的公倍数,最小为 lcm(5,39)=195\operatorname{lcm}(5, 39) = 195

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 kk is a multiple of 13.13. 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.

第 10 题#10
完整试卷

其他年份的第 11 题