3の2024乗を100で割った余り(位数)

方針

解答

⓪ 発想 — どう考え始めるか。 $3^{2024}$ を直接計算するのは論外だ。だが求めるのは「$100$ で割った余り」だけ。余りの世界では、$3$ のべきはいつか必ず $1$ に戻り、そこから同じ列を繰り返す。

そこで $3^k\equiv 1(\mathrm{mod}100)$ となる最小の $k$(位数)を探す。周期が分かれば、指数 $2024$ をその周期で割った余りに置き換えられる。

巨大な指数を「周期で折りたたむ」。これが位数の考え方だ。

① 位数を求める。 $\mathrm{mod}100$ で $$3^1=3,3^2=9,3^4=81,3^5=243\equiv 43,3^{10}\equiv 43^2=1849\equiv 49,3^{20}\equiv 49^2=2401\equiv 1.$$ よって位数は $20$($3^{20}\equiv 1$)。

② 指数を周期で割る。 $2024=20\times 101+4$ だから $$3^{2024}=(3^{20}{)}^{101}\cdot 3^4\equiv 1^{101}\cdot 3^4=3^4(\mathrm{mod}100).$$ ③ 余り。 $3^4=81$。よって $3^{2024}$ を $100$ で割った余りは $81$。

まとめ $3$ のべきは $\mathrm{mod}100$ で周期 $20$($3^{20}\equiv 1$)。$2024\equiv 4(\mathrm{mod}20)$ だから $3^{2024}\equiv 3^4=81$。整数(合同)・位数・周期の融合。

発展 — 一歩先へ。 $1\sim 100$ で $100$ と互いに素な数はちょうど $40$ 個あり、$3$ の位数 $20$ はこの $40$ の約数になっている。「位数は全体の個数の約数」という関係は一般に成り立ち、位数の候補を絞る道具になる(オイラーの定理への入り口)。

別解

別解 — $100=4\times 25$ に分けて別々に攻める(得意な人向けの高い視点)。 $\mathrm{mod}100$ の代わりに、互いに素な $\mathrm{mod}4$ と $\mathrm{mod}25$ で別々に余りを求め、最後に合体させる。

$\mathrm{mod}4$ では $3\equiv -1$ だから、$3^{2024}\equiv (-1{)}^{2024}=1$。

$\mathrm{mod}25$ では $3$ のべきを追うと $3^{20}\equiv 1$(周期 $20$)。$2024=20\cdot 101+4$ より $3^{2024}\equiv 3^4=81\equiv 6(\mathrm{mod}25)$。

「$25$ で割ると $6$ 余る」$0\sim 99$ の数は $6,31,56,81$ の $4$ つ。このうち「$4$ で割ると $1$ 余る」のは $81$ だけ。よって $3^{2024}\equiv 81(\mathrm{mod}100)$。

法を素因数のかたまりに分けると、周期探しが小さな世界($\mathrm{mod}25$)で済む。大きな法を分解して各個撃破する手は、ほかの合同式の問題でも広く効く。