合同式と剰余類

$a$, $b\in\mathbb{Z}$, $m\in \mathbb{Z}_{>0}$とする.

$$m\mid (a-b)$$

となるとき, $a$と$b$とは$m$を法として合同であるといい, 記号で

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

と書く.

また, $\equiv$の入った式を合同式という.

例えば,

$$3\equiv 1\pmod{2}$$

や, 未知数$x$の入った式

$$7x\equiv 3\pmod{10}$$

は合同式である.

定理 5.1   $a$, $b$, $c\in\mathbb{Z}$, $m\in \mathbb{Z}_{>0}$とする.

(i)

$a\equiv a\pmod{m}$.

(ii)

$a\equiv b\pmod{m}$ならば $b\equiv a\pmod{m}$.

(iii)

$a\equiv b\pmod{m}$, $b\equiv c\pmod{m}$がともに成り立てば, $a\equiv c\pmod{m}$.

証明. (i)    任意の $a\in\mathbb{Z}$, $m\in \mathbb{Z}_{>0}$に対して,

$$a-a = 0 = m\cdot 0.$$

よって $m\mid (a-a)$. したがって $a\equiv a\pmod{m}$.

(ii)     $a\equiv b\pmod{m}$のとき, ある $t\in\mathbb{Z}$が存在して

$$a-b = mt.$$

このとき

$$b-a = m(-t).$$

ゆえに $m\mid(b-a)$. したがって $b\equiv a\pmod{m}$.

(iii)     $a\equiv b\pmod{m}$, $b\equiv c\pmod{m}$がともに成り立つとき, ある$s$, $t\in\mathbb{Z}$が存在して

$$a - b = ms,\quad b - c = mt.$$

このとき

$$a - c = (a - b) + (b - c) = m(s+t).$$

ゆえに $m\mid(a-c)$. したがって $a\equiv c\pmod{m}$. $\qedsymbol$

$m\in \mathbb{Z}_{>0}$を一つ固定する. $a\in\mathbb{Z}_{>0}$に対して

$$C(a) = \{ x\in\mathbb{Z} \mid x\equiv a\pmod{m} \}$$

とおく. $C(a)$を法$m$に関する剰余類という.

またこのとき, $a$を剰余類$C(a)$の代表元という.

定理 5.2   $a$, $b\in\mathbb{Z}$, $m\in \mathbb{Z}_{>0}$とする. $C(*)$は法$m$に関する剰余類を表すものとする.

(i)

$a\equiv b\pmod{m}\Longrightarrow C(a)=C(b)$.

(ii)

$a\not\equiv b\pmod{m}\Longrightarrow C(a)\cap C(b) =\emptyset$.

証明. (i)    $x\in C(a)$とすれば, $x\equiv a\pmod{m)}$. これと $a\equiv b\pmod{m}$という仮定から, $x\equiv b\pmod{m}$がいえる. ゆえに$x\in C(b)$. したがって $C(a)\subseteq C(b)$.

同様に $C(b)\subseteq C(a)$もいえる. よって$C(a)=C(b)$.

(ii)     $C(a)\cap C(b)\neq\emptyset$と仮定すると, ある $x\in\mathbb{Z}$が存在して,

$x\in C(a)$かつ$x\in C(b)$.

すなわち,

$x\equiv a\pmod{m}$かつ $x\equiv b\pmod{m}$.

このことから

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

が導かれる. したがって

$$C(a)\cap C(b)\neq\emptyset \Longrightarrow a\equiv b\pmod{m}.$$

あとは, この対偶をとればよい. $\qedsymbol$

$m\in \mathbb{Z}_{>0}$に対して, 法$m$に関する剰余類の全体からなる集合を $\mathbb{Z}/m\mathbb{Z}$とおく:

$$\mathbb{Z}/m\mathbb{Z} = \{ C(a) \mid a\in\mathbb{Z} \} = \{C(0), C(1), \ldots, C(m-1) \}.$$

$\mathbb{Z}/m\mathbb{Z}$は$m$個の元からなる有限集合である.

定理 5.3   $a$, $a'$, $b$, $b'\in\mathbb{Z}$, $m\in \mathbb{Z}_{>0}$とする.

$$a\equiv a'\pmod{m},\quad b\equiv b'\pmod{m}$$

がともに成り立つとき, 次のことが成り立つ:

(i)

$a+b\equiv a'+b'\pmod{m}$.

(ii)

$a-b\equiv a'-b'\pmod{m}$.

(iii)

$ab\equiv a'b'\pmod{m}$.

証明. (i)     $(a+b)-(a'+b')=(a-a')+(b-b')$よりわかる.

(ii)     $(a-b)-(a'-b')=(a-a')-(b-b')$よりわかる.

