the art of computer programming 1.2.4 を読む

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 ma \equiv b かつ x \equiv y なら a \pm x \equiv b \pm y かつ ax \equiv byである。

    法則B.\pmod max \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 bab が互いに素であることを表す。

 

    フェルマーの小定理は法則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-zy の倍数であり、(x-z) \bmod y =0 である。

 式を変形すると、

 x \bmod y - z \bmod y = 0

 x \bmod y = z \bmod y

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

 x \bmod y = zとなる。