Question

求最小正整数 $n$ ，使得 $3^n$ 写成 $143$ 进制时，其最右边两位 $143$ 进制数字为 $01$ 。

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

答案

答案：195

知识点：乘法阶模运算二项式定理最小公倍数

难度评级：2990

解答：

最后两个 $143$ 进制数字为 $01$ ，恰好等价于 $3^n \equiv 1 \pmod{143^2}$ 。由于 $143^2 = 11^2 \cdot 13^2$ ，这又等价于 $3^n \equiv 1$ 同时在模 $11^2$ 与 $13^2.$ 下成立。

模 $121$ ： $3^5 = 243 = 2 \cdot 121 + 1 \equiv 1$ ，且由于 $5$ 是质数、 $3 \not\equiv 1$ ， $3$ 的阶恰为 $5$ 。模 $169$ ： $3$ 模 $13$ 的阶为 $3$ ，所以模 $169$ 的阶是 $3$ 的倍数。写 $3^3 = 27 = 1 + 26$ ，并注意 $26^2 = 4 \cdot 169 \equiv 0 \pmod{169}$ ，二项式定理给出 $3^{3k} = (1 + 26)^k$ $\equiv 1 + 26k \pmod{169}$ ，它等于 $1$ 当且仅当 $13 \mid k$ 。所以 $3$ 模 $169$ 的阶为 $39$ 。

因此 $n$ 必须是 $5$ 与 $39$ 的公倍数，最小为 $\operatorname{lcm}(5, 39) = 195$ 。

The last two base- $143$ digits are $01$ exactly when $3^n \equiv 1 \pmod{143^2},$ and since $143^2 = 11^2 \cdot 13^2,$ this holds exactly when $3^n \equiv 1$ modulo both $11^2$ and $13^2.$

Modulo $121:$ $3^5 = 243 = 2 \cdot 121 + 1 \equiv 1,$ and since $5$ is prime and $3 \not\equiv 1,$ the order of $3$ is exactly $5.$ Modulo $169:$ the order of $3$ modulo $13$ is $3,$ so the order modulo $169$ is a multiple of $3.$ Writing $3^3 = 27 = 1 + 26$ and noting $26^2 = 4 \cdot 169 \equiv 0 \pmod{169},$ the binomial theorem gives $3^{3k} = (1 + 26)^k$ $\equiv 1 + 26k \pmod{169},$ which is $1$ exactly when $13 \mid k.$ So the order of $3$ modulo $169$ is $39.$

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

2018 AIME I 第 11 题

答案：195

难度评级：2990

解答：

其他年份的第 11 题