somemo's diary

プログラマ、雑記、プログラミング関係はLinkから、数式はこっちでまとめていることが多い

アルゴリズム

【数学】2つの整数の積の剰余とそれぞれの剰余の積の剰余が等しい

数式 (a * b) mod m = ((a mod m) * (b mod m)) mod m についての記事です。 アルゴリズムを学ぼうという書籍の問題「aのk乗をmで割った余りを求める」ときに使われていました。 右辺を左辺の形に展開していきます。 余りを数式で定義する aをmで割った余り…