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!