Ergebnis
Ohne mod
Volle Umdrehungen
ggT(a, n)

    Mehr über modulare Arithmetik

    Modulo-Uhr

    Fünf Stunden nach 9 Uhr ist es 2 Uhr, denn 9 + 5 = 14, und 14 ist 2 mehr als 12. Das ist modulare Arithmetik: Zählen auf einer Uhr, die nach n wieder bei 0 beginnt. Wählen Sie eine Rechenart, geben Sie n, a und b ein, und der Rechner liefert das Ergebnis mit jedem Schritt ausgeschrieben, vom Rest einer Division bis zum wiederholten Quadrieren und zum erweiterten euklidischen Algorithmus, während die Uhr zeigt, wie das Ergebnis zustande kommt. Wählen Sie eine Rechenart und geben Sie dann den Modul n und die Zahlen a und b ein; ganze Zahlen mit bis zu 30 Stellen sind möglich, auch negative, und n darf bis zu 10^18 betragen. Die Uhr hat n Positionen mit der 0 oben, und ihr Zeiger zeigt auf das Ergebnis. Addition und Subtraktion werden als Spirale aus b Schritten gezeichnet, mit einem Ring für jede volle Umdrehung; die Multiplikation als Sprünge um a; Potenzen als die Sehnen a, a², a³ …, die sich zu einem Zyklus schließen; das Inverse und die Division als die Vielfachen, die auf 1 bzw. auf a landen. Die Schritte zeigen dieselbe Rechnung in Zahlen. Bis mod 20 wird die Tabelle der Rechenart angezeigt; klicken Sie auf eine Zelle, um ihre Zahlen zu übernehmen. Beispiel setzt eine klassische Aufgabe ein.

    Wie es funktioniert

    1. Wählen Sie eine Rechenart: a mod n, Addition, Subtraktion, Multiplikation, Division, eine Potenz oder das Inverse von a.
    2. Geben Sie den Modul n und die Zahlen a und b ein, oder wählen Sie ein Beispiel wie die letzte Ziffer von 7^2026 oder eine kleine RSA-Nachricht.
    3. Lesen Sie das Ergebnis und die Schritte ab, verfolgen Sie den Weg auf der Uhr, und klicken Sie bis mod 20 auf eine Zelle der Tabelle, um ihre Zahlen auszuprobieren.

    Was a mod n bedeutet

    a mod n ist der Rest, wenn a durch n geteilt wird: 17 mod 5 = 2, denn 17 = 3 × 5 + 2. Der Rest liegt immer zwischen 0 und n − 1, auch bei negativen Zahlen: −7 mod 3 = 2, denn −7 = −3 × 3 + 2. Auf der Uhr heißt das, von 0 aus 7 Schritte rückwärts zu gehen. Zwei Zahlen mit demselben Rest sind kongruent, geschrieben 17 ≡ 2 (mod 5), eine Schreibweise, die Carl Friedrich Gauß 1801 einführte. Summen, Differenzen und Produkte dürfen bei jedem Schritt mod n reduziert werden, was die Zahlen klein hält.

    Wo modulare Arithmetik verwendet wird

    Uhren und Kalender rechnen mod 12, mod 24 und mod 7: 100 Tage nach einem Mittwoch ist Freitag, denn 100 mod 7 = 2. Prüfziffern nutzen sie, um Tippfehler zu erkennen, von ISBN-10-Nummern (mod 11) über Bankkartennummern (mod 10) bis zu IBANs (mod 97). Chiffren verschieben Buchstaben mod 26, und die affine Chiffre braucht zum Entschlüsseln ein Inverses mod 26. RSA, das einen großen Teil des Internets schützt, verschlüsselt eine Nachricht m als m^e mod n und entschlüsselt mit einer weiteren Potenz: Mit n = 3233 ist 65^17 mod 3233 = 2790 und 2790^413 mod 3233 = 65.

    Häufig gestellte Fragen

    Wie berechnet man a mod n für eine negative Zahl?

    Addieren oder subtrahieren Sie Vielfache von n, bis die Zahl zwischen 0 und n − 1 liegt. Für −7 mod 3: −7 + 9 = 2, das Ergebnis ist also 2. Manche Programmiersprachen liefern für −7 % 3 stattdessen −1, weil sie den Quotienten in Richtung null runden; in der Mathematik ist der Rest nie negativ.

    Was ist ein modulares Inverses?

    Das Inverse von a mod n ist die Zahl x mit a × x ≡ 1 (mod n). Das Inverse von 7 mod 26 ist 15, denn 7 × 15 = 105 = 4 × 26 + 1. Es existiert nur, wenn a und n keinen gemeinsamen Teiler haben, und der erweiterte euklidische Algorithmus findet es. Durch a mod n zu dividieren heißt, mit seinem Inversen zu multiplizieren.

    Wie lässt sich eine Potenz wie 7^2026 mod n berechnen?

    Durch wiederholtes Quadrieren: Quadrieren Sie 7 immer wieder und reduzieren Sie jedes Mal mod n, um 7^1, 7^2, 7^4, 7^8 und so weiter zu erhalten, und multiplizieren Sie dann diejenigen, die zusammen 2026 im Binärsystem ergeben. Das braucht 10 Quadrierungen und 7 Multiplikationen statt 2.025 Multiplikationen, und die Zahlen werden nie größer als n². 7^2026 endet auf 9.

    Warum zeigt die Uhr 0 statt 12?

    In der modularen Arithmetik laufen die Reste von 0 bis n − 1, deshalb ist auf einer Uhr mit 12 Positionen 12 Uhr mittags die 0. 12 ≡ 0 (mod 12); eine gewöhnliche Uhr schreibt einfach 12, wo die Mathematik 0 schreibt.

    Wie groß dürfen die Zahlen sein?

    a und b dürfen bis zu 30 Stellen haben und negativ sein, und der Modul darf bis zu 10^18 betragen. Der Rechner arbeitet in Ihrem Browser mit exakten ganzen Zahlen, sodass selbst Beispiele in RSA-Größe exakte Ergebnisse liefern, und nichts wird irgendwohin gesendet.

    Bereit, es auszuprobieren?

    Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

    Zum Editor