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]
ということは は の倍数であり、 である。
式を変形すると、
は、 が なので、 をとってもとらなくても結果は変わらない。よって、
となる。