合同式の基本的な性質（加減乗除・べき乗）

今回は、合同式の基本的な性質として、合同式の加減乗除・べき乗について見ていきます。

例えば、「\({2}^{2025}\) を \(17\) で割った余りを求めよ」のような問題が出たとき、まさか、実際に、\(2\) を \(2025\) 乗するわけにはいきません。。。（コンピュータを使ってもメチャメチャ大変です）

そんな時に使えるのが「合同式」で、\({2}^{2025}\) 自体はわかりませんが、それを \(17\) で割った余りなら、すぐに計算できてしまうという、非常に便利なものです。

\[\begin{alignat*}{3}
{2}^{2025}&={({2}^{4})}^{506}\cdot {2}^{1} \\
&={16}^{506}\cdot 2 \\
&\equiv {(-1)}^{506}\cdot 2\pmod {17} \\
&=1\cdot 2 \\
&\equiv 2\pmod {17}
\end{alignat*}\]

\[\therefore\ {2}^{2025}\ を\ 17\ で割った余りは、2\]

この「合同式」は、特に、整数の性質に関する証明で利用することが多く、みなさんも、合同式の加減乗除・べき乗の性質を利用して、証明問題などを解いたことがあるのではないでしょうか。

ただ、そもそも、「その性質が、なぜ成立するのか？」と言われると、少々自信のない方も結構いらっしゃるのではないかと思います。

今回は、そんな「合同式の加減乗除・べき乗」について、なぜそのような計算をしてもよいのか、という部分を丁寧に見ていきます。
この解説を通じて、証明問題などで、自信をもって合同式を利用できるようになっていただければ、とてもうれしいです！

それでは解説に入ります。

解説

（復習）合同式の定義

今回の解説では、合同式の定義を利用して各関係を導いていくため、先に、「合同式の定義」について復習しておきます。

合同式の加法・減法

まずは、加法と減法について見ていきます。

整数 \(a，b，c，d\)、自然数 \(n\) に対して、\(a\equiv b\)、\(c\equiv d\pmod n\) が成り立っているとします。

このとき、合同式の定義より、整数 \(k，l\) を用いて、以下のように書くことができます。

\[\begin{alignat*}{3}
a-b&=kn&\quad・・・① \\
c-d&=ln&・・・②
\end{alignat*}\]

①②の両辺をそれぞれ足し合わせると、

\[\begin{alignat*}{3}
&(a-b)+(c-d)=kn+ln \\
\Leftrightarrow\ &(a+c)-(b+d)=(k+l)n
\end{alignat*}\]

\(k，l\) は整数のため、\((k+l)\) も整数であることに注意すると、合同式の定義より、\(a+c\equiv b+d\pmod n\) となり、加法の場合について成立することを確認できました。

同様に、①ー②を考えると、

\[\begin{alignat*}{3}
&(a-b)-(c-d)=kn-ln \\
\Leftrightarrow\ &(a-c)-(b-d)=(k-l)n
\end{alignat*}\]

したがって、\(a-c\equiv b-d\pmod n\) となり、減法についても確認できました。

合同式の乗法

次に、乗法を見ていきます。

整数 \(a，b，c，d\)、自然数 \(n\) に対して、\(a\equiv b\)、\(c\equiv d\pmod n\) が成り立っているとすると、整数 \(k，l\) を用いて、以下のように書くことができます。

\[\begin{alignat*}{3}
a-b&=&kn\ \Leftrightarrow\ a&=&b+kn&\quad&・・・③ \\
c-d&=&ln\ \Leftrightarrow\ c&=&d+ln&&・・・④
\end{alignat*}\]

③④の両辺をそれぞれ掛け算すると、

\[\begin{alignat*}{3}
ac&=(b+kn)(d+ln) \\
&=bd+(bl+dk+kln)\cdot n
\end{alignat*}\]

\[\therefore\ ac-bd=(bl+dk+kln)\cdot n\]

\(b，d，k，l\) は整数、\(n\) は自然数のため、\((bl+dk+kln)\) も整数であることに注意すると、合同式の定義より、\(ac\equiv bd\pmod n\) となり、乗法の場合について確認できました。

合同式のべき乗

次は、べき乗です。

こちらは、合同式の乗法が成り立つことから明らかで、乗法で得られた、\(ac\equiv bd\pmod n\) という式の \(c，d\) を各々 \(a，b\) に置き換えると、

\[{a}^{2}\equiv {b}^{2}\pmod n\]

となります。
\(a\equiv b\pmod n\) なので、この式の両辺に、さらに、各々 \(a，b\) を掛け算すると、合同式の乗法の性質より、

\[{a}^{3}\equiv {b}^{3}\pmod n\]

・・・と、これを繰り返せば、任意の自然数 \(k\) に対して、

\[{a}^{k}\equiv {b}^{k}\pmod n\]

が得られます。

※本来は、数学的帰納法を用いた証明が必要ですが、合同式の乗法を認めると、ほぼ自明なため、今回は簡易的な確認にとどめています。

合同式の除法　※注意点アリ

最後に、除法の場合を考えます。

整数 \(a，b，c\)、自然数 \(n\) に対して、\(ac\equiv bc\pmod n\) が成り立っているとすると、整数 \(k\) を用いて、

\[\begin{alignat*}{3}
&ac-bc=kn \\
&\Leftrightarrow\ (a-b)c=kn
\end{alignat*}\]

と書けます。

ここで、背理法を用いて、\(c\) と \(n\) が互いに素の場合に、\((a-b)\) が \(n\) の倍数であることを確認します。

\(c\) と \(n\) が互いに素の場合に、\((a-b)\) が \(n\) の倍数でないと仮定すると、

左辺の \(a-b，c\) は、いずれも \(n\) の倍数でない

ことになり、それらを掛け合わせた

左辺は、全体で \(n\) の倍数ではないことになります。

一方で、右辺は、整数 \(k\) と、自然数 \(n\) の積であり、明らかに \(n\) の倍数のため、矛盾を導けました。

したがって、\(c\) と \(n\) が互いに素の場合、\(a-b\) が \(n\) の倍数であり、整数 \(m\) を用いて以下のように書くことができます。

\[a-b=mn\]

合同式の定義より、\(a\equiv b\pmod n\) となるため、除法の場合について確認できました。

上の証明をご覧いただいたら分かるように、除法の場合は、「\(c\) と \(n\) が互いに素の場合」という条件が付くことがポイントになります。

実際に、例えば、\(6\) と \(15\) を考えると、

• \(6=0\cdot 9+6\)
• \(15=1\cdot 9+6\)

となり、\(6\equiv 15\pmod {9}\) となります。

一方で、\(6\) と \(15\) の共通因数 \(3\) でこれらを割り算した \(2\) と \(5\) は、\(9\) が \(3\) を因数に持つため、法 \(9\) において合同ではありません。

おわりに

今回は、合同式の基本的な性質として、合同式の加減乗除・べき乗を見てきました。

それぞれの証明をご覧いただければ、これらの演算ができるのは、そりゃそうだよね！と理解いただけたと思います。

特に、除法については、「割る数と、法が互いに素である」という条件が付加されており、この部分をニガテとする方が結構いらっしゃる気がします。
今回の証明の流れを理解すれば、もし忘れてしまっても、この条件を、その場で適切に設定できると思います。

腹落ちするまで何度も読み返して、ぜひ合同式を、みなさんの強力な武器にしてください！