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.

Vier Stunden nach neun Uhr sind 1 Uhr

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

Geschichte

Bearbeiten

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]

Kongruenzrelation

Bearbeiten

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

  • Die Zahl   teilt die Differenz  .
  •   und   hinterlassen bei Division durch   denselben Rest.[2]

Letzteres kann man unter der Modulo-Notation auch als   schreiben.

Man schreibt dazu  . 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   als Abstand haben. Für die Restklasse von   modulo   schreibt man für gewöhnlich   oder  . Bezüglich modulo   sind die Reste gegeben durch  ,  ,  ,   und  . Wählt man diese als Repräsentanten aus, so ergibt sich der nebenstehende Zahlenstrahl.

Restklassenringe

Bearbeiten

Die Menge aller Restklassen modulo   bezeichnet man als Restklassenring modulo  . Man schreibt  ,  ,   oder   (sprich „Z modulo m“).

Addition und Multiplikation definiert man mit

 ,
 .

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

 .

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

Anwendungen

Bearbeiten

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  .
  • 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

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

Anmerkungen

Bearbeiten
  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.