Shulou(Shulou.com)06/02 Report--

Xiaobian to share with you what mod means in the algorithm, I believe most people still do not know how, so share this article for your reference, I hope you have a lot of harvest after reading this article, let's go to understand it together!

In arithmetic, mod means modulo, or remainder. The mod operation, or remainder operation, is an integer operation that finds the remainder of dividing one integer x by another integer y, regardless of the quotient of the operation.

The mod operation, or remainder operation, is an integer operation that finds the remainder of dividing one integer x by another integer y, regardless of the quotient of the operation. In computer programming, there is a MOD operation in the form mod(nExp1,nExp2), which is the remainder of the division of two numerical expressions.

modulo p operation editing

Given a positive integer p, any integer n, there must be an equation

n = kp + r where k and r are integers and 0 ≤ r

< p，称呼k为n除以p的商，r为n除以p的余数。 对于正整数p和整数a,b，定义如下运算： 取模运算：a mod p 表示a除以p的余数。 模p加法：(a + b) mod p ，其结果是a+b算术和除以p的余数，也就是说，(a+b) = kp +r，则 (a+b) mod p = r。 模p减法：(a-b) mod p ，其结果是a-b算术差除以p的余数。 模p乘法：(a × b) mod p，其结果是 a × b算术乘法除以p的余数。 可以发现,模p运算和普通的四则运算有很多类似的规律，如： 结合律 ((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p ((a*b) mod p * c)mod p = (a * (b*c) mod p) mod p 交换律 (a + b) mod p = (b+a) mod p (a × b) mod p = (b × a) mod p 分配律 ((a +b)mod p × c) mod p = ((a × c) mod p + (b × c) mod p) mod p (a×b) mod c=(a mod c * b mod c) mod c (a+b) mod c=(a mod c+ b mod c) mod c (a-b) mod c=(a mod c- b mod c) mod c 简单的证明其中第一个公式： ((a+b) mod p + c) mod p = (a + (b+c) mod p) mod p 假设 a = k1*p + r1 b = k2*p + r2 c = k3*p + r3 a+b = (k1 + k2) p + (r1 + r2) 如果(r1 + r2) >

= p, then

(a+b) mod p = (r1 + r2) -p

otherwise

(a+b) mod p = (r1 + r2)

And c modulo p sum operation, get

The result is the arithmetic sum of r1 + r2 + r3 divided by the remainder of p.

The same result can be obtained by calculating on the right side, which is proved.

modulo p equals

If two numbers a and b satisfy a mod p = b mod p, then they are said to be equal modulo p, denoted as

a ≡ b (mod p)

It can be proved that a and b satisfy a = kp + b, where k is an integer.

For equality modulo p and multiplication modulo p, there is a rule quite different from that of the four operations. In four operations, if c is a non-zero integer, then

ac = bc yields a =b

But in modulo p operations, this relation does not exist, for example:

(3 x 3) mod 9 = 0

(6 x 3) mod 9 = 0

but

3 mod 9 = 3

6 mod 9 =6

Theorem (elimination law): if gcd(c,p) = 1, then ac = bc mod p can be deduced a =(b mod p)

Proof:

because ac = bc (mod p)

So ac = bc + kp, which means c(a-b) = kp.

Since c and p have no common divisor other than 1, one of the following two conditions must be satisfied for the above expression to hold

1)c divides k.

2) a = b

If 2 is not true, then c| kp

Since c and p have no common divisor, it is obvious that c| k, so k = ck'

Thus c(a-b)=kp can be expressed as c(a-b) =ck'p

Therefore a-b = k'p, resulting in a $> b (mod p)

If a = b, then a = b mod p obviously holds.

get proof

The above is "what does mod mean in the algorithm" all the contents of this article, thank you for reading! I believe that everyone has a certain understanding, hope to share the content to help everyone, if you still want to learn more knowledge, welcome to pay attention to the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.