合同式の性質を使った整数の余りの計算方法

どうも、木村（@kimu3_slime）です。

突然ですが、\(2021 ^{20}\)を\(7\)で割った余りを求めることはできますか？　原理的にはできますが、実際の計算は大変そうです。

今回はそんな計算が比較的簡単にできる方法として、合同式の性質を使った整数の余り、1の位の数の求め方を紹介します。

合同式とその性質
合同式の性質を使った計算例
こちらもおすすめ

合同式とその性質

\(8,15,22\)という整数は、余りが\(1\)という点では共通しています。この関係性を\(8 \equiv 15 \equiv 22 \,(\mathrm{mod} 7)\)と表せると、単純で便利です。

2つの数\(x,y\)の差\(x-y\)が整数\(n\)の倍数であるとき、\(x,y\)は\(n\)を法として合同（congruent modulo \(n\)）と呼び、\(x\equiv y\, (\mathrm{mod}\, n)\)と表します。これは合同算術、合同式、モジュラー算術、モッドとも呼ばれるものです。

参考：倍数同士の和は同じ倍数となること、整数の合同modとは

この定義は、\(x,y\)を\(n\)で割ったときの余りが等しいことと同値です。

確かめてみましょう。\(x-y=nk\)となる整数\(k\)が存在したと仮定します。\(y\)を\(n\)で割ると、除法の原理より、\(y=q_y n +r_y\)と表せます。これらを合わせれば、\(x=nk+y=(k+q_y)n + r_y\)です。除法の原理（あまりの一意性）より、\(r_y\)が\(x\)を\(n\)で割ったあまりに等しいことがわかりました。

逆に、\(x,y\)を\(n\)で割った余りが等しいと仮定します。すなわち、\(x=q_x n+r\)、\(y=q_y n+r\)と仮定します。すると、\(x-y=(q_x-q_y)n\)で、\(q_x- q_y\)は整数なので、差が\(n\)の倍数となることがわかりました。

つまり、\(x\)を\(n\)で割ったあまりが\(r\)であることは、\(x \equiv r \,(\mathrm{mod} \,n)\)と言い換えられます。\(x\)が\(n\)で割り切れることは、あまりが\(r=0\)、\(x \equiv 0 \,(\mathrm{mod} \,n)\)というわけです。

整数の合同には、普通の等号\(=\)と似た、便利な性質があります。基本的な性質は、同値関係の性質として紹介しました。

\(n,a,b,c,d\)を整数、\(k\)を正の整数とする。

\(a \equiv b \,(\mathrm{mod}\,n)\),\(c \equiv d \,(\mathrm{mod}\,n)\)ならば、\(a+c \equiv b+d \,(\mathrm{mod}\,n)\)であり、\(ac \equiv bd \,(\mathrm{mod}\,n)\)である。
\(a \equiv b \,(\mathrm{mod}\,n)\)ならば、\(a+c \equiv b+c \,(\mathrm{mod}\,n)\)であり、\(ac \equiv bc \,(\mathrm{mod}\,n)\)である。
\(a \equiv b \,(\mathrm{mod}\,n)\)ならば、\(a^k \equiv b^k \,(\mathrm{mod}\,n)\)である。

確かめましょう。

1.について。\(a \equiv b \,(\mathrm{mod}\,n)\),\(c \equiv d \,(\mathrm{mod}\,n)\)より、\(a -b=\ell n\),\(c -d=m n\)となる整数\(\ell,m\)が存在します。

\(a+c -(b+d)=a-b+c-d= (\ell+m) n\)なので、\(a +c\equiv b+d \,(\mathrm{mod}\,n)\)が成り立ちます。また、\(ac-bd=c(a-b)+b(c-d)\\=c\ell n+b mn =(c\ell +bm)n\)なので、\(ac \equiv bd \,(\mathrm{mod}\,n)\)が成り立ちます。

2.について。1.において、\(d=c\)のケースを考えたときそのものです。

3.について。\(a^k \equiv b^k \,(\mathrm{mod}\,n)\)であることを、\(k\)に関する数学的帰納法で示しましょう。\(k=1\)のとき、\(a^k \equiv b^k \,(\mathrm{mod}\,n)\)は仮定そのものであり成り立ちます。\(k=m\)のとき\(a^m \equiv b^m \,(\mathrm{mod}\,n)\)が成り立つと仮定して、\(k=m+1\)での成立を確かめましょう。\(a \equiv b \,(\mathrm{mod}\,n)\)なので、1.の積に関する性質を用いると、\(a^m \cdot a \equiv b^m \cdot b \,(\mathrm{mod}\,n) \)が成り立ちます。すなわち、\(a^{m+1} \equiv b^{m+1} \,(\mathrm{mod}\,n)\)が成り立つことが示せました。

