What does mod mean in algorithm?

In the algorithm, mod means taking the modulo, which is taking the remainder. The mod operation, that is, the remainder operation, is an operation that finds the remainder of dividing an integer x by another integer y in integer operations, without considering the quotient of the operation.

The mod operation, that is, the remainder operation, is an operation that finds the remainder of dividing an integer x by another integer y in integer operations, regardless of the operation. quotient. There is MOD operation in computer programming, and its format is: mod(nExp1,nExp2), which is the remainder after dividing two numerical expressions.

Modulo p operation editor

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

n = kp r where k , r is an integer, and 0 ≤ r

For positive integer p and integers a and b, the following operation is defined:

Modulo operation: a mod p represents the remainder of dividing a by p.

Addition modulo p: (a b) mod p, the result is the remainder of the arithmetic sum of a b divided by p, that is, (a b) = kp r, then (a b) mod p = r.

Modul p subtraction: (a-b) mod p, the result is the remainder of the arithmetic difference a-b divided by p.

Modul p multiplication: (a × b) mod p, the result is the remainder of the a × b arithmetic multiplication divided by p.

It can be found that the modular p operation has many similar rules to the four ordinary arithmetic operations, such as:

Associative Law	((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
COMmutativity	(a b) mod p = (b a ) mod p (a × b) mod p = (b × a) mod p
##distributive law	((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

Simple proof of the first formula:

((a b) mod p c) mod p = (a (b c) mod p) mod p

Assume

a = k1*p r1

b = k2*p r2

c = k3*p r3

a b = (k1 k2) p (r1 r2)

If (r1 r2) >= p, then

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

Otherwise

(a b) mod p = (r1 r2)

Then perform modulo p sum operation with c, and the result is

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

The same result can be obtained by calculating the right side, and the proof is obtained.

Equal modulo p

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 at this time, a and b satisfy a = kp b, where k is an integer.

For equality modulo p and multiplication modulo p, there is a completely different rule from the four arithmetic operations. In the four arithmetic operations, if c is a non-0 integer, then

ac = bc can be obtained as a =b

. However, in the modulo p operation, this relationship 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 deduce a ≡ (b mod p)

Proof:

Because ac ≡ bc (mod p)

so ac = bc kp, that is, c(a-b) = kp

Because c and p are not divided by 1 Common factors other than , then c|kp

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

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

Therefore a-b = k'p, it follows that a ≡ b (mod p)

If a = b, then a ≡ b mod p is obviously true

得证

For more related knowledge, please visit:

PHP中文网

!

The above is the detailed content of What does mod mean in algorithm?. For more information, please follow other related articles on the PHP Chinese website!