数式で独楽する

数式を使って楽しむブログです

[tex: ]

合同式の積

2つの整数 x,yについて、

  •  x pで割った余りと y pで割った余りが等しい

ことを

\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}
ab \equiv cd \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}
ab &=& (a'p +r)(b'p +r') &=& a'b'p^2 +(a'r' +b'r)p +rr'\\
cd &=& (c'p +r)(d'p +r') &=& c'd'p^2 +(c'r' +d'r)p +rr'
\end{eqnarray}です。

ゆえに
\begin{equation}
ab \equiv cd \mod p
\end{equation}が成り立ちます。

toy1972.hatenablog.com