Modulare Arithmetik

Vier Stunden nach neun Uhr sind 1 Uhr

Die modulare Arithmetik ist ein Teilgebiet der Zahlentheorie und Algebra, das man kurz als „Arithmetik mit Resten“ umschreiben könnte. Eine bekannte Anwendung davon ist das Ziffernblatt einer Uhr: Die Uhrzeiten kann man als Reste wahrnehmen, die bei der Division durch 12 entstehen. Wenn nach neun Uhr vier Stunden vergingen, so wäre es eigentlich 13 Uhr. Division durch 12 ergibt den Rest 1 und somit zeigt das Ziffernblatt nicht 13, sondern 1 Uhr an.

Dieser Artikel gibt einen Überblick über das ganze Gebiet. Teilaspekte werden in separaten Artikeln genauer behandelt.

Geschichte

Die modulare Arithmetik in ihrer modernen Notation und dem heute bekannten Formalismus geht auf den Mathematiker Carl Friedrich Gauß zurück, der sie 1801 in seinen Disquisitiones Arithmeticae vorstellte. Aber auch schon lange vorher hat man beim Lösen von Problemen mithilfe von Resten argumentiert. Eine der ältesten Anwendungen, die man heute als Chinesischen Restsatz bezeichnet, stammt vom chinesischen Mathematiker Sun Zi, der vermutlich ungefähr im dritten oder vierten Jahrhundert nach Christus lebte. Ansonsten findet man schon vom 13. Jahrhundert bis ins 18. Jahrhundert zahlreiche Anwendungen und Lösungen von Sonderfällen in den Rechenbüchern, Lehrbüchern und in der Unterhaltungsmathematik.

Kongruenzrelation

→ Hauptartikel: Kongruenz (Zahlentheorie) und Restklasse

Sei $m$ eine natürliche Zahl. Zwei ganze Zahlen $a$ und $b$ heißen kongruent modulo $m$, wenn sie eine der beiden äquivalenten Eigenschaften erfüllen:

• Die Zahl $m$ teilt die Differenz $a-b$.
• $a$ und $b$ hinterlassen bei Division durch $m$ denselben Rest.

Letzteres kann man unter der Modulo-Notation auch als $a{\bmod {m}}=b{\bmod {m}}$ schreiben.

Man schreibt dazu $a\equiv b{\pmod {m}}$. Sie sind inkongruent zueinander, wenn sie die Eigenschaften nicht erfüllen.

Zahlenlinie Modulo 5

Die Kongruenzrelation ist eine Äquivalenzrelation und die Äquivalenzklassen nennt man Restklassen. Unter dem Rückgriff auf die Definition kann man die Restklassen als Menge aller ganzer Zahlen sehen, die untereinander ein Vielfaches von $m$ als Abstand haben. Für die Restklasse von $a$ modulo $m$ schreibt man für gewöhnlich $a+m\mathbb {Z} ,$ oder $[a]_{m}$. Bezüglich modulo $5$ sind die Reste gegeben durch $0$, $1$, $2$, $3$ und $4$. Wählt man diese als Repräsentanten aus, so ergibt sich der nebenstehende Zahlenstrahl.

Restklassenringe

→ Hauptartikel: Restklassenring

Die Menge aller Restklassen modulo $m$ bezeichnet man als Restklassenring modulo $m$. Man schreibt $\mathbb {Z} /m\mathbb {Z}$, $\mathbb {Z} /(m)$, $\mathbb {Z} /m$ oder $\mathbb {Z} _{m}$ (sprich „Z modulo m“).

Addition und Multiplikation definiert man mit

$[a]_{m}+[b]_{m}:=[a+b]_{m}$,

$[a]_{m}\cdot [b]_{m}:=[a\cdot b]_{m}$.

Wie der Name suggeriert, entsteht dadurch ein Ring. Dem Ziffernblattbeispiel in der Einleitung entspräche also

$\mathbb {Z} /12\mathbb {Z} =\left\{[0]_{12},[1]_{12},[2]_{12},[3]_{12},[4]_{12},[5]_{12},[6]_{12},[7]_{12},[8]_{12},[9]_{12},[10]_{12},[11]_{12}\right\}$.

Gängige Konvention ist es, die Notation mit den eckigen Klammern auszulassen, wenn klar ist, um welche Äquivalenzklassen es sich handelt.

Anwendungen

Große Teile der modernen Zahlentheorie bauen auf der modularen Arithmetik auf. Grundsätzlich kann man die modulare Arithmetik auf alles anwenden, was sich zyklisch wiederholt. Außerhalb der Zahlentheorie seien da zu nennen:

• In der Informatik kann man den arithmetischen Überlauf als Restklassenringe sehen. Beispielsweise kann der Datentyp Byte 256 verschiedene Werte annehmen und entspricht daher dem Restklassenring $\mathbb {Z} /256\mathbb {Z}$.
• Neben der Uhrzeit lassen sich auch Datumsangaben darstellen. Bekannteste Anwendung ist die Wochentagsberechnung. Auf Gauß selbst geht ein Spezialfall zurück, die Gaußsche Osterformel.
• Die Caesar-Verschlüsselung verschlüsselt einen Klartext, indem sie die Buchstaben zyklisch nach rechts verschiebt. Dies entspricht einer Addition der Buchstabenpositionsnummer um einen festen Wert modulo der Anzahl der Buchstaben.

Literatur

• Martin Aigner: Zahlentheorie. Eine Einführung mit Übungen, Hinweisen und Lösungen. Vieweg+Teubner, 2012, ISBN 978-3-8348-1805-8.