次: 一次合同方程式 上: 合同式 前: 合同式

合同式

整数の合同

整数$a$と$b$の差が$m$の倍数であるとき， $a$と $b$は $m$を法として互いに合同であるといい，次のように記す．

$$a\equiv b\quad (\bmod.\ m)$$

ここで整数の部分集合$m\mathbb{Z}$を

$$m\mathbb{Z}=\{mx\ \vert\ x\in \mathbb{Z}\ \}$$

とする．集合$m\mathbb{Z}$の要素の和・差・積はふたたび$m\mathbb{Z}$に属する． 合同という関係はこれを用いて

$$a\equiv b\quad (\bmod.\ m)\quad \iff\quad a-b\in m\mathbb{Z}$$

と集合論的にとらえることができる．

定理 9
整数$a$と$b$が$m$を法として合同であることと， $a$と$b$を$m$で割った二つの余りが等しいことは同値である．■

証明     整数$a$と$b$が$m$を法として合同であるとし，$a-b=mq$とおく． ここで$a$と$b$を$m$で割った商と余りをそれぞれ$q_1,\ q_2$，$r_1,\ r_2$とする．

$$\begin{eqnarray*} a&=&mq_1+r_1\\ b&=&mq_2+r_2 \end{eqnarray*}$$

辺々引いて$a-b=mq$を用いると

$$mq=(q_1-q_2)m+r_1-r_2$$

つまり

$$\vert m\vert\vert q-q_1+q_2\vert=\vert r_1-r_2\vert$$

もし $q-q_1+q_2\ne 0$なら， $\vert m\vert\vert q-q_1+q_2\vert\ge \vert m\vert$であるが， 右辺は $m$で割った余りの差なので $\vert r_1-r_2\vert<m$である． これは矛盾である．

$$∴\quad q-q_1+q_2=0，\quad r_1-r_2=0$$

$m$を法として合同な二数は$m$で割った二つの数の余りが等しい．

逆に$a$と$b$を$m$で割った余りが等しいとする．

$$a=mq_1+r,\ b=mq_2+r$$

より $a-b=m(q_1-q_2)$である．つまり$a$と$b$は$m$を法として合同である． □

同値関係

集合$A$の要素の間に，成り立つか成り立たないかがつねに確定する関係が定義されているとする．要素$a$と$b$の間にこの関係が成り立つことを$a〜b$と表す．

(i)

$a〜a$．

(ii)

$a〜b$なら$b〜a$．

(iii)

$a〜b,\ b〜c$なら$a〜c$．

が成り立つとき,「〜」を「同値関係」という．

例 2.1.1        $p$を整数とする．整数$a,\ b$について関係$a〜b$を

$$a-b\ が p の倍数$$

で定める．〜は同値関係である．

同値類

同値関係があると，同値なものをひとつの部分集合にまとめることができる． つまり$A$の要素$a$と同値な要素からなる$A$の部分集合 $\overline{\mathstrut \mathstrut a}$が一意に確定し， $A$のすべての要素はいずれかただひとつの $\overline{\mathstrut a}$に属する． いいかえると，任意の $\overline{\mathstrut a}$と $\overline{\mathstrut b}$について $\overline{\mathstrut a}=\overline{\mathstrut b}$ か $\overline{\mathstrut a}\cap \overline{\mathstrut b}=\emptyset$のいずれか一方が成立する．

$a$の属する部分集合 $\overline{\mathstrut a}$を$a$の同値類という．このようにして得られる同値類の集合

$$A／〜=\{\overline{\mathstrut a}\ \vert\ a\in A \}$$

を，集合$A$の関係〜に関する商集合という．

合同は同値関係

$$\begin{array}{ll} 反射律&a\equiv a\quad (\bmod.\ m)\\ 対.. ...d (\bmod.\ m)\ 、ハ、鬢ミ \ a\equiv c\quad (\bmod.\ m) \end{array}$$

ネソシヘホァ。、ツミセホホァ、マフタ、鬢ォ、ヌ、「、・・ソ莢ワホァ、!-- MATH $a-b,\ b-c \in m\mathbb{Z}$ --> $a-b,\ b-c \in m\mathbb{Z}$なら

$$a-c=(a-b)+(b-c)\in m\mathbb{Z}$$

より成立する． つまり合同という関係は同値関係である．

剰余類

$\mathbb{Z}$において，$m$を法として互いに合同な整数で一つの部分集合を作り，合同でないものは異なる部分集合になるようにして，$\mathbb{Z}$を互いに共通部分のない，いくつかの部分集合の和にすることができる．その一つ一つの部分集合を$m$を法とする類といい，類に分けることを類別という．$m$を法とする類とは，$m$を法として互いに合同なすべての数の集合である．いいかえると$m$で割ったとき余りの等しい整数の集合である．つまり整数を$m$で割った余りで類別したのである．それぞれの部分集合を剰余類という．

剰余類の集合が整数の集合$\mathbb{Z}$のこの同値関係による商集合である．これを $\mathbb{Z}\big/m\mathbb{Z}$と表す．あるいは$\mathbb{Z}_m$と表すこともある．$m$を法とする類別では$m$個の類に類別される．したがって$\mathbb{Z}_m$は$m$個の要素からなる集合である．

剰余類の間の演算

定理 10
    

