数式で独楽する

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

[tex: ]

合同式のべき乗

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

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

ことを

\begin{equation}
x \equiv y \mod p
\end{equation}

で表します。これを「合同式」といいます。


合同式には、次の性質があります。
\begin{equation}
a \equiv c \mod p
\end{equation}の場合、以下の関係が成り立ちます。

\begin{equation}
a^k \equiv c^k \mod p
\end{equation}

本項では、合同式のべき乗(冪乗)について確認します。

\begin{eqnarray}
a &=& a'p +r \\
c &=& c'p +r
\end{eqnarray}なので、
\begin{eqnarray}
a^k &=& (a'p +r)^k \\
c^k &=& (c'p +r)^k
\end{eqnarray}です。
ここで右辺を展開すると、二項定理により r^k以外の項は全て pを因数に持ちます。
二項定理 - 数式で独楽する

つまり、
\begin{eqnarray}
a^k & \equiv & r^k \mod p \\
c^k & \equiv & r^k \mod p \\
\therefore \quad a^k & \equiv & c^k \mod p
\end{eqnarray}が成り立ちます。

toy1972.hatenablog.com