次: 剰余系 上: 余りによる類別 前: 余りによる類別

整数の合同

整数 $a$と$b$の差が$m$の倍数であるとき,

$$a と b は m を法として互いに\textbf{合同}である．$$

といい，次のように記す．

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

次のことは高校数学範囲では証明なしに用いてよい． しかしまた，証明されることであることも知っておこう．

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

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

$$a=mq_1+r_1,\ b=mq_2+r_2$$

2式の辺々を引いて$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$$

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

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

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