アルゴリズム論特論(塩田)第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$ で割った余りなら1桁の数だけで計算できる、という例です。
 何故こんな計算をして良いか、という理由は、次の定理が成り立つからです:
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$ で割った余りに取り換えてはいけません。