Matchaldの日記

the art of computer programming 1.2.4 を読む

taocp the_art_of_computer_programming

1.2.4 整数関数と初等整数論

modについて

　(a) $y \gt 0$ なら $0 \le x \bmod y \lt y$

(b) $y \lt 0$ なら $0 \ge x \bmod y \gt y$

(c) $x-(x \bmod y)$ は $y$ の整数倍

　となる。例えば、

　 $5 \bmod 3 = 2$

$18 \bmod 3 = 0$

$-2 \bmod 3 = 1$

となる。最後の式は

$5 \bmod 3 = 2$

$4 \bmod 3 = 1$

$3 \bmod 3 = 0$

$2 \bmod 3 = 2$

$1 \bmod 3 = 1$

$0 \bmod 3 = 0$

　を考えると、あまりは2,1,0,2,1,0となっているので-1を3で割った余りはその順序に従って2となる。なので、-2を3で割った余りは1となる。

modの法則

　法則A. $\pmod m$ で $a \equiv b$ かつ $x \equiv y$ なら $a \pm x \equiv b \pm y$ かつ $ax \equiv by$ である。

法則B. $\pmod m$ で $ax \equiv by$ かつ $a \equiv b$ で、なおかつ $a \perp m$ なら $x \equiv y$ である。

法則C. $n \neq 0$ とするとき、 $a \equiv b \pmod m$ の必要十分条件は $an \equiv bn \pmod {mn}$ である。

法則D. $r \perp s$ なら $a \equiv b \pmod {rs}$ になる必要十分条件は $a \equiv b \pmod r$ かつ $a \equiv b \pmod s$ である。

＊ $a \perp b$ は $a$ と $b$ が互いに素であることを表す。

フェルマーの小定理は法則AとBから導き出される。

フェルマーの小定理

　 $p$ が素数なら、すべての整数 $a$ に対して $a^p \equiv a \pmod p$ になる。

　証明

　　 $p$ は素数なので、 $a \perp p$ である。そこで以下の数値について考える。

　　 $0 \bmod p, a \bmod p, 2a \bmod p, ... , (p - 1)a \bmod p$

　　これら $p$ 個の値は異なる値である。なので、非負で $p$ より小さい数は、 $0,1,2,3,4,...,p-1$ と続く。そこで、法則Aより、次の式が成り立つ。

　　 $(a)(2a) ... ((p-1)a) \equiv 1 \cdot 2 ... (p-1) \pmod p$

　　この合同式の両辺に $a$ を掛けると次のようになる

　　 $a^p(1 \cdot 2 ... (p-1) ) \equiv a(1 \cdot 2 ... (p-1) ) \pmod p$

　　これを法則Bに当てはめると、

　　 $a^p(1 \cdot 2 ... (p-1) ) \equiv a(1 \cdot 2 ... (p-1) ) \pmod p$ かつ $(1 \cdot 2 ... (p-1) ) \equiv (1 \cdot 2 ... (p-1) )$ で、なおかつ $(1 \cdot 2 ... (p-1) ) \perp p$ なので $a^p \equiv a$ である。

　　これで定理は証明された。

この定理を応用すると、

$a^{p-1} \equiv 1 \pmod p$

となり、さらに

$a^{p-2} \equiv a^{-1} \pmod p$

となる。この式は $a$ で割ることは $a^{p-2}$ を $p$ で割った余りと等しいということである。

$a$ で割ることを $a^{p-2} \bmod p$ にすることの何が嬉しいのかというと、小数の精度を気にしなくても良くなることである。

有理数でない限り(有理数であっても)少なからず誤差が発生する。しかし、掛け算の場合はオーバーフローの問題を考えなければ、メモリを食い尽くさないかぎりコンピュータで表現が可能である。

　この問題の例としてAtcoder Beginner Contestがある。この問題では

$a^{p-2} \equiv a^{-1} \pmod p$

　を使用して問題を解く。

演習問題

16.[M10]

　 $\frac{x-z}{y}=0$ ということは $x-z$ は $y$ の倍数であり、 $(x-z) \bmod y =0$ である。

　式を変形すると、

　 $x \bmod y - z \bmod y = 0$

　 $x \bmod y = z \bmod y$

　 $z \bmod y$ は、 $z$ が $0 \le z \lt y$ なので、 $\bmod$ をとってもとらなくても結果は変わらない。よって、

　 $x \bmod y = z$ となる。