9.6 合同算術

数論の名著『Disquisitionesディスクィジティオネス Arithmeticaeアリトメティカエ (算術研究)』の最初のページで、Gaussガウスは合同 (congruence) の概念を導入する。この Gauss という人物もそれなりに優れたアイデアをいくつかひねり出すことに成功しているので、合同の定義と性質をこれから見ていく。Gauss は「\(n\) を法 (modulus) として \(a\) と \(b\) が合同」を「\(n \; | \; (a - b)\)」と定義した。この関係は次のように表記される:

\[ a \equiv b \quad (\text{mod } n) \]

例えば、\(7 \; | \; (29 - 15)\) から次の関係が分かる:

\[ 29 \equiv 15 \quad (\text{mod } 7) \]

\(n \leq 0\) の法を考える意味は薄いので、以降では法は正整数だと仮定する。

合同と剰余の間には密接な関係がある:

補題 9.6.1

\[ a \equiv b \quad (\text{mod } n) \ \ \longleftrightarrow \ \ \operatorname{rem}(a, n) = \operatorname{rem}(b, n) \]

証明除算定理 (定理 9.1.4) より、次の等式を満たす一意な整数の組 \(q_{1}\), \(r_{1}\) と \(q_{2}\), \(r_{2}\) が存在する:

\[ \begin{aligned} a &= q_{1} n + r_{1} \\ b &= q_{2} n + r_{2} \end{aligned} \]

ただし \(r_{1}, r_{2} \in [0..n)\) である。一つ目の等式から二つ目の等式を引けば次を得る:

\[ a - b = (q_{1} - q_{2})n + (r_{1} - r_{2}) \]

合同の定義より、「\(a \equiv b \ \ (\text{mod } n)\)」と「\((q_{1} - q_{2})n + (r_{1} - r_{2})\) が \(n\) で割り切れる」は同値である。\((q_{1} - q_{2})n\) は \(n\) で割り切れるので、この条件は「\(r_{1} - r_{2}\) が \(n\) で割り切れる」に等しい。\(r_{1}, r_{2} \in [0..n)\) より \(r_{1} - r_{2} \in (-n .. n)\) なので、これは \(r_{1} - r_{2} = 0\) を意味する。言い換えれば、\(a \equiv b \ \ (\text{mod } n)\) は \(r_{1} ::= \operatorname{rem}(a,n) = r_{2} ::= \operatorname{rem}(b, n)\) と同値である。 ■

よって \(29 \equiv 15 \ \ (\text{mod } 7)\) は次の関係からも分かる:

\[ \operatorname{rem}(29, 7) = 1 = \operatorname{rem}(15, 7) \]

「\(\text{mod } 7\)」は式の末尾に書かれるものの、この記号が \(29\) より \(15\) に強く関連付くわけではない。例えば \(29 \equiv_{\text{mod} 7} 15\) などと書いた方が分かりやすいだろう。ただ、数学で標準的なのは法を末尾に書く記法なので、我々はそれを受け入れるしかない。

補題 9.6.1 からは、合同関係が等価関係と同様の性質を持つことが分かる。具体的には、次の性質¹が直ちに示せる:

補題 9.6.2

\[ \begin{aligned} a &\equiv a \quad (\text{mod } n) \qquad \text{(反射性)} \\ a \equiv b \ \ \longleftrightarrow \ \ b &\equiv a \quad (\text{mod } n) \qquad \text{(対称性)} \\ (a \equiv b \ \operatorname{\text{\footnotesize AND}} \ b \equiv c) \ \ \longrightarrow \ \ a &\equiv c \quad (\text{mod } n) \qquad \text{(推移性)} \end{aligned} \]

補題 9.6.1 から直ちに分かる次の系も頻繁に利用される:

系 9.6.3

\[ a \equiv \operatorname{rem}(a, n) \quad (\text{mod } n) \]

\(n\) を法とする合同関係が整数全体の集合を \(n\) 個の集合に分割すると捉えることもできる。例えば、法が \(3\) のとき整数全体の集合は次の \(3\) 個の集合に分割される:

\[ \def\arraystretch{1.2}\begin{array}{rrrrrrrrrrl} \{ & \ldots, & -6, & -3, & 0, & 3, & 6, & 9, & 12, & \ldots & \}, \\ \{ & \ldots, & -5, & -2, & 1, & 4, & 7, & 10, & 13, & \ldots & \}, \\ \{ & \ldots, & -4, & -1, & 2, & 5, & 9, & 11, & 14, & \ldots & \} \end{array} \]

これらの集合には \(3\) で割ったときの剰余がそれぞれ \(0\), \(1\), \(2\) である整数が含まれる。整数を \(n\) で割った剰余は \(n\) 個しか存在しないので、\(n\) を法とする合同算術では考える「数」が \(n\) 個だけになる。この意味で、通常の算術を一般化したのが合同算術だと言える。

次に証明するのは、加算と乗算で合同関係が保存されるという有用な事実である:

補題 9.6.4

\(a \equiv b \ \ (\text{mod } n)\) かつ \(c \equiv d \ \ (\text{mod } n)\) なら、次の合同関係が成り立つ:

\[ a + c \equiv b + d \quad (\text{mod } n) \tag{9.7}\]

\[ ac \equiv bd \quad (\text{mod } n) \tag{9.8}\]

証明まず合同関係 \(\text{(9.7)}\) を示す。\(a \equiv b \ \ (\text{mod } n)\) なので、定義より \(n \; | \; (b - a)\) を得る。これは \(n \; | \; ((b + c) - (a + c))\) と同値だから、次の関係が分かる:

\[ a + c \equiv b + c \quad (\text{mod } n) \]

同様に \(c \equiv d \ \ (\text{mod } n)\) からは次の関係が分かる:

\[ b + c \equiv b + d \quad (\text{mod } n) \]

よって合同関係の推移性 (補題 9.6.2) より次を得る:

\[ a + c \equiv b + d \quad (\text{mod } n) \]

合同関係 \(\text{(9.8)}\) も同様に示せる。\(b - a\) を割り切る \(n\) は \(bc - ac\) も割り切る事実を利用する。 ■

これらの三つの性質を持つ二項関係を同値関係 (equivalence relation) と呼ぶ。第 10.10 節で詳しく見る。 ↩︎