合同式を使った余りの計算

大きなべき乗の余りを直接計算するのは大変です。 $7^{100}$ を 5 で割った余りを求めようとして、 $7^{100}$ を実際に計算するわけにはいきません。合同式を使えば、このような計算を効率的に行えます。

合同式の基本

$a$ と $b$ を $n$ で割った余りが等しいとき、 $a \equiv b (mod n)$ と書きます。合同式には次の性質があります。

加法

$a \equiv b$ 、 $c \equiv d$ ならば $a + c \equiv b + d$

乗法

$a \equiv b$ 、 $c \equiv d$ ならば $a c \equiv b d$

べき乗

$a \equiv b$ ならば $a^{k} \equiv b^{k}$

特に重要なのは、計算の途中で余りを取ってよいという点です。これにより、数を小さく保ちながら計算を進められます。

基本的な解法

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

まず、7 を 5 で割った余りは 2 なので $7 \equiv 2 (mod 5)$ です。

$7^{100} \equiv 2^{100} (mod 5)$

次に、 $2^{4} = 16 \equiv 1 (mod 5)$ に注目します。

$100 = 4 \times 25$ なので

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

よって、余りは 1 です。

繰り返し二乗法

指数が大きいときは、繰り返し二乗法が便利です。 $3^{50}$ を 7 で割った余りを求めます。

指数を 2 進法で表す： $50 = 32 + 16 + 2 = 11001 0_{(2)}$

$3^{1}, 3^{2}, 3^{4}, 3^{8}, 3^{16}, 3^{32}$ を順に計算（余りを取りながら）

必要な項を掛け合わせる

$3^{1} \equiv 3 (mod 7)$

$3^{2} \equiv 9 \equiv 2 (mod 7)$

$3^{4} \equiv 2^{2} = 4 (mod 7)$

$3^{8} \equiv 4^{2} = 16 \equiv 2 (mod 7)$

$3^{16} \equiv 2^{2} = 4 (mod 7)$

$3^{32} \equiv 4^{2} = 16 \equiv 2 (mod 7)$

$3^{50} = 3^{32} \times 3^{16} \times 3^{2} \equiv 2 \times 4 \times 2 = 16 \equiv 2 (mod 7)$

よって、余りは 2 です。

周期性を利用する方法

べき乗の余りは周期的になることが多いです。 $2^{n}$ を 7 で割った余りの列を見てみましょう。

$2^{1}$	2
$2^{2}$	4
$2^{3}$	1
$2^{4}$	2
$2^{5}$	4
$2^{6}$	1

周期 3 で繰り返しています。 $2^{100}$ を 7 で割った余りは、 $100 \div 3 = 33$ 余り $1$ なので、 $2^{1} \equiv 2$ と同じです。

フェルマーの小定理との組み合わせ

$p$ が素数で $a$ が $p$ の倍数でないとき、 $a^{p - 1} \equiv 1 (mod p)$ が成り立ちます。

$5^{1000}$ を 7 で割った余りを求めます。

$7$ は素数で、 $5$ は $7$ の倍数でないので

$5^{6} \equiv 1 (mod 7)$

$1000 = 6 \times 166 + 4$ なので

$5^{1000} = (5^{6})^{166} \times 5^{4} \equiv 1 \times 5^{4} (mod 7)$

$5^{2} = 25 \equiv 4 (mod 7)$

$5^{4} \equiv 4^{2} = 16 \equiv 2 (mod 7)$

よって、余りは 2 です。

小さな指数

直接計算するか、周期を見つける

大きな指数

フェルマーの小定理や繰り返し二乗法を使う

合同式を使いこなせば、手計算でも非常に大きなべき乗の余りを求められます。