【数学】2つの整数の積の剰余とそれぞれの剰余の積の剰余が等しい - somemo programming etc.

数式 (a * b) mod m = ((a mod m) * (b mod m)) mod m についての記事です。 アルゴリズムを学ぼうという書籍の問題「aのk乗をmで割った余りを求める」ときに使われていました。 右辺を左辺の形に展開していきます。 余りを数式で定義する aをmで割った余りをxとすると、aはmの倍数と剰余xの和なので、a = m * n1+ x より x = a - m * n1 同様にbをmで割った余りをyとすると、 y = b - m * n2 右辺の展開 右辺は (a - m * n1) * (b - m * n2) をmで割った余りとなる。x * yを展開すると、 ab -am(n2) -bm(n1) + m^2(n1)(n2) = m(-a(n2) -b(n1) +m(n1)(n2)) + ab となる (a * b) mod m = z とすると (a *