0

（a * b）％M =（a％M * b％M）％M

しかし、方程式が:(（a * b）/ c）％Mの場合はどうなりますか？ここでも上記のロジックを使用できるとは思いません..そしてここでMは非素数です..あなたは（a * b）/cが浮動小数点になることはありません。

For eg:
If a=10 b=9 and c=6,M=4 then (a*b)/c=15 and 15%4=3
but if I use the property as it is with multiplications then ((10%4*9%4)/(6%4))%4= (2*1)/2=1

このような問題の解決方法を教えてください。

4

1 に答える 1

2

cとMが互いに素である場合、c ^ -1％Mを掛けることができ、数学は機能するはずです。ただし、GCD（c、M）> 1の場合、c ^ -1％Mは存在せず、私が知っている簡単な方法はありません。

c ^ -1％Mとは、c * c ^ -1％M=1となる数です。たとえば、c=2およびM=9の場合、2 * 5％9 = 10％9 = 1であるため、c ^ -1％M=5です。

拡張ユークリッドアルゴリズムを使用してc^-1％Mを計算できます。つまり、 ac + bM = 1になるため、ac = 1 +（-b）Mおよびac％M=1になります。

于 2012-08-10T02:13:10.890 に答える