%演算子(余り計算、moduro)を使った式を証明したい

質問

％演算子に関して以下の法則が成り立ちそうな
気がしますが、証明が苦手で立証できません。
(％演算子とは余りを求める演算子とします)

(a*b)%c <=> (a%c)*(b%c)%c

これを証明しているサイトや、%演算子の法則などに
ついて纏めているサイトなどご存じないでしょうか？
または証明のヒントなどご教示頂けないでしょうか。

夏休みの宿題っぽいですが、全然関係ないです。
Cでプログラム書いていて、bがコンパイラで扱えない
ほど大きい定数なので、予めb%cの計算結果に
置き換えたいのです(cも定数)。
wikipediaなどで調べたのですが、分配法則、
交換法則などの説明には%演算子が含まれておらず、
質問した次第です。
よろしくお願いします。

回答No.2

age_momo · ベストアンサー

wikipediaを検索するなら『合同式』でどうぞ。

(a*b)%c <=> {(a%c)*(b%c)}%cは次のように考えれば証明できます。
a=hc+m
b=kc+n ただしm,n<c

とすると
a*b =(hc+m)(kc+n)=c(hkc+hn+km)+mn
(a*b)%c=(m*n)%c

一方、
a%c=m,b%c=nより
右辺=(m*n)%c
で等しくなります。

お礼

No.1さんの書かれた、
aをｃで割ったときの商をx，あまりをd，…
の説明と合わせて読んで理解できました。

Wikipediaの「合同式」に書かれていたんですね！
探し方が甘かったと反省しました。
しかし、これを読んでも理解にたどり着けなかったので、
回答して頂いて本当に助かりました。
ありがとうございます。

回答No.1

sunasearch

aをｃで割ったときの商をx，あまりをd，
bをｃで割ったときの商をy，あまりをe，として，

a=xc+d,b=yc+eとおいて計算してみましょう．

すると，両辺とも(d*e)%cになり，一致します．

お礼

No.2さんの書かれた途中式と合わせて読んで
理解できました。
自分の中では仮説だったので、これで堂々と
使えますね。
ありがとうございます！