the art of computer programming 1.2.4 を読む
1.2.4 整数関数と初等整数論
modについて
(a) なら
(b) なら
(c) は
の整数倍
となる。例えば、
となる。最後の式は
を考えると、あまりは2,1,0,2,1,0となっているので-1を3で割った余りはその順序に従って2となる。なので、-2を3で割った余りは1となる。
modの法則
法則A. で
かつ
なら
かつ
である。
法則B. で
かつ
で、なおかつ
なら
である。
法則C. とするとき、
の必要十分条件は
である。
法則D. なら
になる必要十分条件は
かつ
である。
* は
と
が互いに素であることを表す。
フェルマーの小定理は法則AとBから導き出される。
フェルマーの小定理
が素数なら、すべての整数
に対して
になる。
証明
は素数なので、
である。そこで以下の数値について考える。
これら 個の値は異なる値である。なので、非負で
より小さい数は、
と続く。そこで、法則Aより、次の式が成り立つ。
この合同式の両辺に を掛けると次のようになる
これを法則Bに当てはめると、
かつ
で、なおかつ
なので
である。
これで定理は証明された。
この定理を応用すると、
となり、さらに
となる。この式は で割ることは
を
で割った余りと等しいということである。
で割ることを
にすることの何が嬉しいのかというと、小数の精度を気にしなくても良くなることである。
有理数でない限り(有理数であっても)少なからず誤差が発生する。しかし、掛け算の場合はオーバーフローの問題を考えなければ、メモリを食い尽くさないかぎりコンピュータで表現が可能である。
この問題の例としてAtcoder Beginner Contestがある。この問題では
を使用して問題を解く。
演習問題
16.[M10]
ということは
は
の倍数であり、
である。
式を変形すると、
は、
が
なので、
をとってもとらなくても結果は変わらない。よって、
となる。