Que signifie mod en algorithme ?

Dans l'algorithme, mod signifie prendre le modulo, qui prend le reste. L'opération mod, c'est-à-dire l'opération de reste, est une opération qui trouve le reste de la division d'un entier x par un autre entier y dans des opérations entières, sans tenir compte du quotient de l'opération.

L'opération mod, c'est-à-dire l'opération de reste, est une opération qui trouve le reste de la division d'un entier x par un autre entier y dans des opérations entières, et ne prend pas en compte le quotient d’opération. Il existe une opération MOD en programmation informatique, et son format est : mod(nExp1,nExp2), qui est le reste après la division de deux expressions numériques.

Éditeur d'opération Modulo p

Étant donné un entier positif p et tout entier n, il doit y avoir une équation

n = kp + r où k et r sont des nombres entiers, et 0 ≤ r

Pour l'entier positif p et les entiers a, b, l'opération suivante est définie :

Opération modulo : un mod p représente le reste de la division a par p.

Addition modulo p : (a + b) mod p, le résultat est le reste de la somme arithmétique de a+b divisé par p, soit (a+b) = kp +r, alors ( une+ b) mod p = r.

Soustraction module p : (a-b) mod p, le résultat est le reste de la différence arithmétique de a-b divisé par p.

Multiplication module p : (a × b) mod p, le résultat est le reste de la multiplication arithmétique a × b divisé par p.

On peut constater que l'opération modulo p a de nombreuses règles similaires aux quatre opérations arithmétiques ordinaires, telles que :

结合律	((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

Preuve simple de la première formule :

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

Supposer

a = k1*p + r1

b = k2*p + r2

c = k3*p + r3

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

Si (r1 + r2) >= p, alors

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

sinon

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

puis effectuez l'opération de somme modulo p avec c, et le résultat de

est le reste de la somme arithmétique de r1 + r2 + r3 divisé par p.

Le même résultat peut être obtenu en calculant le côté droit, et la preuve est obtenue.

Égal modulo p

Si deux nombres a et b satisfont a mod p = b mod p, alors ils sont dits égaux modulo p, noté comme

a ≡ b (mod p)

On peut prouver qu'à ce moment, a et b satisfont a = kp + b, où k est un entier.

Pour l'égalité modulo p et la multiplication modulo p, il existe une règle complètement différente des quatre opérations arithmétiques. Dans les quatre opérations arithmétiques, si c est un entier non nul, alors

ac = bc peut être obtenu sous la forme a =b

Cependant, dans l'opération modulo p, cette relation est vraie. n'existe pas, par exemple :

(3 x 3) mod 9 = 0

(6 x 3) mod 9 = 0

Mais

3 mod 9 = 3

6 mod 9 =6

Théorème (loi d'élimination) : Si pgcd(c,p) = 1, alors ac ≡ bc mod p peut en déduire a ≡ (b mod p)

Preuve :

Parce que ac ≡ bc (mod p)

donc ac = bc + kp, c'est-à-dire c(a-b) = kp

Parce que c et p n'ont pas de facteurs communs autres que 1, donc pour que la formule ci-dessus soit vraie, l'une des deux conditions suivantes doit être remplie

1) c peut être divisé par k

2) a = b

Si 2 n'est pas vrai, alors c|kp

Parce que c et p n'ont pas de facteurs communs, il est évident que c|k, donc k = ck '

Par conséquent c(a-b)=kp peut être exprimé comme c (a-b) =ck'p

Par conséquent a-b = k'p, on obtient a ≡ b (mod p)

Si a = b, alors a ≡ b mod p est évidemment vrai

Certifié

Pour plus de connaissances connexes, veuillez visiter : Site Web PHP chinois !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!