Kongruenzen und Modulare Arithmetik

Die modulare Arithmetik untersucht ganze Zahlen bis zur Teilbarkeit durch einen festen Modul, wodurch die ganzen Zahlen zu dem endlichen Ring Z/nZ werden und die Zahlentheorie ihr flexibelstes Rechenwerkzeug erhält.

Definition

Zwei ganze Zahlen sind kongruent modulo n, wenn ihre Differenz durch n teilbar ist. Modulare Arithmetik ist die Arithmetik der resultierenden Restklassen, die den kommutativen Ring Z/nZ bilden.

Scope

Dieses Thema behandelt die Kongruenzrelation und Restklassen, Arithmetik in Z/nZ, lineare und polynomielle Kongruenzen, den chinesischen Restsatz, den kleinen Satz von Fermat und den Satz von Euler, die Struktur der Einheitengruppe, Primitivwurzeln und die Ordnung von Elementen. Es ist die Sprache, in der der größte Teil der elementaren und rechnerischen Zahlentheorie ausgedrückt wird.

Core questions

• Wann hat eine lineare Kongruenz ax kongruent zu b mod n Lösungen, und wie viele?
• Wie zerlegt der chinesische Restsatz Z/nZ in ein Produkt über Primzahlpotenzmoduli?
• Warum gelten der kleine Satz von Fermat und der Satz von Euler, und was sagen sie über die Ordnung von Einheiten aus?
• Für welche Moduli existiert eine Primitivwurzel, die die Einheitengruppe zyklisch macht?

Key theories

Chinesischer Restsatz

Sind die Moduli paarweise teilerfremd, so hat ein System simultaner Kongruenzen eine eindeutige Lösung modulo des Produkts; äquivalent dazu ist Z/nZ isomorph zum Produkt von Z über seine Primzahlpotenzfaktoren.

Kleiner Satz von Fermat und Satz von Euler

Für a teilerfremd zu n ist a hoch dem Totienten von n kongruent zu eins modulo n; der Primzahlfall (Fermat) liegt Primzahltests zugrunde und der allgemeine Fall (Euler) RSA.

Primitivwurzeln und Gruppenstruktur

Die multiplikative Gruppe der Einheiten modulo n ist genau dann zyklisch, wenn n eins, zwei, vier, eine ungerade Primzahlpotenz oder das Doppelte einer solchen ist; ein Generator ist eine Primitivwurzel, die einen diskreten Logarithmus liefert.

Clinical relevance

Modulare Arithmetik ist die Rechengrundlage der Kryptographie (RSA, Diffie-Hellman, elliptische Kurvenverfahren), von Prüfsummen und Fehlererkennung (ISBN, Hash-Funktionen) sowie der Erzeugung von Pseudozufallszahlen, was sie zum am weitesten verbreiteten Teil der Zahlentheorie macht.

History

Obwohl Spezialfälle in der alten chinesischen und indischen Mathematik (das nach ersterer benannte Restproblem) auftauchen, wurde die systematische Theorie der Kongruenzen von Gauss in den Disquisitiones Arithmeticae (1801) eingeführt, wo er die Notation etablierte und die zentralen strukturellen Ergebnisse bewies.

Key figures

• Carl Friedrich Gauss
• Pierre de Fermat
• Leonhard Euler

Seminal works

• irelandRosen1990

Frequently asked questions

Was bedeutet die Notation a kongruent zu b mod n?

Es bedeutet, dass n die Differenz a minus b teilt, äquivalent dazu lassen a und b bei Division durch n denselben Rest.

Warum basiert RSA auf dem Satz von Euler?

RSA-Verschlüsselung und -Entschlüsselung sind modulare Exponentiationen, deren Komposition die ursprüngliche Nachricht genau deshalb zurückgibt, weil der Satz von Euler garantiert, dass der relevante Exponent als Identität modulo des Schlüssels wirkt.