乗算で余りを計算するまえにそれぞれの値の余りを求めた場合について

Question

前提・実現したいこと

https://atcoder.jp/contests/atc002/tasks/atc002_b
についての質問です

n,m,pが与えられ、n ^ p mod m を求める問題です。
pow(n,p,m)とpow(n%m, p%m, m)の値が違う場合があるのですが理解できていません。
違う例）n,m,p = 123456789, 234567894, 6574837563712

(a*b) mod m = {(a mod m) * (b mod m)} mod m
であるならばpow(n,p,m) == pow(n%m, p%m, m)のように思えるのですが、なにか見落としているのだとわかっているのですが、理解できていません。

べき算の場合は計算してから余りを求めないといけないのでしょうか。

こういうものだ、ということであればそれで構わないのですが、自分が見落としている点などがありましたらご指摘お願いいたします。

Comments

[Zuishin]

n ^ p は n * p ではありません。n を p 回かけたものです。
p % m を求めるのは意味がありません。

繰り返し二乗法について非常にわかりやすい解説がありますので読んでください。

[YT0014]

乗算は、一般には、掛け算を意味します。べき乗計算の意味だと思われますが、誤解が起きないように、他の用語への書き換えをお勧めします。

[fana]

うおおおお，私しか「？」ってなってないみたいで恥ずかしいけど，まず
What is "pow" ?
と問うぜ！

pow( n,p,m ) = n^p mod m

という話だと思って良い？

[afushi]

pow( n,p,m ) = n^p mod m
であってます。
乗算からべき乗に変更しました。
ご指摘ありがとうございます。

[Zuishin]

乗算からべき乗に変更したことで解決しないのか。
べき乗でその法則が成り立つと、どこの資料に書いてあるんですか？
引用してください。

[fana]

n ^ p = { n^(p-1) * n } と考えて，ここに

> (a*b) mod m = {(a mod m) * (b mod m)} mod m

を適用することを考えます．
で，同様に n^(p-1) もまた，{ n^(p-2) * n } として…　と繰り返していくことを考えると，

> (a*b) mod m = {(a mod m) * (b mod m)} mod m

の末尾にある mod m の計算が毎度毎度必要となるように思えます．
（私の頭だとここで行き詰ります）
この状態から

> pow(n%m, p%m, m)

のようにできる，という結論までの間にちょっと大きな飛躍があるように感じるので，この間の部分をどう考えた話なのか，というのを可能であれば少し説明頂けると良いのではないかと存じます．

[Zuishin]

「その法則」が通じないかもしれないので書き直します。

(5 * 4) % 3 = ((5 % 3) * (4 % 3)) % 3 = 2

乗算ならこれが成り立ちます。

(5 ^ 4) % 3 = 625 % 3 = 1
((5 % 3) ^ (4 % 3)) % 3 = (2 ^ 1) % 3 = 2
1 ≠ 2

べき乗だと必ずしも成り立ちません。

べき乗でも成り立つとどこに書いてあるんですか？

[Zuishin]

解決したけど、わかったんだかわからないんだか。

Answer 1

言葉がまず間違ってます。
「乗算」は n * p です。
「べき乗」は n ^ p です。

一般に、 (n ^ p) mod m と (n mod m)^(p mod m) mod m は一致しません。
数学的にはオイラーの定理で示されるように、 n≠0 ならば n^φ(m) ≡ 1 mod m なので p - (p mod m) が φ(m) の倍数であれば一致するでしょう。