Was bedeutet Mod im Algorithmus?

Im Algorithmus bedeutet mod, dass man den Modul nimmt, also den Rest nimmt. Die Mod-Operation, also die Restoperation, ist eine Operation, die den Rest der Division einer ganzen Zahl x durch eine andere ganze Zahl y in ganzzahligen Operationen ermittelt, ohne den Quotienten der Operation zu berücksichtigen.

Die Mod-Operation, also die Restoperation, ist eine Operation, die den Rest der Division einer ganzen Zahl x durch eine andere ganze Zahl y in ganzzahligen Operationen ermittelt, ohne den Quotienten der Operation zu berücksichtigen. In der Computerprogrammierung gibt es eine MOD-Operation und ihr Format ist: mod(nExp1,nExp2), was der Rest nach der Division zweier numerischer Ausdrücke ist.

Modulo p-Operationseditor

Gegeben eine positive ganze Zahl p und eine beliebige ganze Zahl n, muss es eine Gleichung geben

n = kp + r, wobei k und r ganze Zahlen sind und 0 ≤ r < der Quotient von n dividiert durch p, und r ist der Rest von n dividiert durch p.

Für positive ganze Zahlen p und ganze Zahlen a, b ist die folgende Operation definiert:

Moduloperation: a mod p stellt den Rest der Division von a durch p dar.

Addition modulo p: (a + b) mod p, das Ergebnis ist der Rest der arithmetischen Summe von a+b dividiert durch p, also (a+b) = kp +r, dann (a+b) mod p =r.

Modul p-Subtraktion: (a-b) mod p, das Ergebnis ist der Rest der arithmetischen Differenz von a-b dividiert durch p.

Multiplikation modulo p: (a × b) mod p, das Ergebnis ist der Rest der arithmetischen Multiplikation von a × b dividiert durch p.

Es kann festgestellt werden, dass die Modulo-p-Operation viele ähnliche Regeln wie die vier gewöhnlichen arithmetischen Operationen aufweist, wie zum Beispiel:

Assoziativgesetz	((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
kommutativ Gesetz	(a + b) mod p = (b+a) mod p (a × b) mod p = (b × a) mod p
Distributivgesetz	( (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

Einfach Beweis davon A-Formel:

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

Angenommen

a = k1*p + r1

b = k2 *p + r2

c = k3*p + r3

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

Wenn (r1 + r2) >= p , dann

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

Sonst

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

Und führen Sie dann die Modulo-p-Summenoperation mit c aus, das Ergebnis von

ist r1 + r2 + Der Rest der arithmetischen Summe von r3 dividiert durch p.

Das gleiche Ergebnis kann durch Berechnung der rechten Seite erzielt werden, und der Beweis wird erhalten.

Gleich modulo p

Wenn zwei Zahlen a und b einen mod p = b mod p erfüllen, dann werden sie als gleich modulo p bezeichnet, bezeichnet als

a ≡ b (mod p)

Das kann Dies kann bewiesen werden, wenn a und b a = kp + b erfüllen, wobei k eine ganze Zahl ist.

Für Gleichheit modulo p und Multiplikation modulo p gilt eine völlig andere Regel als die vier Rechenoperationen. Wenn c in den vier arithmetischen Operationen eine Ganzzahl ungleich 0 ist, kann

ac = bc als a =b

erhalten werden. Bei der Modulo-p-Operation existiert diese Beziehung jedoch nicht, zum Beispiel:

(3 x 3) mod 9 = 0

(6 x 3) mod 9 = 0

aber

3 mod 9 = 3

6 mod 9 =6

Theorem (Eliminationsgesetz): Wenn gcd(c, p) = 1, dann kann aus ac ≡ bc mod p abgeleitet werden a ≡ (b mod p)

Beweis:

Weil ac ≡ bc (mod p)

also ac = bc + kp, also c(a-b ) = kp

Da c und p keine anderen gemeinsamen Faktoren als 1 haben, muss eine der folgenden beiden Bedingungen erfüllt sein, damit die obige Formel wahr ist

1) c kann k teilen

2) a = b

Wenn 2 nicht wahr ist, dann c|kp

Da c und p keine gemeinsamen Faktoren haben, ist es offensichtlich, dass c|k, also k = ck'

Daher kann c(a-b)=kp als c ausgedrückt werden (a-b) =ck'p

Daher ist a-b = k'p, wir erhalten a ≡ b (mod p)

Wenn a = b, dann ist a ≡ b mod p offensichtlich etabliert

Bewiesen

Für weitere verwandte Kenntnisse , besuchen Sie bitte: Chinesische PHP-Website!

Das obige ist der detaillierte Inhalt vonWas bedeutet Mod im Algorithmus?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!