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

整数の合同

整数 $a$$b$の差が$m$の倍数であるとき,
\begin{displaymath}
a と b は m を法として互いに\textbf{合同}である.
\end{displaymath}

といい,次のように記す.
\begin{displaymath}
a\equiv b\quad (\bmod.\ m)
\end{displaymath}

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

定理 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$ とする.

\begin{displaymath}
a=mq_1+r_1,\ b=mq_2+r_2
\end{displaymath}

2式の辺々を引いて$a-b=mq$ を用いると
\begin{displaymath}
mq=(q_1-q_2)m+r_1-r_2
\end{displaymath}

つまり
\begin{displaymath}
\vert m\vert\vert q-q_1+q_2\vert=\vert r_1-r_2\vert
\end{displaymath}

もし $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$ となり矛盾する.
\begin{displaymath}
∴\quad q-q_1+q_2=0,\quad r_1-r_2=0
\end{displaymath}

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

\begin{displaymath}
a=mq_1+r,\ b=mq_2+r
\end{displaymath}

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