合同式とその性質

この記事の所要時間：約 2分46秒

合同式(congruence)

$a, b$ は整数, $c$ は正の整数として, $a-b$ が $c$ で割り切れるとき

\begin{align*}
a\equiv b \pmod{c}
\end{align*}

と書き, この形の式を合同式といいます. また, このときの $c$ を合同式の法といいます.

また, 上の式を以下のように書くこともあります.

\begin{align*}
a \bmod c = b
\end{align*}

プログラム経験のある人なら, $a \% c$ という記号を使うと思いますが, 数学では $\bmod$ を使います.

合同式の両辺の $a$, $b$ は整数であることに注意してください. この部分が分数の形になる計算をする場合は, 割り切れているかを確認した上で合同式を使いましょう.

合同式は高校では習いませんが, 使えるようになれば整数の問題などの解答をコンパクトに書くことができます. 以下にも簡単な例を載せています.

合同式の重要な性質を以下に挙げます. 但し, ここでは合同式の法はすべて$p$とします.

1.$a\bmod b$ かつ $b\bmod c\Rightarrow a\bmod c$

2.$a\bmod b$ かつ $c\bmod d\Rightarrow a\pm c\bmod b\pm d$(複号同順), $ac\bmod bd$

3.$a\bmod b\Rightarrow ac\bmod bc$

4.$ac\bmod bc$ かつ $c$ と $p$ が互いに素$\Rightarrow a\bmod b$

5.$a\bmod b\Rightarrow a^n\bmod b^n$($n$は自然数)

1から4の性質は定義から簡単に導かれます. また, 5は1を繰り返し用いれば出てきます.

問題例.$20^16$ を9で割った余りはいくらか.

解答. 合同式の法を9として,

\begin{align*}
20^{16} &\equiv 2^{16}\\
&\equiv 16^4\\
&\equiv (-2)^4\\
&\equiv 16\\
&\equiv 7
\end{align*}

より割った余りは7.

このように合同式を用いると簡単に計算ができ, 分かりやすい解答を書くことができます.

整数に関する定理で, 合同式が関係しているものは沢山あります. 以下にその一部を挙げておきます.