模运算除法性质 [英] 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屋!