cafelier2010/04/16 13:28素数でないと成り立たないです。m(x)=x%MODVALとして、m(x)とm(y)からm(x/y)を求めたいわけなのでx/y=z ⇔ x=zy ⇒ m(x)=m(z)m(y) ⇒ m(x)m(y)^{MODVAL-2}=m(z)m(y)^{MODVAL-1} ⇒(フェルマーの小定理より)⇒ m(x)m(y)^{MODVAL-2}=m(z)こんな感じ
cafelier2010/04/16 13:37素でない場合はそもそも先にmodを取ってしまうと情報が落ちて割り算が不可能になってしまうので、パスカルの三角形か何かで、割り算を回避して式を立てる必要があります。
n4_t2010/04/16 13:51腑に落ちました。どうもありがとうございます！
m(x)=x%MODVALとして、m(x)とm(y)からm(x/y)を求めたいわけなので
x/y=z ⇔ x=zy ⇒ m(x)=m(z)m(y) ⇒ m(x)m(y)^{MODVAL-2}=m(z)m(y)^{MODVAL-1} ⇒(フェルマーの小定理より)⇒ m(x)m(y)^{MODVAL-2}=m(z)
こんな感じ