2つの整数について、
を
で割った余りと
を
ことを
\begin{equation}
x \equiv y \mod p
\end{equation}
で表します。これを「合同式」といいます。
合同式には、次の性質があります。
\begin{eqnarray}
a & \equiv & c \mod p \\
b & \equiv & d \mod p
\end{eqnarray}の場合、以下の関係が成り立ちます。
\begin{equation}
a +b \equiv c +d \mod p
\end{equation}
本項では、合同式の和について確認します。
\begin{eqnarray}
a &=& a'p +r \\
b &=& b'p +r' \\
c &=& c'p +r \\
d &=& d'p +r'
\end{eqnarray}なので、
\begin{eqnarray}
a +b &=& (a' +b')p +(r +r') \\
c +d &=& (c' +d')p +(r +r')
\end{eqnarray}です。
ゆえに
\begin{equation}
a +b \equiv c +d \mod p
\end{equation}が成り立ちます。
