アルゴリズム論特論（塩田）第5回 (2) 法演算
法演算
Def.4 法 $n$ で合同な数を「同じ」と思って合同式の形で計算することを法演算と言う。
計算のテクニック
- $n$ の倍数は $0$ に置き換えてよい。
- 数を $n$ で割った余りに置き換えることで、扱う数を小さくする。
Ex.5 (1) $\bmod 7$ で $6\,! = $ ?
\begin{align}
6\,! &\equiv 6 \times 5 \times 4 \times 3 \times 2 \times 1 \\
&\equiv (-1) \times (-2) \times (-3) \times 3 \times 2 \times 1 \\
&\equiv (-1) \times 6 \times 6 \\
&\equiv (-1) \times (-1) \times (-1) \equiv -1 \equiv 6 \pmod{7}\\
\end{align}
(2) $\bmod 7$ で $3^6 = $ ?
\begin{align}
3^6 & \equiv (3^2)^3 \equiv 9^3 \equiv 2^3 \equiv 8 \equiv 1 \pmod{7}\\
\end{align}
法演算を使わなければ、$6\,!=720=7 \times 103 - 1$, $3^6=729=7 \times 104+1$ ですが、
$7$ で割った余りなら１桁の数だけで計算できる、という例です。
何故こんな計算をして良いか、という理由は、次の定理が成り立つからです：
Th.6 $\bmod n$ で
$a \equiv b\quad$ かつ $\quad c \equiv d$
であれば
(1)$\quad a+c \equiv b+d$
(2)$\quad a-c \equiv b-d$
(3)$\quad a \times c \equiv b \times d$
$\require{color}$
証明 (1), (2) 条件より $\textcolor{red}{a-b}$, $\textcolor{red}{c-d}$ が $n$ の倍数であるから、
$(a \pm c) - (b \pm d) = (\textcolor{red}{a-b}) \pm (\textcolor{red}{c-d})$
は $n$ の倍数ゆえ。
(3) 同じく
$ac - bd = ac - bc + bc -bd =(\textcolor{red}{a-b})c + b(\textcolor{red}{c-d})$
は $n$ の倍数ゆえ。(証明終)
Cor.7 $a \equiv b \pmod n$ ならば、$\forall e \geqq 0$ について
$a^e \equiv b^e \pmod n$
※ $+$, $-$, $\times$, べき乗に関して $\equiv$ は「イコール感覚」で扱ってよい、ということです。
※ ただし、べき指数 $e$ は $n$ で割った余りに取り換えては
いけません。