模运算除法性质 [英] modulus operation division property

问题描述

我有一个等式

((a*b*c*d)/(e*f*g*h))%m

我的问题是，我可以首先应用乘法属性

My question is , Can i first apply multiplication property

(a*b) mod(n) = (a*mod(n)) * (b*mod(n) ) mod(n)

到分子然后是分母，使分子和分母成为一个值，然后求解除法运算？

to numerator and then denominator , so that numerator and denominator becomes a single value , and then solve the division operation?

(a/b) mod(n) = (a*inv(b)) mod(n)    

推荐答案

让 N = a * b * c * d 和 D = e * f * g * h 。我们要计算：

(N/D) mod n = (N * inv(D)) mod n

我们可以通过以下方式在此处使用乘法属性：

We can use the multiplication property here in the following way:

(N * inv(D)) mod n = ((N mod n) * (inv(D) mod n)) mod n

要计算 N mod n ，我们可以再次应用乘法属性，因此答案是肯定的-您可以在解决除法运算之前将乘法属性应用于分子，因为无论如何您都必须这样做。

To calculate N mod n we can apply the multiplication property again so the first part of answer is yes - you can apply the multiplication property to the numerator before solving the division because you will have to do it anyway.

的结果（inv（D）mod n）是满足等式的数字 X ：

(D * X) mod n = 1
((D mod n) * (X mod n)) mod n = 1

如果在求解除法之前将乘法属性应用于分母，则会得到：

If you apply the multiplication property to the denominator before solving the division you will get:

(((D mod n) mod n) * (X mod n)) mod n = 1

但是（D mod n）mod n = D mod n ，所以没关系。这意味着答案的第二部分也是-您可以在解决除法运算之前将乘法属性应用于分母。

However (D mod n) mod n = D mod n so it doesn't matter. It means that the second part of the answer is also yes - you can apply the multiplication property to the denominator before solving the division.

这篇关于模运算除法性质的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！