Modulare Arithmetik

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 gesamte Gebiet. Teilaspekte werden in separaten Artikeln genauer behandelt.

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.^[1]

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

• Die Zahl ${\displaystyle m}$ teilt die Differenz ${\displaystyle a-b}$.
• ${\displaystyle a}$ und ${\displaystyle b}$ hinterlassen bei Division durch ${\displaystyle m}$ denselben Rest.^[2]

Letzteres lässt sich mit Hilfe der Modulo-Notation auch als ${\displaystyle a{\bmod {m}}=b{\bmod {m}}}$ schreiben.

Man schreibt dazu ${\displaystyle a\equiv b{\pmod {m}}}$. Die Zahlen ${\displaystyle a}$ und ${\displaystyle b}$ sind modulo ${\displaystyle m}$ inkongruent zueinander, wenn die genannten Eigenschaften nicht erfüllt sind.

Für jede natürliche Zahl ${\displaystyle m}$ ist die Kongruenzrelation modulo ${\displaystyle m}$ eine Äquivalenzrelation auf der Menge der ganzen Zahlen und die Äquivalenzklassen bezüglich dieser werden Restklassen modulo ${\displaystyle m}$ genannt. Innerhalb jeder der insgesamt ${\displaystyle m}$ Äquivalenzklassen, die den möglichen Resten bei der Division mit ${\displaystyle m}$ entsprechen, beträgt der Abstand je zweier Zahlen gemäß der obigen Definition ein ganzzahliges Vielfaches von ${\displaystyle m}$. Für die Restklasse von ${\displaystyle a}$ modulo ${\displaystyle m}$ schreibt man für gewöhnlich ${\displaystyle a+m\mathbb {Z} ,}$ oder ${\displaystyle [a]_{m}}$. Wird beispielsweise modulo ${\displaystyle 5}$ gerechnet, so sind die Reste gegeben durch ${\displaystyle 0}$, ${\displaystyle 1}$, ${\displaystyle 2}$, ${\displaystyle 3}$ und ${\displaystyle 4}$. Wählt man diese als Repräsentanten aus, so ergibt sich die nebenstehende Zahlengerade.

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

Addition und Multiplikation werden hierbei definiert durch

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

${\displaystyle [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 der Restklassenring

${\displaystyle \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.

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 ${\displaystyle \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.

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

1. ↑ Siehe dazu: Marten Bullynck: Modular arithmetic before C.F. Gauss: Systematizations and discussions on remainder problems in 18th-century Germany. Historia Mathematica, Band 36, Nr. 1, 2009, S. 48–72.
2. ↑ Das funktioniert natürlich nur, wenn man Division mit Rest bzw. die Modulo-Operation auch für negative Zahlen zulässt.