(ii)     $ab-a'b'=a(b-b')+b'(a-a')$よりわかる. $\qedsymbol$

$\mathbb{Z}/m\mathbb{Z}$の二つの元$C(a)$と$C(b)$との和$C(a)+C(b)$, 差$C(a)-C(b)$, 積$C(a)C(b)$を次のように定義する:

$$C(a)+C(b) = C(a+b),\quad C(a)-C(b) = c(a-b),\quad C(a)C(b) = C(ab).$$

この定義は, 剰余類の代表元の選び方に依存しない.

定理 5.4   $a$, $b$, $c\in\mathbb{Z}$, $c\neq 0$, $m\in \mathbb{Z}_{>0}$とする.

$$ca\equiv cb\pmod{m}$$

が成り立つとき, $d=\mathrm{gcd}(c, m)$とおけば

$$a\equiv b\pmod{\frac{m}{d}}$$

が成り立つ.

証明. $ca\equiv cb\pmod{m}$のとき, ある $t\in\mathbb{Z}$が存在して,

$$c(a-b) = mt.$$

$c=dc'$, $m=dm'$とおくと,

$$c'(a-b)=m't.$$

よって

$$m'\mid c'(a-b).$$

$\mathrm{gcd}(c', m')=1$であるから, $m'\mid (a-b)$でなければならない. ゆえに

$$a\equiv b\pmod{m'}.$$

$\qedsymbol$

法$m$に関する剰余類は$m$個ある.

その各々から$1$つずつ代表元をとって作った$m$個の整数の組を, 法$m$に関する完全剰余系という.

例えば$m=7$のとき,

$$0,\quad 1,\quad 2,\quad 3,\quad 4,\quad 5,\quad 6$$

や

$$-3,\quad -2,\quad -1,\quad 0,\quad 1,\quad 2,\quad 3$$

は完全剰余系である.

一般に, 完全剰余系の選び方は無数にある.

定理 5.5   $m\in \mathbb{Z}_{>0}$, $c\in\mathbb{Z}$とし, $\mathrm{gcd}(c, m)=1$とする. $a_1$, $a_2$, $\ldots$, $a_m$を法$m$に関する完全剰余系とすれば, $ca_1$, $ca_2$, $\ldots$, $ca_m$もまた法$m$に関する完全剰余系である.

証明. ある番号$i$, $j$が存在して

$$ca_i\equiv ca_j\pmod{m}$$

であるとする. 仮定 $\mathrm{gcd}(c, m)=1$より,

$$a_i\equiv a_j\pmod{m}.$$

したがって,

$$C(a_i)=C(a_j).$$

完全剰余系の定義の仕方から, $i=j$でなければならない.

よって, $ca_1$, $ca_2$, $\ldots$, $ca_m$は別々の剰余類に属する. $\qedsymbol$

定理 5.6   $a$, $b\in\mathbb{Z}$, $m\in \mathbb{Z}_{>0}$とする. $d=\mathrm{gcd}(a, m)$とおく.

合同式

$$ax\equiv b\pmod{m}$$

が整数解を持つための必要十分条件は, $d$が$b$を割り切ることである.

さらに, $m$を法として考えたとき, 上の合同式の整数解の個数は$d$である.

証明. 上の合同式が整数解$x_0$を持つと仮定すると, ある $t\in\mathbb{Z}$が存在して

$$ax-b=mt.$$

ゆえに

$$d\mid (ax-mt)=b.$$

逆に, $d$が$b$を割り切ると仮定すると, 方程式

$$ax+my = b$$

は解$x$, $y\in\mathbb{Z}$を持つ. このとき,

$$ax\equiv b\pmod{m}$$

となっている. よって, 与えられた合同式は解 $x\in\mathbb{Z}$を持つ.

さらに, $x_0\in\mathbb{Z}$を与えられた合同式の解の一つとし,

$$a=a'd,\quad m=m'd,\quad b=b'd$$

とおく. 与えられた合同式の任意の解 $x\in\mathbb{Z}$に対して,

$$a'x\equiv b'\pmod{m'},\quad a'x_0\equiv b'\pmod{m'}$$

であるから,

$$a'x\equiv a'x_0\pmod{m'}.$$

$\mathrm{gcd}(a', m')=1$であるから,

$$x\equiv x_0\pmod{m'}.$$

したがって, $x$は$m$を法として

$$x_0,\quad x_0+m',\quad x_0+2\cdot m',\quad \ldots,\quad x_0+(d-1)\cdot m'$$

の$d$個のうちのいずれかと合同である.

逆に, これらの$d$個はすべて与えられた合同式の解である.

したがって, 与えられた合同式の解は$m$を法としてちょうど$d$個ある. $\qedsymbol$

定理 5.7   $a_1$, $a_2\in\mathbb{Z}$, $m_1$, $m_2\in\mathbb{Z}_{>0}$とする. 連立合同式

$$x\equiv a_1\pmod{m_1},\quad x\equiv a_2\pmod{m_2}$$

が整数解を持つための必要十分条件は, $d=\mathrm{gcd}(m_1, m_2)$とおくとき,

$$a_1\equiv a_2 \pmod{d}$$

が成り立つことである.

さらに, 上の連立合同式が整数解を持つとき, その解は$m_1$, $m_2$の最小公倍数を法として一意的である.

証明. 上の連立合同式が解 $x\in\mathbb{Z}$を持つとする:

$$x\equiv a_1\pmod{m_1},\quad x\equiv a_2\pmod{m_2}.$$

$m_1$, $m_2$はともに$d$で割り切れるから,

$$x\equiv a_1\pmod{d},\quad x\equiv a_2\pmod{d}.$$

ゆえに

$$a_1\equiv a_2\pmod{d}.$$

逆に, $a_1\equiv a_2\pmod{d}$が成り立つと仮定すると, 合同式

$$m_1t\equiv a_2-a_1\pmod{m_2}$$

は解 $t\in\mathbb{Z}$を持つ. このとき,

$$x = a_1 + m_1t$$

とおけば,

$$x\equiv a_1\pmod{d},\quad x\equiv a_2\pmod{d}$$

となる.

最後に, 解の一意性を証明する.

もし, $x_1$, $x_2\in\mathbb{Z}$がともに与えられた連立合同式の解であるとすると,

$$x_1\equiv a_1 \pmod{m_1},\quad x_1\equiv a_2 \pmod{m_2},$$

$$x_2\equiv a_2 \pmod{m_1},\quad x_2\equiv a_2 \pmod{m_2}.$$

よって,

$$x_1\equiv x_2 \pmod{m_1},\quad x_1\equiv x_2 \pmod{m_2}.$$

言い換えると,

$$m_1\mid (x_1-x_2),\quad m_2\mid (x_1-x_2).$$

したがって, $l=\mathrm{lcm}(m_1, m_2)$とおくと, 最小公倍数の性質から,

$$l\mid (x_1-x_2).$$

すなわち,

$$x_1\equiv x_2\pmod{l}.$$

$\qedsymbol$

系 5.7.1 (中国剰余定理)   $a_1$, $a_2$, $\ldots$, $a_n\in\mathbb{Z}$, $m_1$, $m_2$, $\ldots$, $m_n\in\mathbb{Z}_{>0}$, $n\geq 2$とする.

$i\neq j$のとき, $\mathrm{gcd}(m_i, m_j)=1$と仮定する.

このとき, 連立合同式

$$x \equiv a_1 \pmod{m_1},$$

$$x \equiv a_2 \pmod{m_2},$$

$$\cdots\cdots,$$

$$x \equiv a_n \pmod{m_n}$$

は, 積 $m_1m_2\cdots m_n$を法としてただ一つの整数解を持つ.

証明. 合同式の個数$n$に関する数学的帰納法によって証明する.

$n=2$のときは, 上の定理より明らかである.

$n=k$のとき, 主張が正しいと仮定すると, 連立合同式

$$x \equiv a_1 \pmod{m_1},$$

$$x \equiv a_2 \pmod{m_2},$$

$$\cdots\cdots,$$

$$x \equiv a_k \pmod{m_k}$$

は解 $b_0\in\mathbb{Z}$を持ち, すべての整数解$x$は

$$x\equiv b_0\pmod{m_1m_2\cdots m_k}$$

を満たす. ここで, $i\neq j$のとき $\mathrm{gcd}(m_i, m_j)=1$という仮定から, $m_1$, $m_2$, $\ldots$, $m_k$の最小公倍数が積 $m_1m_2\cdots m_k$になることに注意する.

さらに合同式 $x\equiv a_{k+1}\pmod{m_{k+1}}$を追加したとき, $k+1$個の合同式

$$x \equiv a_1 \pmod{m_1},$$

$$x \equiv a_2 \pmod{m_2},$$

$$\cdots\cdots,$$

$$x \equiv a_k \pmod{m_k},$$

$$x \equiv a_{k+1} \pmod{m_{k+1}}$$

の整数解$x$は, 連立合同式

$$x\equiv b_0 \pmod{m_1m_2\cdots m_k},\quad x\equiv a_{k+1}\pmod{m_{k+1}}$$

の解である. そして上の定理より, この連立方程式は解 $b_0'\in\mathbb{Z}$を持ち, すべての整数解$x'$は

$$x'\equiv b_0'\pmod{m_1m_2\cdots m_km_{k+1}}$$

を満たす. したがって$k+1$のときも主張は正しい. $\qedsymbol$