次: 演習問題 上: 余りによる類別 前: 剰余系

合同式

合同であることを示す関係式 $a\equiv b\quad (\bmod.\ m)$は， 整数の和差積に関して，等式の場合と同じく次のことが成り立つ．

定理 10        以下，各文字は整数を表す．

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

$$a\pm b\equiv a'\pm b'\quad (\bmod.\ m),\quad ab \equiv a'b'\quad (\bmod.\ m)$$ (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)

証明     仮定によって $a-a'\ および\ b-b'\ はm$ の倍数である． ゆえに $(a+b)-(a'+b')=(a-a')+(b-b')$は $m$ の倍数である．また, $ab-a'b'=(a-a')b+a'(b-b')$ も $m$ の倍数である．すなわち(1)が示された．

(1)から $a\equiv a'\quad (\bmod.\ m)$ なら次のことが成り立つ．
    1)    任意の整数 $N$ に対して $Na\equiv Na'\quad (\bmod.\ m)$．
    2)    数学的帰納法と組みあわせて自然数$\alpha$に対し $a^{\alpha}\equiv a'^{\alpha}\quad (\bmod.\ m)$．

ふたたび(1)から $Na^{\alpha}b^{\beta}c^{\gamma} \cdots \equiv Na'^{\alpha}{b'}^{\beta}{c'}^{\gamma} \cdots\quad (\bmod.\ m)$である．

もういちど(1)から $\sum Na^{\alpha}b^{\beta}c^{\gamma} \cdots \equiv \sum Na'^{\alpha}{b'}^{\beta}{c'}^{\gamma} \cdots(\bmod.\ m)$となり (2)が示された． (証明終わり)

合同式に関する二つの定理を紹介する．

第一は数の等式での命題

$$ab=ac\ かつ\ a\ne 0 ならば b=c$$

に対応するものである．

定理 11        $ac\equiv bc\quad (\bmod.\ m)\ かつ\ (c,\ m)=1\ ならば a\equiv b\quad (\bmod.\ m)$

証明     仮定から $ac-bc$ は $m$ の倍数つまり整数 $N$ で $ac-bc=(a-b)c=mN$となるものがある． $m$ と $c$ は互いに素なのでこれから $a-b$ が $m$ の倍数であることがわかる．つまり

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

が示された． (証明終わり)

第二は，逆数の存在に関するものである．

定理 12        $a$と$m$が互いに素なとき $ax\equiv 1\quad (\bmod.\ m)$ となる整数$x$が存在する．

証明     $a$と$m$が互いに素なので，一次不定方程式

$$ax+my=1$$

は整数解 $(x,\ y)=(\alpha,\ \beta)$をもつ．

$$a\alpha=1-m\beta\equiv 1\quad (\bmod.\ m)$$

なので$x=\alpha$が条件を満たす整数である． (証明終わり)

注意 2        ここは高校数学範囲を越えることであるが，定理10の意味は，2つの剰余類からそれぞれそこに属する整数をとりだし， その加法や乗法をおこなうと，その和や積の属する剰余類は，とりだした整数によらず確定する，ということである．この結果，剰余類の間に加法や乗法を定めることができる． 合同式(1)は，このようにつかんではじめてその意味がわかる．