本項では以下の内容を解説しています。
本章では、合同式の意味について解説します。
合同式とは以下のように定義される式のことをいいます。
上記のような式を『\(\large{\hspace{1pt}a\hspace{2pt}}\)と\(\large{\hspace{1pt}b\hspace{2pt}}\)は\(\large{\hspace{1pt}m\hspace{2pt}}\)を法として合同である』といいます。
等号による式『\(\large{\hspace{1pt}a=b\hspace{2pt}}\)』は\(\large{\hspace{1pt}a\hspace{2pt}}\)と\(\large{\hspace{1pt}b\hspace{2pt}}\)の値が等しいことを意味します。
一方、合同式『\(\large{\hspace{1pt}a \equiv b\hspace{2pt}}\)』は\(\large{\hspace{1pt}a\hspace{2pt}}\)と\(\large{\hspace{1pt}b\hspace{2pt}}\)を\(\large{\hspace{1pt}m\hspace{2pt}}\)で割った余りが等しいことを意味します。
合同式の意味は『経過した時間』と『アナログ時計の時針の数字』の関係を考えると分かりやすいです。
例えば、午前\(\large{\hspace{1pt}0\hspace{2pt}}\)時を基準に『経過した時間』と『時計の時針の数字』を比較してみます。
午前\(\large{\hspace{1pt}0\hspace{2pt}}\)時から\(\large{\hspace{1pt}1\hspace{2pt}}\)時間後には、時計の時針は\(\large{\hspace{1pt}1\hspace{2pt}}\)時を指します。
さらに時間が経ち、午前\(\large{\hspace{1pt}0\hspace{2pt}}\)時から\(\large{\hspace{1pt}13\hspace{2pt}}\)時間だけ経過すると、時計の時針は一周して再び\(\large{\hspace{1pt}1\hspace{2pt}}\)時を指します。
なぜ時計の時針が同じ数字を示すのかというと、時計の時針は一周が\(\large{\hspace{1pt}12\hspace{2pt}}\)時間であることから、時針は『経過した時間を\(\large{\hspace{1pt}12\hspace{2pt}}\)で割った余り』の数字を指すためです。
経過した時間を\(\large{\hspace{1pt}12\hspace{2pt}}\)で割った余りを計算すると
午前\(\large{\hspace{1pt}0\hspace{2pt}}\)時から\(\large{\hspace{1pt}1\hspace{2pt}}\)時間後は
$$\large{1 \div 12 = 0 \hspace{5pt} \rm{余り}\hspace{3pt}\color{red}{1}}$$
午前\(\large{\hspace{1pt}0\hspace{2pt}}\)時から\(\large{\hspace{1pt}13\hspace{2pt}}\)時間後は $$\large{13 \div 12 = 1 \hspace{5pt} \rm{余り}\hspace{3pt}\color{red}{1}}$$ であることから、\(\large{1\hspace{2pt}}\)と\(\large{\hspace{1pt}13\hspace{2pt}}\)は\(\large{\hspace{1pt}12\hspace{2pt}}\)で割った余りが\(\large{\hspace{1pt}1\hspace{2pt}}\)であるので、\(\large{1\hspace{2pt}}\)時間後と\(\large{\hspace{1pt}13\hspace{2pt}}\)時間後は同じ\(\large{\hspace{1pt}1\hspace{2pt}}\)時を指すと考えることができます。
この関係を合同式で表すと $$\large{1 \equiv 13 \pmod {12}}$$ と表すことができます。
ここで、さらに時間が経過した場合を考えると、午前\(\large{\hspace{1pt}0\hspace{2pt}}\)時から\(\large{\hspace{1pt}25\hspace{2pt}}\)時間後は $$\large{25 \div 12 = 2 \hspace{5pt} \rm{余り}\hspace{3pt}\color{red}{1}}$$ であることから、\(\large{1\hspace{2pt}}\)と\(\large{\hspace{1pt}13\hspace{2pt}}\)と\(\large{\hspace{1pt}25\hspace{2pt}}\)は\(\large{\hspace{1pt}12\hspace{2pt}}\)で割った余りが\(\large{\hspace{1pt}1\hspace{2pt}}\)となるので、\(\large{1\hspace{2pt}}\)時間後と\(\large{\hspace{1pt}13\hspace{2pt}}\)時間後と\(\large{\hspace{1pt}25\hspace{2pt}}\)時間後は同じ\(\large{\hspace{1pt}1\hspace{2pt}}\)時を指すと考えることができます。
この関係を合同式で表すと $$\large{1 \equiv 13 \equiv 25 \pmod {12}}$$ と表すことができます。
このように、合同式 $$\large{a \equiv b \pmod {12}}$$ は一周の数字の数が\(\large{\hspace{1pt}12\hspace{2pt}}\)個である時計で、同じ数字を指す経過時間\(\large{\hspace{1pt}a\hspace{2pt}}\)と\(\large{\hspace{1pt}b\hspace{2pt}}\)を『\(\large{\hspace{1pt}\equiv\hspace{2pt}}\)』の記号で結んでいると考えると分かりやすいです。
さらに、一般的に言えば $$\large{a \equiv b \pmod m}$$ は一周の目盛りの数が\(\large{\hspace{1pt}m\hspace{2pt}}\)個の測定器を使って、同じ数字を指す量\(\large{\hspace{1pt}a\hspace{2pt}}\)と\(\large{\hspace{1pt}b\hspace{2pt}}\)を『\(\large{\hspace{1pt}\equiv\hspace{2pt}}\)』の記号で結んでいると考えると分かりやすいです。
合同式が非常に便利な理由として、あらゆる任意の整数を余りの等しい数字同士にまとめることができるという点にあります。
整数\(\large{\hspace{1pt}-4\hspace{2pt}}\)から\(\large{\hspace{1pt}11\hspace{2pt}}\)までを\(\large{\hspace{1pt}4\hspace{2pt}}\)で割ったときの整数と余りの関係を表にします。
(負の整数を\(\large{\hspace{1pt}4\hspace{2pt}}\)で割った余りは\(\large{\hspace{1pt}-3 = -1 \times 4 +\color{red}{1}\hspace{2pt}}\)から余りが\(\large{\hspace{1pt}1\hspace{2pt}}\)などと求められます。)
| 整数 | \(\large{\hspace{1pt}4\hspace{2pt}}\)で割った余り |
|---|---|
| \(\large{\hspace{6pt}-4\hspace{2pt}}\) | \(\large{\hspace{1pt}0\hspace{2pt}}\) |
| \(\large{\hspace{6pt}-3\hspace{2pt}}\) | \(\large{\hspace{1pt}1\hspace{2pt}}\) |
| \(\large{\hspace{6pt}-2\hspace{2pt}}\) | \(\large{\hspace{1pt}2\hspace{2pt}}\) |
| \(\large{\hspace{6pt}-1\hspace{2pt}}\) | \(\large{\hspace{1pt}3\hspace{2pt}}\) |
| \(\large{\hspace{1pt}0\hspace{2pt}}\) | \(\large{\hspace{1pt}0\hspace{2pt}}\) |
| \(\large{\hspace{1pt}1\hspace{2pt}}\) | \(\large{\hspace{1pt}1\hspace{2pt}}\) |
| \(\large{\hspace{1pt}2\hspace{2pt}}\) | \(\large{\hspace{1pt}2\hspace{2pt}}\) |
| \(\large{\hspace{1pt}3\hspace{2pt}}\) | \(\large{\hspace{1pt}3\hspace{2pt}}\) |
| \(\large{\hspace{1pt}4\hspace{2pt}}\) | \(\large{\hspace{1pt}0\hspace{2pt}}\) |
| \(\large{\hspace{1pt}5\hspace{2pt}}\) | \(\large{\hspace{1pt}1\hspace{2pt}}\) |
| \(\large{\hspace{1pt}6\hspace{2pt}}\) | \(\large{\hspace{1pt}2\hspace{2pt}}\) |
| \(\large{\hspace{1pt}7\hspace{2pt}}\) | \(\large{\hspace{1pt}3\hspace{2pt}}\) |
| \(\large{\hspace{1pt}8\hspace{2pt}}\) | \(\large{\hspace{1pt}0\hspace{2pt}}\) |
| \(\large{\hspace{1pt}9\hspace{2pt}}\) | \(\large{\hspace{1pt}1\hspace{2pt}}\) |
| \(\large{\hspace{1pt}10\hspace{2pt}}\) | \(\large{\hspace{1pt}2\hspace{2pt}}\) |
| \(\large{\hspace{1pt}11\hspace{2pt}}\) | \(\large{\hspace{1pt}3\hspace{2pt}}\) |
表のように、整数を\(\large{\hspace{1pt}4\hspace{2pt}}\)で割った余りは\(\large{\hspace{1pt}0\hspace{2pt},\hspace{2pt}1\hspace{2pt},\hspace{2pt}2\hspace{2pt},\hspace{2pt}3\hspace{2pt}}\)で周期性を持つことが分かります。
表の値を参考に整数\(\large{\hspace{1pt}-4\hspace{2pt}}\)から\(\large{\hspace{1pt}11\hspace{2pt}}\)までの整数を合同式で整理すると \begin{eqnarray} \large 8 \equiv 4 \equiv 0 \equiv && \large -4\pmod 4 \\[0.5em] \large 9 \equiv 5 \equiv 1 \equiv && \large -3 \pmod 4 \\[0.5em] \large 10 \equiv 6 \equiv 2 \equiv && \large -2 \pmod 4 \\[0.5em] \large 11 \equiv 7 \equiv 3 \equiv && \large -1\pmod 4 \\[0.5em] \end{eqnarray} と表すことができます。
このように、合同式を利用することで任意の整数を余りの等しい数同士にまとめることができます。
合同式には、以下のような性質があります。
また以下のように、合同式の両辺に同じ数のたし算・引き算・かけ算なども可能です。
上記の合同式の性質は加法・減法・乗法について成り立ちますが、商(割り算)は成り立たない場合があることに注意が必要です。
合同式の商は以下のような条件付きで成り立ちます。
『\(\large{\hspace{1pt}k\hspace{2pt}}\)と\(\large{\hspace{1pt}m\hspace{2pt}}\)が互いに素』とは、\(\large{2\hspace{2pt}}\)つの整数に共通する約数が\(\large{\hspace{1pt}1\hspace{2pt}}\)以外に存在しないことをいいます。
本章では、合同式に関連する問題と解き方について解説します。
解答と解説 : 問題1
解答と解説 : 問題2
解答と解説 : 問題3
解答と解説 : 問題4
解答と解説 : 問題5
合同式の性質から『＝』で結ばれた等式と同様に移項することができます。
問題の合同式を変形すると $$\large{x\equiv 2-3 \pmod 7}$$ すなわち $$\large{x \equiv -1 \pmod 7}$$ ここで、\(\large{\hspace{1pt} -1 \equiv 6 \pmod 7\hspace{2pt}}\)であるから $$\large{x \equiv 6 \pmod 7}$$ となります。
\(\large{x\hspace{2pt}}\)に具体的な値を入れて、どの値であれば合同式が成り立つかを調べます。
求める\(\large{\hspace{1pt}x\hspace{2pt}}\)が\(\large{\hspace{1pt}7\hspace{2pt}}\)より小さい自然数であるので\(\large{\hspace{1pt}1\hspace{2pt},\hspace{2pt}2\hspace{2pt},\hspace{2pt}3\hspace{2pt},\hspace{2pt}4\hspace{2pt},\hspace{2pt}5\hspace{2pt},\hspace{2pt}6\hspace{2pt}}\)の場合それぞれで計算してみます。
| $$\large{x}$$ | $$\large{1}$$ | $$\large{2}$$ | $$\large{3}$$ | $$\large{4}$$ | $$\large{5}$$ | $$\large{6}$$ |
| $$\large{3x}$$ | $$\large{3}$$ | $$\large{6}$$ | $$\large{9 \equiv 2}$$ | $$\large{12 \equiv 5}$$ | $$\large{15 \equiv 1}$$ | $$\large{18 \equiv 4}$$ |
表より、\(\large{18 \equiv 4 \pmod 7\hspace{2pt}}\)であることから $$\large{x \equiv 6 \pmod 7}$$ となります。
合同式の性質を利用し、\(\large{x \equiv a \pmod m\hspace{2pt}}\)の形式に変形することもできます。
合同式の性質から\(\large{\hspace{2pt}3x \equiv 4 \pmod 7 \hspace{3pt}}\)の両辺に\(\large{\hspace{1pt}2\hspace{2pt}}\)をかけると $$\large{6x \equiv 8 \pmod 7}$$ ここで、\(\large{8 \equiv 1 \pmod 7\hspace{2pt}}\)であるので $$\large{6x \equiv 1 \pmod 7\hspace{5pt}\cdots (1)}$$
また、\(\large{7x\hspace{2pt}}\)を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りと、\(\large{7\hspace{2pt}}\)を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りは\(\large{\hspace{1pt}0\hspace{2pt}}\)となり等しいから $$\large{7x \equiv 7 \pmod 7\hspace{5pt}\cdots (2)}$$ が成り立ちます。
合同式の性質から、(2)式-(1)式を計算すると $$\large{7x-6x \equiv 7-1 \pmod 7}$$ つまり $$\large{x \equiv 6 \pmod 7}$$ と求められます。
この問題は以下の合同式の性質を利用して解きます。
上記の性質を利用すると 合同式が\(\large{\hspace{3pt}a \equiv 1 \pmod m\hspace{2pt}}\)のとき $$\large{a^n \equiv 1^n \pmod m}$$ となります。
ここで、\(\large{1^n = 1\hspace{2pt}}\)であるので $$\large{a^n \equiv 1 \pmod m}$$ となり、\(\large{a^n\hspace{2pt}}\)を\(\large{\hspace{1pt}m\hspace{2pt}}\)で割った余りが\(\large{\hspace{1pt}1\hspace{2pt}}\)と求めることができます。
\(\large{8^{100}\hspace{2pt}}\)の\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りを求める場合、まず\(\large{\hspace{1pt}8\hspace{2pt}}\)を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りを調べてみます。
\(\large{8\hspace{2pt}}\)を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りは\(\large{\hspace{1pt}1\hspace{2pt}}\)であるので $$\large{8 \equiv 1 \pmod 7}$$ と表されます。合同式の性質から上式を変形すると $$\large{8^{100} \equiv 1^{100} \pmod 7}$$ すなわち $$\large{8^{100} \equiv 1 \pmod 7}$$ となります。
よって、\(\large{8^{100}\hspace{2pt}}\)を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りは\(\large{\hspace{1pt}1\hspace{2pt}}\)となります。
前問では\(\large{\hspace{3pt}8 \equiv 1 \pmod 7\hspace{2pt}}\)と右辺が\(\large{\hspace{1pt}1\hspace{2pt}}\)の形にすぐ変形できたため、簡単に答えを求めることができました。
本問はこのような変形ができないため\(\large{\hspace{2pt}11^2\hspace{2pt},\hspace{2pt}}\)\(\large{11^3\hspace{2pt},\hspace{2pt}}\)\(\large{\hspace{1pt}11^4\hspace{2pt},\hspace{2pt}\cdots\hspace{3pt}}\)を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りを調べ、余りが\(\large{\hspace{1pt}1\hspace{2pt}}\)や\(\large{\hspace{1pt}-1\hspace{2pt}}\)となる数を探します。
\(\large{11\hspace{2pt}}\)を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りを調べると
$$\large{11 \equiv 4 \pmod 7}$$
\(\large{11^2\hspace{2pt}}\)を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りを調べると
$$\large{11^{2} \equiv 121 \equiv 2 \pmod 7}$$
\(\large{11^3\hspace{2pt}}\)を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りを調べると $$\large{11^{3} \equiv 1331 \equiv 1 \pmod 7}$$ となることから、\(\large{\hspace{1pt}11^3\hspace{2pt}}\)を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りが\(\large{\hspace{1pt}1\hspace{2pt}}\)となります。
すなわち $$\large{11^{100} \equiv 11\cdot(11^3)^{33} \equiv 11 \equiv 4 \pmod 7}$$
よって、\(\large{11^{100}\hspace{2pt}}\)を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りは\(\large{\hspace{1pt}4\hspace{2pt}}\)となります。
\(\large{\hspace{1pt}11\cdot(11^3)^{33} \equiv 11\hspace{2pt}}\)の変形は
合同式\(\large{\hspace{3pt}a \equiv b \pmod m\hspace{2pt},\hspace{2pt}c \equiv d \pmod m\hspace{3pt}}\)が成り立つとき
$$\large{\hspace{3pt}a\hspace{1pt}c \equiv b\hspace{1pt}d \pmod m}$$
が成り立つことを利用しています。
\(\large{\hspace{1pt}(11^3)^{33} \equiv 1 \pmod 7\hspace{2pt}}\)であることから $$\large{11\times (11^3)^{33} \equiv 11 \times 1}$$ となります。
前記の解法では、\(\large{11^2\hspace{2pt}}\)や\(\large{11^3\hspace{2pt}}\)の余りを調べる過程で計算量が多くなります。
そこで、\(\large{11 \equiv 4 \pmod 7\hspace{2pt}}\)の関係を利用して、\(\large{\hspace{1pt}11\hspace{2pt}}\)の累乗の代わりに\(\large{\hspace{1pt}4\hspace{2pt}}\)の累乗を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りを調べることで計算量を減らせます。
\(\large{4^2\hspace{2pt}}\)を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りを調べると
$$\large{4^{2} \equiv 16 \equiv 2 \pmod 7}$$
\(\large{4^3\hspace{2pt}}\)を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りを調べると $$\large{4^{3} \equiv 64 \equiv 1 \pmod 7}$$ となることから、\(\large{\hspace{1pt}4^3\hspace{2pt}}\)を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りが\(\large{\hspace{1pt}1\hspace{2pt}}\)となります。
すなわち $$\large{11^{100} \equiv 4^{100} \equiv 4\cdot(4^3)^{33} \equiv 4 \pmod 7}$$
よって、\(\large{11^{100}\hspace{2pt}}\)を\(\large{\hspace{1pt}7\hspace{2pt}}\)で割った余りは\(\large{\hspace{1pt}4\hspace{2pt}}\)となります。
一の位の数は\(\large{\hspace{1pt}10\hspace{2pt}}\)で割った余りから求められます。
具体的な数で調べてみると
\(\large{123\hspace{2pt}}\)を\(\large{\hspace{1pt}10\hspace{2pt}}\)で割った余りは\(\large{\hspace{1pt}123 = 12 \times 10 + 3 \hspace{2pt}}\)から余りは\(\large{\hspace{1pt}3\hspace{2pt}}\)となります。
また、\(\large{1234\hspace{2pt}}\)を\(\large{\hspace{1pt}10\hspace{2pt}}\)で割った余りは\(\large{\hspace{1pt}1234 = 123 \times 10 + 4 \hspace{2pt}}\)から余りは\(\large{\hspace{1pt}4\hspace{2pt}}\)となります。
すなわち、合同式で表せば $$\large{a \equiv b \pmod {10}}$$ を満たす\(\large{\hspace{1pt}10\hspace{2pt}}\)より小さい正の整数\(\large{\hspace{1pt}b\hspace{2pt}}\)が\(\large{\hspace{1pt}a\hspace{2pt}}\)の一の位の数となります。
\(\large{7^2\hspace{2pt}}\)を\(\large{\hspace{1pt}10\hspace{2pt}}\)で割った余りを調べると
$$\large{7^2 \equiv 49 \equiv 9 \pmod {10}}$$
\(\large{7^3\hspace{2pt}}\)を\(\large{\hspace{1pt}10\hspace{2pt}}\)で割った余りを調べると $$\large{7^{3} \equiv 343 \equiv 3 \pmod {10}}$$
\(\large{7^4\hspace{2pt}}\)を\(\large{\hspace{1pt}10\hspace{2pt}}\)で割った余りを調べると $$\large{7^{4} \equiv 2401 \equiv 1 \pmod {10}}$$
すなわち $$\large{7^{100} \equiv (7^4)^{25} \equiv 1 \pmod {10}}$$
よって、\(\large{7^{100}\hspace{2pt}}\)の一の位の数は\(\large{\hspace{1pt}1\hspace{2pt}}\)となります。
上記の別解として、\(\large{7^2\hspace{2pt}}\)を\(\large{\hspace{1pt}10\hspace{2pt}}\)で割った余りが\(\large{\hspace{1pt}-1\hspace{2pt}}\)であることを利用することもできます。
(\(\large{\hspace{1pt} 49 = 5 \times 10 -1\hspace{2pt}}\)から余りが\(\large{\hspace{1pt}-1\hspace{2pt}}\)とすることができます。)
\(\large{7^2\hspace{2pt}}\)を\(\large{\hspace{1pt}10\hspace{2pt}}\)で割った余りを調べると
$$\large{7^2 \equiv 49 \equiv {-1} \pmod {10}}$$
すなわち $$\large{7^{100} \equiv (7^2)^{50} \equiv (-1)^{50} \equiv 1 \pmod {10}}$$
よって、\(\large{7^{100}\hspace{2pt}}\)の一の位の数は\(\large{\hspace{1pt}1\hspace{2pt}}\)となります。