Modulare Division

Modulare Division sucht ein Residuum q, sodass b mal q kongruent a modulo n ist. In der gewöhnlichen Arithmetik dividieren Sie einfach; in der modularen Arithmetik ist Division die Multiplikation mit dem modularen Inversen des Divisors. Dieses Inverse existiert nur, wenn b und n teilerfremd sind. Kryptografie-Labore, Wettbewerbsprogrammierung, Hausaufgaben zu endlichen Körpern und Übungen zu linearen Kongruenzen brauchen diese Operation, doch viele Sprachen liefern nur einen GCD oder ein bloßes modulares Inverses und überlassen Ihnen den Multiplikationsschritt. Dieser Rechner nimmt die ganzen Zahlen a, b und den Modul n, invertiert b modulo n mit dem erweiterten euklidischen Algorithmus, wenn möglich, multipliziert mit a und liefert den eindeutigen nichtnegativen Quotienten von null bis n minus eins, zusammen mit dem Inversen, dem gcd und einem Prüfprodukt, damit Sie das Ergebnis prüfen können, ohne die Schritte neu abzuleiten.

Was modulare Division bedeutet und wann sie definiert ist

In den ganzen Zahlen hat jede von null verschiedene Zahl ein Reziprokes in den rationalen Zahlen, sodass Division außerhalb von null immer definiert ist. Modulo n ist das Bild strenger: Residuen bilden einen Ring, und nur Einheiten—Elemente mit multiplikativem Inversen—dürfen als legale Divisoren auftreten. Wir sagen, q sei ein modularer Quotient von a geteilt durch b modulo n, wenn b mal q denselben Rest lässt wie a, wenn beide Produkte modulo n reduziert werden.

Äquivalent ist q kongruent zu a mal dem Inversen von b modulo n. Das Inverse von b existiert genau dann, wenn der gcd von b und n gleich eins ist; sonst teilt jedes Vielfache von b einen Faktor mit n und kann nicht jede Restklasse treffen, sodass kein einziges q für beliebiges a funktioniert.

Ingenieure und Studierende stoßen auf diese Hürde, wenn sie in einem zusammengesetzten Modul teilen, der kein Primkörper ist, wenn sie einen Koeffizienten in einer linearen Kongruenz kürzen oder wenn sie eine modulare Multiplikation in einem Hash- oder Chiffrierschritt rückgängig machen. Beachten Sie, dass a selbst nicht teilerfremd zu n sein muss; nur der Divisor b muss eine Einheit sein. Diese Asymmetrie vergisst man leicht, wenn man nur den Spezialfall des modularen Inversen mit a gleich eins im Kopf hat.

Praktische Nutzung, Grenzen, Preise und Bereitstellung

Nutzen Sie das Browser-Werkzeug, wenn Sie einen schnellen modularen Quotienten wünschen, während Sie eine zahlentheoretische Notiz lesen, eine Hausaufgabe der Form b x kongruent a mod n prüfen oder eine modulare Pipeline debuggen, die bereits von Hand mit Inversen multipliziert. Akzeptierte Eingaben sind ganze Zahlen a und b mit Absolutbetrag höchstens eine Billion und Module n von zwei bis eine Billion. Ergebnisse sind deterministisch: dasselbe Tripel liefert immer dieselben Felder quotient, inverse und check.

Verdrahten Sie den Endpunkt in Wettbewerbshelfer, Demos endlicher Körper, RSA-Lehrsandkästen, die mehr als bloße Inverse brauchen, oder jede ganzzahlige Pipeline, die exakte Arithmetik heuristischen Gleitkommaverfahren vorzieht. Wenn Sie nur das Inverse von b ohne Multiplikation mit a brauchen, bevorzugen Sie die dedizierte Fähigkeit für modulare Inverse; diese Seite zielt auf die volle Divisionsabsicht, die Suchende als modulare Division oder a geteilt durch b mod n formulieren.