math - 当模值非质数时如何在除法方程中使用模运算符

Question

我知道 (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

请告诉我如何解决这种问题？？

Answer 1

如果 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。