2.4.1 合同式

自然数$n$を固定します。ここでは、整数を$n$で割った余りにより分類することを考えます。

定義 2.4.1
2つの整数$a,b$の差が$n$の倍数のとき、$a$と$b$は$n$を法として互いに合同（congruent modulo $n$）といい、

$$a\equiv b \pmod{n}$$

と記します。$\pmod {n}$は（モッドエヌ)とよみます。 また、$a,b$の差が$n$の倍数ではないとき、 $a \not\equiv b\pmod{n}$と書きます。

例 2.4.2
（1） $4\equiv 7\pmod 3\qquad 15\equiv22\pmod 7 \qquad 5\equiv 25 \pmod 5$
（2） $4\not\equiv 7\pmod 4\qquad 15\not\equiv 22\pmod8 \qquad 5\not\equiv 25 \pmod 3$

上の式には$\pmod {n}$がついているため$\equiv$の代わりに$=$を使っても混同しませんので、$\equiv$の代わりに$=$を使うことがあります。つまり、 $a\equiv b \pmod n$と $a=b \pmod n$は同じ意味です。また、前後の文脈から明らかな場合は$\pmod {n}$も省略することもあります。 $\equiv \pmod n$が使われている式のことを$n$を法とする合同式（congruence equation）といいます。

次の命題は、$\pmod n$の性質を$n$で割った余りが等しいことに言い換えています。

命題 2.4.3
自然数$n$を固定し$a,b$を整数とすると、

$$a\equiv b \pmod n \Longleftrightarrow aをnで割った余りが等しい$$

証明
$a$を$n$で割ったときの余りを$r_1$、$b$を$n$で割ったときの余りを$r_2$とすると、

$$a=nq_1+r_1、b=nq_2+r_2$$

となるような整数$q_1,q_2$が存在します。したがって、 $a-b=n(q_1-q_2)+r_1-r_2$です。ここで、$a-b$が$n$の倍数であるとすると、$r_1-r_2$が$n$の倍数である必要がありますが、 $0\leqq r_i<n$ですので $-n<r_1-r_2<n$でありこの範囲で$n$の倍数は0しかありませんので、$r_1-r_2=0$つまり余りが等しいことが分かります。

逆に、余りが等しい（$r_1=r_2$）と仮定すると、上の式より$a-b$が$n$の倍数であることが分かります。

次の命題は、合同式は、 $+,-,\times$に関する限り$=$と同様に取り扱うことができることを意味しています。

定理 2.4.4
自然数$n$を固定する。$a,b,a',b'$が整数で

$$a\equiv a'\pmod n\hspace{10mm} b\equiv b'\pmod n$$

とすると
（1） $a+b\equiv a'+b'\pmod n$
（2） $a-b\equiv a'-b'\pmod n$
（3） $ab\equiv a'b'\pmod n$

証明
（1）仮定より $n\vert a-a',n\vert b-b'$よって、 $n\vert(a+b)-(a'+b'）$であり、これは、 $a+b=a'+b'\pmod n$を意味する。
（2）仮定より $n\vert a-a',n\vert b-b'$よって、 $n\vert(a-b)-(a'-b'）$であり、これは、 $a-b=a'-b'\pmod n$を意味する。
（3）仮定より $n\vert a-a',n\vert b-b'$よって、 $(a-a')=na'',(b-b')=nb''$となる整数$a'',b''$が存在する。よって、 $a=a'+na'',b=b'+nb''$。両辺をかけると $ab=a'b'+n(a''b'+b''a'+na''b'')$よって、$n\vert ab-a'b'$。

この定理を使うことにより次のような基本的な整数の性質を簡単に示すことができます。

例 2.4.5 (法2の場合)
$a$を偶数とすると $a\equiv 0 \pmod 2$、$b$を奇数とすると $b\equiv 1\pmod 2$です。 上記の命題より、 $a+b\equiv 1\pmod 2\hspace{5mm}ab \equiv 0\pmod 2$です。
これは、偶数+奇数=奇数、偶数×奇数=偶数を意味しています。同様に、偶数+偶数=偶数、奇数+奇数=偶数、奇数×奇数=奇数などを示すことができます。

例 2.4.6 (法3の場合)
整数を3で割った余りは、0、1、2のいずれかになります。 $n\equiv 2\pmod 3、m\equiv 1\pmod 3$とすると、 $n+m\equiv 0\pmod3,nm\equiv 2\pmod 3$となります。 つまり、3で割ったときの余りが2の整数と余りが1の整数を足すと余りは0となる（つまり3の倍数となる）ことが分かります。また、掛けると余りは2となることが分かります。

次の例では1次合同式 $a\mathrm{X}+b\equiv 0\pmod n$が解ける場合があることが分かります。どのような場合に解けるかについては、を参照してください。

例 2.4.7 (一次合同式)
1次合同式 $5\mathrm{X}+3\equiv 0\pmod 7$を解いてみましょう。
両辺に$-3$を足すことにより、

$$5\mathrm{X} \equiv -3 \pmod 7$$

$$\equiv 4 \pmod 7$$

$$3\cdot5=15\equiv 1\pmod 7$$

$$\mathrm{X} \equiv 12\pmod 7$$

$$\equiv 5 \pmod 7$$

よって、 $\mathrm{X}\equiv 5\pmod 7$が解です。

例 2.4.8
1次合同式 $3\mathrm{X}-5\equiv 0 \pmod{11}$を解いてみましょう。
両辺に$5$を足すことにより、

$$3\mathrm{X} \equiv 5\pmod{11}$$

$$4\cdot 3=12\equiv 1\pmod{11}$$

$$\mathrm{X} \equiv 20 \pmod{11}$$

$$\equiv 9 \pmod{11}$$

よって、 $\mathrm{X}\equiv 9\pmod{11}$が解です。

例2.4.7では、 $3\cdot 5=14\equiv 1\pmod 7$を使うことにより合同式を解きました。例2.4.8では、 $4\cdot 3=12\equiv 1\pmod{11}$を使うことにより合同式を解きました。常にこのようにうまくいくとは限りません。

例 2.4.9
1次合同式 $2\mathrm{X}-3\equiv 0\pmod 4$を解いてみましょう。
両辺に3を足すことにより

$$2\mathrm{X} \equiv 3 \pmod 4$$

ここで、$2$に何かをかけて$1\pmod 4$にしたいところですが、そのような数字は見つかりません。なぜでしょうか。

左辺は2の倍数ですから必ず偶数です。偶数を$4$で割ると余りは0か2です。したがって、余りが3になることはありません。
よって、1次合同式 $2\mathrm{X}-3\equiv 0\pmod 4$の解はありません。

上の例からも1次合同式がどのような場合に解けるのか、予想してみましょう。こたえは2.4.4で扱います。また、2次合同式は解けるのか知りたいですね。2次合同式が解けるか否かをあつかったのはGaussであり、平方剰余の相互法則という極めて美しい結果があります。平方剰余の相互法則は本章の目標の1つです。