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{equation}
a -b \equiv c -d \mod p
\end{equation}
合同式の差 - 数式で独楽する
積
\begin{equation}
ab \equiv cd \mod p
\end{equation}
合同式の積 - 数式で独楽する
冪乗
\begin{equation}
a^k \equiv c^k \mod p
\end{equation}
合同式のべき乗 - 数式で独楽する
定数倍
\begin{equation}
ka \equiv kc \mod p
\end{equation}
が互いに素でない場合、
\begin{equation}
ka \equiv 0 \mod p
\end{equation}となる場合があります。
合同式の定数倍 - 数式で独楽する
定数による除算
が互いに素の場合、
\begin{equation}
ka \equiv kc \mod p
\end{equation}ならば
\begin{equation}
a \equiv c \mod p
\end{equation}
合同式の定数による除算 - 数式で独楽する
