2つの整数について、
を
で割った余りと
を
ことを
\begin{equation}
x \equiv y \mod p
\end{equation}
で表します。これを「合同式」といいます。
合同式には、次の性質があります。
本稿では、合同式を定数で割る場合について確認します。
\begin{equation}
ka \equiv kc \mod p
\end{equation}について、が互いに素であれば、
\begin{equation}
a \equiv c \mod p
\end{equation}が成り立ちます。
\begin{eqnarray}
ka &=& ka'p +kr \\
kc &=& kc'p +kr
\end{eqnarray}なので、
\begin{eqnarray}
a &=& a'p +r \\
c &=& c'p +r
\end{eqnarray}です。
つまり、
\begin{equation}
a \equiv c \mod p
\end{equation}が成り立ちます。
ただし、先に述べた通り、が互いに素の場合に限ります。
例えば、
\begin{equation}
70 \equiv 40 \mod 6
\end{equation}の両辺を5で割ると、5と6は互いに素であり
\begin{eqnarray}
70 &=& 6 \times 11 +4 \\
40 &=& 6 \times 6 +4 \\
14 &=& 6 \times 2 +2 \\
8 &=& 6 \times 1 +2
\end{eqnarray}なので
\begin{equation}
14 \equiv 8 \mod 6
\end{equation}が成り立ちます。
\begin{equation}
46 \equiv 28 \mod 6
\end{equation}の両辺を2で割ると、2と6は互いに素ではなく、
\begin{eqnarray}
46 &=& 6 \times 7 +4 \\
28 &=& 6 \times 4 +4 \\
23 &=& 6 \times 3 +5 \\
14 &=& 6 \times 2 +2
\end{eqnarray}なので
\begin{equation}
23 \equiv 14 \mod 6
\end{equation}は成り立ちません。
法と互いに素でない定数
で割ることは、通常の演算において0で割ることに相当するため、このようなことが起こるのです。
