📂整数論

整数論における合同

定義 ¹

整数 $a \equiv b \pmod{m}$, $\iff$, $a$, $b$, $m$ に対して、$a = b + mk$ を満たす整数 $k$ が存在する。

定理

$a_{1} \equiv b_{1} \pmod{m}$ と $a_{2} \equiv b_{2} \pmod{m}$ が成り立つとしよう。

• [1] 加算: $a_{1} + a_{2} \equiv b_{1} + b_{2} \pmod{m}$
• [2] 減算: $a_{1} - a_{2} \equiv b_{1} - b_{2} \pmod{m}$
• [3] 乗算: $a_{1} a_{2} \equiv b_{1} b_{2} \pmod{m}$
• [4] 除算: $\gcd ( c , m ) = 1$ の場合、 $$ac \equiv bc \pmod{m} \implies a \equiv b \pmod{m}$$
• [5] モジュロ同士の乗算: $\gcd ( m_{1} , m_{2} ) = 1$ の場合、 $$\begin{cases} a \equiv b \pmod{ m_{1} } \\ a = b \pmod{ m_{2} } \end{cases} \implies a \equiv b \pmod{ m_{1} m_{2} }$$
• [6] モジュロのべき乗: $a \equiv b \pmod{m^n}$ の場合は $a \equiv b \pmod{m}$
• [7] モジュロを含む約分: $ax \equiv ay \pmod{am} \iff x \equiv y \pmod{m}$

説明

式 $a \equiv b \pmod{m}$ を合同式と呼び、法（モジュロ）$m$ で $a$ は $b$ に合同であるという。ただし、方程式の中で $\pmod{}$ がそのまま使われているので、モジュロ $m$ と発音する方が一般的だ。

定理 [4]で、$\gcd(c,m) = 1$ という条件がない場合、両辺から $c$ を割ることはできない。例えば $8 \equiv 20 \pmod{12}$ は成り立つが、両辺から $4$ を割った $2 \equiv 5 \pmod{12}$ は成り立たない。

通常、簡単な整数論の問題を扱う場合は $m$ を素数とするが、複雑になると $m$ を合成数とする。したがって、合同方程式全体を大きく見て、その性質も理解しておく必要がある。

証明

[5]

$a \equiv b \pmod{m_{1}}$ であるから、次を満たす整数 $n_{1}$ が存在する。 $$a = b + n_{1} m_{1}$$ $a \equiv b \pmod{m_{2}}$ であるから、次を満たす整数 $n_{2}$ が存在する。 $$a = b + n_{2} m_{2}$$ $m_{1}$ と $m_{2}$ は互いに素であるため、二つの式が同時に成り立つには、$n_{1}$ は $m_{2}$ の倍数であり、$n_{2}$ は $m_{1}$ の倍数でなければならない。したがって、次を満たす整数 $n_{3}$ が存在する。 $$a = b + n_{3} m_{1} m_{2}$$ すると、合同式の定義により $$a \equiv b \pmod{ m_{1} m_{2} }$$

■

[6]

$a \equiv b \pmod{m^n}$ の場合、次を満たす整数 $k$ が存在する。 $$a = b + m^n k$$ $m^{n-1}$ を取り除くと、 $$a = b + m^{n} k \cdot n = b + m \cdot (m^{n-1} k)$$ したがって、次を満たす整数 $m^{n-1} k$ が存在する。 $$a \equiv b \pmod{m}$$

■

[7]

ある整数 $k$ について、 $$\begin{align*} ax \equiv ay \pmod{am} & \iff ax = ay + amk \\ & \iff x = y + mk \\ & \iff x \equiv y \pmod{m} \end{align*}$$

■