2つの整数について、
を
で割った余りと
を
ことを
\begin{equation}
x \equiv y \mod p
\end{equation}
で表します。これを「合同式」といいます。
合同式には、次の性質があります。
\begin{equation}
a \equiv c \mod p
\end{equation}の場合、以下の関係が成り立ちます。
\begin{equation}
ka \equiv kc \mod p
\end{equation}
本項では、合同式の定数倍について確認します。
\begin{eqnarray}
a &=& a'p +r \\
c &=& c'p +r
\end{eqnarray}なので、
\begin{eqnarray}
ka &=& ka'p +kr \\
kc &=& kc'p +kr
\end{eqnarray}です。
つまり、
\begin{equation}
ka \equiv kc \mod p
\end{equation}が成り立ちます。
ここで、
\begin{equation}
kr = lp
\end{equation}であれば、つまりが
と互いに素ではない場合、定数倍した余りが
の定数倍となり、
\begin{equation}
ka \equiv 0 \mod p
\end{equation}となります。
言い換えると、法と互いに素でない定数
を掛けることは、通常の演算で0を掛けることに相当します。