合同式の性質を使った計算例

\(2021 ^{20}\)を\(7\)で割った余りを求めてみましょう。整数の合同で言えば、\(x \equiv 2021^{20}\,(\mathrm{mod}\,7) \)を求めることです。

\(2021=1400+560+56+5\)なので、\(2021 \equiv 5\,(\mathrm{mod}\,7) \)です。整数の合同の性質より、\(2021^{20} \equiv 5 ^{20}\,(\mathrm{mod}\,7) \)となります。\(25 \equiv 4 \,(\mathrm{mod}\,7)\)なので、整数の合同の性質より、\(5^{20} \equiv ({5^2})^{10}\equiv 4^{10} \,(\mathrm{mod}\,7) \)です。\(16 \equiv 2 \,(\mathrm{mod}\,7)\)なので、整数の合同の性質より\(4^{10} \equiv ({4^2})^{5}\equiv 2^{5} \,(\mathrm{mod}\,7) \)です。そして、\(2^5=32\)なので、\(2^{5} \equiv 4 \,(\mathrm{mod}\,7)\)。以上によって、\(2021^{20}\equiv 4 (\mathrm{mod}\,7)\)がわかりました。

大きな数のべき乗を、どんどん小さな数のべき乗と「あまりは等しい（合同）」と言い換えていくことで、最終的に手計算レベルの式に落とし込むことができる。これはとても便利です。

次いで、\(2021 ^{20}\)の1の位の数を求めてみましょう。それはすなわち、\(10\)で割った余りは何か、\(10\)を法として何に合同か、を求める問題です。

\(2021 \equiv 1\,(\mathrm{mod}\,10) \)なので、整数の合同の性質より、\(2021^{20} \equiv 1^{20} \equiv 1 \,(\mathrm{mod}\,10) \)です。よって、1の位の数は\(1\)であるとわかりました。

これを少し一般化すれば、次のことがわかります。\(a\)を\(10\)の倍数とするとき、\((a+1)^k\)の下1桁の数は1である。これは二項定理で展開して示すこともできますが、合同式を使っても簡単です。\(a+1 \equiv 1\,(\mathrm{mod}\,10) \)なので、整数の合同の性質より、\((a+1)^{k} \equiv 1^{k} \equiv 1 \,(\mathrm{mod}\,10) \)となります。

平方数のあまり（平方剰余）については、例えば次のことがわかります。

\(x\)を整数とする。\(x^2\)を3で割ったあまりは0または1である。\(x^2\)を4で割ったあまりは0または1である。

\(x\)を\(3\)で割ったあまりを\(r\)とすると、\(x \equiv r\,(\mathrm{mod}\,3) \)です。合同の性質より、\(x^2 \equiv r^2 \,(\mathrm{mod}\,3) \)となります。あまり\(r\)の可能性としては、\(0,1,2\)の可能性があるので、それぞれのときの\(x^2\)のあまりを調べましょう。\(0^2 \equiv 0\,(\mathrm{mod}\,3) \),\(1^2 \equiv 1\,(\mathrm{mod}\,3) \),\(2^2 \equiv 1\,(\mathrm{mod}\,3) \)なので、\(x^2\)のあまりは0または1であることがわかりました。

\(x\)を\(4\)で割ったあまりについても、同様に調べられます。あまりの可能性は、\(0,1,2,3\)です。\(0^2 \equiv 0\,(\mathrm{mod}\,4) \),\(1^2 \equiv 1\,(\mathrm{mod}\,4) \),\(2^2 \equiv 0\,(\mathrm{mod}\,4) \),\(3^2 \equiv 1\,(\mathrm{mod}\,4) \)なので、\(x^2\)のあまりは0または1であることがわかりました。

平方数のあまりについては、平方剰余といった概念や、平方剰余の相互法則と呼ばれる定理が知られています。これは別記事にて紹介予定。

以上、合同式（mod）の性質を示した上で、それを活用してべき乗で表される数の余りを調べました。

手計算でべき乗を求めてからあまりを求めるのは大変です。大きな数が割り切れるか、あまりがどうなっているかという問題に出会ったら、合同式の性質を活用してみてください。

木村すらいむ（@kimu3_slime）でした。ではでは。