数学II / 指数関数・対数関数

7の累乗を100で割った余り

最難関編累乗合同

問題

$7^{100}$ を $100$ で割った余りを求めよ。

ヒントを見る

直接計算は無理。 $100$ を法として $7^{2}, 7^{4}, \dots$ を計算し、 $1$ に戻る周期を探す。

解答・解説

方針

$100$ を法とした $7$ のべきの周期を調べる。 $7^{4} \equiv 1 (mod 100)$ がわかれば $100 = 4 \cdot 25$ で一気に出る。

解答

⓪ 発想 — どう考え始めるか。 $7^{100}$ を正面から計算するのは無理だ。だが「 $100$ で割った余り」だけなら、掛け算のたびに余りへ戻してよい(合同式)。

余りの世界は有限だから、 $7$ のべきの余りはいずれ必ず繰り返す。まず $7^{2}, 7^{4}, \dots$ と計算して、 $1$ に戻る周期を探す。

$7^{4} = 2401$ で早くも $1$ に戻る。あとは指数 $100$ を $4$ のかたまりに分ければ、一気に落ちる。

定理合同

a \equiv b (mod m)

はべき乗でも保たれる:

a^{k} \equiv b^{k} (mod m)

① 周期を見つける。 $7^{2} = 49$ 、 $7^{4} = 4 9^{2} = 2401 = 24 \cdot 100 + 1 \equiv 1 (mod 100)$ 。 $7^{4} \equiv 1$ (周期 $4$ )。

② 指数を周期でまとめる。 $100 = 4 \cdot 25$ だから

$7^{100} = (7^{4})^{25} \equiv 1^{25} = 1 (mod 100)$

余りは $1$ 、下 $2$ 桁は $01$ 。

まとめ: $7^{4} \equiv 1 (mod 100)$ (周期 $4$ )を見つけるのが急所。指数を $4$ でくくれば $1$ に落ちる。指数(累乗)と整数(合同)の融合。

発展 — 一歩先へ。 $1$ に戻る最小の指数(位数)は、勝手な値を取れない。 $1$ から $100$ のうち $100$ と互いに素な数はちょうど $40$ 個あり、位数は必ずこの $40$ の約数になる(オイラーの定理)。 $7$ の位数 $4$ も $40$ の約数だ。「 $40$ の約数の指数だけ試せばよい」という高速の周期探しにつながる。

答

$1$ (下 $2$ 桁は $01$ )

別解

法を分けて合わせる( $4$ と $25$ に分解)。 $100 = 4 \cdot 25$ で、 $4$ と $25$ は互いに素。そこで余りを別々に調べて、最後に合体させる。

$4$ を法にすると、 $7 \equiv - 1$ だから

$7^{100} \equiv (- 1)^{100} = 1 (mod 4)$

$25$ を法にすると、 $7^{2} = 49 \equiv - 1$ だから

$7^{100} = (7^{2})^{50} \equiv (- 1)^{50} = 1 (mod 25)$

つまり $7^{100} - 1$ は $4$ の倍数であり、 $25$ の倍数でもある。 $4$ と $25$ は互いに素だから、 $7^{100} - 1$ は $100$ の倍数。よって余りは $1$ 。

周期を1本で見つける(本解)か、法を小さなパーツに割って別々に倒す(本ルート)か。法が大きいほど分解ルートの計算は軽くなる。 $49 \equiv - 1 (mod 25)$ のような「 $- 1$ の発見」が、このルートの快感だ。

ポイント

$7^{4} \equiv 1 (mod 100)$ (周期4)。
$100 = 4 \cdot 25$ で $7^{100} \equiv 1$ 。

よくある間違い

$7^{2} = 49$ の段階で $1$ に戻らないのを見て周期探しをあきらめる。 $4 9^{2} = 2401$ は暗算圏内で、 $7^{4}$ で戻る。
指数の分解 $100 = 4 \cdot 25$ と、法の $100$ を混同する。周期 $4$ は「 $4$ 乗ごとに余りが $1$ に戻る」ことで、法の $100$ とは別の数。
合同式の途中で法を黙って変える。全編 $mod 100$ で通すか、法を分けるなら最後に「互いに素だから合体できる」の一段を明示する。