数学塾variée@吉祥寺

数学塾の中の人の日記

2018 AIME 第11問

2018年の AIME の第11問を解きました。

 3^n を 143 進法であらわしたとき,下 2 桁が 01 になるような自然数  n の最小値を求めよ。

https://artofproblemsolving.com/community/c5h1604138p9995346

与えられた条件を合同式を使ってあらわすと,こうなります。

 3^n\equiv 1\pmod{143^2}

これだと法が大きすぎてお手上げですが, 3^n-1\equiv 0\pmod{143^2} と変形して,

 3^n-1 143^2=11^2\cdot 13^2 で割り切れる」

と解釈するとだいぶ易しくなります。この条件は次と同値です。

 3^n-1\equiv 0\pmod{11^2} かつ  3^n-1\equiv 0\pmod{13^2}

これをどう処理するかは pdf を見てください。
一旦  \bmod\, 13 で考えた後,二項定理を使って  \bmod\, 13^2 に直したりします。

www.dropbox.com


要するに  p, q を互いに素な数として

 x pq で割った余りは 1」
=「 x-1 pq で割り切れる」
=「 x-1 p でも  q でも割り切れる」

と変形して解いたわけです。「余り0」は「余り1」よりずっと扱いやすい,という問題でした。