合同式(3)

今回は、合同式の累乗を見ていきます。

つまり、$${k}$$を正整数として$${a \equiv b \mod n}$$のとき$${a^k \equiv b^k \mod n}$$が成り立つかを調べます。

合同式の辺辺同士の掛け算の性質を応用すれば成立を導けますが、今回はもう少し工夫して成立を証明します。

$${(a - b) (a^{k-1}b + a^{k-2}b^2 + \dots + ab^{k-1})}$$を展開すると$${a^k - b^k}$$となります。

逆に言うと、$${a^k - b^k}$$を因数分解すると$${(a - b) (a^{k-1}b + a^{k-2}b^2 + \dots + ab^{k-1})}$$となります。

今、$${a \equiv b \mod n}$$が成り立つならば合同式の定義から$${a - b}$$は$${n}$$の倍数です。

したがって、$${(a - b) (a^{k-1}b + a^{k-2}b^2 + \dots + ab^{k-1})}$$も$${n}$$の倍数です。

よって、$${a^k - b^k}$$も$${n}$$の倍数、つまり合同式の定義から$${a^k \equiv b^k \mod n}$$です。

この定理を用いると、例えば$${7^{50}}$$を$${6}$$で割った余りを素早く求められます。

前知識がない状態で解こうとすると、$${7^{50}}$$を計算し、結果を$${6}$$で割って余りを求めることになります。

$${7^{50}}$$は$${1798465042647412146620280340569649349251249}$$であり、$${6}$$で割ると商が$${299744173774568691103380056761608224875208}$$で余りが$${1}$$となります。

先ほど紹介した合同式の性質を用いると
$${7 \equiv 1 \mod 6}$$なので$${7^{50} \equiv 1^{50} \mod 6}$$
等式として$${1^{50} =1 }$$なので$${7^{50} \equiv 1 \mod 6}$$
余りが$${1}$$であることを求められます。