$$a\equiv a'\quad (\bmod.\ m),\ b\equiv b'\quad (\bmod.\ m)$$

ならば

$$a\pm b \equiv a'\pm b'\quad (\bmod.\ m)$$

$$ab \equiv a'b'\quad (\bmod.\ m)$$ (2.1)

一般に

$$a\equiv a'\ (\bmod.\ m),\ \ b\equiv b'\ (\bmod.\ m),\ \ c\equiv c'\ (\bmod.\ m),\ \cdots$$

で $f(x,\ y,\ z,\ \cdots)$が $x,\ y,\ z,\ \cdots$に関する整数係数の整式ならば

$$f(a,\ b,\ c,\ \cdots)\equiv f(a',\ b',\ c',\ \cdots)\quad (\bmod.\ m)$$ (2.2)

が成り立つ．■

証明     仮定によって

$$\begin{array}{ll} a\equiv a'\quad (\bmod.\ m)&したがってa-a... ...quiv b'\quad (\bmod.\ m)&したがってb-b'\ はm の倍数 \end{array}$$

ゆえに $(a+b)-(a'+b')=(a-a')+(b-b')$は $m$の倍数である．また, $ab-a'b'=(a-a')b+a'(b-b')$も $m$の倍数である．すなわち(2.1)が示された．

(2.1)から $a\equiv a'\quad (\bmod.\ m)$なら任意の整数 $N$に対して

$$Na\equiv Na'\quad (\bmod.\ m)$$

および

$$Na^{\alpha}b^{\beta}c^{\gamma} \cdots \equiv Na'^{\alpha}{b'}^{\beta}{c'}^{\gamma} \cdots\quad (\bmod.\ m)$$

ふたたび(2.1)から

$$\sum Na^{\alpha}b^{\beta}c^{\gamma} \cdots \equiv \sum Na'^{\alpha}{b'}^{\beta}{c'}^{\gamma} \cdots\quad (\bmod.\ m)$$

すなわち (2.2)が示された．□

$\mathbb{Z}_m$において整数$a$の属する類を$\overline{a}$と表す．$m$を明示する必要があるときは $\overline{a}_m$と表そう．本定理の意味することは，$\mathbb{Z}_m$における和と積を

$$\overline{a}+\overline{b}=\overline{a+b},\ \overline{a}\cdot\overline{b}=\overline{a\cdot b}$$

で適切に定義することができる，ということである．つまり$\mathbb{Z}_m$の各類からどのように整数を選んで演算を考えても同じ結果になる．選び方によらず類のみで定まる類と類の間の演算が定義される．そして，分配法則

$$\overline{c}\left(\overline{a}+\overline{b}\right)= \overline{c}\cdot\overline{a}+\overline{c}\cdot\overline{a}\overline{b}$$

も成り立つ．加法と乗法の単位元は$\overline{0}$と$\overline{1}$である．これによって$\mathbb{Z}_m$は有限個($m$個)の要素からなる環である.

例 2.1.2   $m=6$のとき．

$$\begin{eqnarray*} \overline{0}&=&\{\cdots,\ -12,\ -6,\ 0,\ 6,\ 12,\ \cdots\}\\ ... ...\ \overline{5}&=&\{\cdots,\ -7,\ -1,\ 5,\ 11,\ 17,\ \cdots\}\\ \end{eqnarray*}$$

$$\mathbb{Z}_6=\mathbb{Z}\big/6\mathbb{Z}=\{ \overline{0},\ \o... ... \overline{2},\ \overline{3},\ \overline{4},\ \overline{5}\}$$

演算：

$$\begin{eqnarray*} &&\overline{2}+\overline{5}=\overline{7}=\overline{1},\ \over... ...e{10}=\overline{3},\ \overline{2}\cdot\overline{1}=\overline{2} \end{eqnarray*}$$

ただし，

$$\overline{2}\cdot\overline{3}=\overline{6}=\overline{0}$$

なので乗法の逆元が存在するとはかぎらない．

有限体

乗法の逆元が存在すれば環は体になる．有理数体，実数体，複素数体はすべて四則演算ができる体であった．これらの体は，無数の要素からなっている．それに対して有限個の要素からなる体が存在する．これはガロアの発見であるが，現代の代数学の扉を開けるものであった．

定理 11
     $p$を素数とする． $\mathbb{Z}_p=\mathbb{Z}\big/p\mathbb{Z}$は$p$個の要素からなる体である． ■

証明     $\overline{0}$でない他の$\overline{a}$に積の逆元が存在することを示せばよい．$a$として1から$p-1$のいずれかをとることができる．このとき$p$と$a$は互いに素になる．したがって

$$pq+ab=1$$

となる整数$b$が存在する．ところが

$$\overline{a}\cdot\overline{b}=\overline{ab}=\overline{1}$$

であるから， $\overline{b}=\overline{a}^{-1}$となり$\overline{a}$に逆元が存在した．よって$\mathbb{Z}_p$は体である． □

このように，剰余類という整数の部分集合を一つの要素と見なし，剰余類にあいだの演算を考える．ここが難しいところであり，また数学が現代に飛躍するところでもあった．今後，本質的なところではこの考え方で考察をすすめるが，必ずしも本質的でないところでは，古典的な考え方でいくようにしたい．

次: 一次合同方程式 上: 合同式 前: 合同式