Kongruenz (Zahlentheorie)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel behandelt die Kongruenz bezüglich der Division mit Rest. Zur Kongruenz bezüglich des Flächeninhalts siehe Kongruente Zahl.

Die Kongruenz ist in der Zahlentheorie eine Beziehung zwischen ganzen Zahlen. Man nennt zwei Zahlen kongruent bezüglich eines Moduls (eine weitere Zahl), wenn sie bei Division durch den Modul denselben Rest haben. Das ist genau dann der Fall, wenn sie sich um ein ganzzahliges Vielfaches des Moduls unterscheiden. Stimmen die Reste nicht überein, so nennt man die Zahlen inkongruent bezüglich des Moduls.

Beispielsweise ist 5 kongruent 11 modulo 3, da und , bzw. . Und −8 ist kongruent zu 10 modulo 6, denn bei Division durch 6 liefern sowohl 10 als auch −8 den Rest 4. Man beachte, dass die mathematische Definition der Ganzzahldivision zugrunde gelegt wird, nach der der Rest dasselbe Vorzeichen wie der Divisor (hier 6) erhält, also .

Für die Aussage „ und sind kongruent modulo “ verwendet man folgende Schreibweisen:

  • .

Die Bedeutung von Kongruenzen beruht darauf, dass mit ihnen annähernd wie mit Gleichungen gerechnet werden kann.

Die Theorie der Kongruenzen wurde von Carl Friedrich Gauß in seinem im Jahr 1801 veröffentlichten Werk „Disquisitiones Arithmeticae“ entwickelt. Der Begriff Kongruenz wurde von Christian Goldbach schon ab 1730 in Briefen an Leonhard Euler verwendet, jedoch ohne die theoretische Tiefe von Gauß. Im Gegensatz zu Gauß verwendete Goldbach das Symbol und nicht .[1] Auch der chinesische Mathematiker Ch'in Chiu-Shao kannte schon Kongruenzen und die damit einhergehende Theorie, wie aus seinem 1247 veröffentlichten Buch „Mathematische Abhandlung in neun Kapiteln“ hervorgeht.[2]

Formale Definition[Bearbeiten | Quelltext bearbeiten]

In der Zahlentheorie wird die Kongruenz auf eine Teilbarkeitsaussage zurückgeführt. Seien dazu , und ganze Zahlen, d.h. Elemente aus .

Zwei Zahlen und heißen kongruent modulo , wenn die Differenz teilt.
Zwei Zahlen und heißen inkongruent modulo , wenn die Differenz nicht teilt.

Unter Verwendung der mathematischen Notation lassen sich diese beiden Aussagen wie folgt schreiben:

Restklassen[Bearbeiten | Quelltext bearbeiten]

Die Kongruenz ist eine Äquivalenzrelation. Sie hat also die folgenden Eigenschaften:

Reflexivität
für alle
Symmetrie
für alle
Transitivität
und für alle

Legt man einen Modul fest, so kann dadurch die Menge aller Zahlen auf sogenannte Restklassen verteilt werden. In einer Restklasse befinden sich alle Zahlen, die unter dem festgelegten Modul kongruent zueinander sind, die also stets den gleichen Rest aufweisen. Der Absolutwert des Modul entspricht immer der Anzahl der Restklassen. Beispielsweise existieren für den Modul 2 die beiden Restklassen der geraden und der ungeraden Zahlen. Die Restklassen eines Moduls bilden einen Ring, den sogenannten Restklassenring.

Rechenregeln[Bearbeiten | Quelltext bearbeiten]

Im Folgenden seien , , , , und ganze Zahlen. Dabei sei , und . Dann gelten folgende Rechenregeln:

Ist ein Polynom über den ganzen Zahlen, dann gilt

Auch bei Kongruenzen ist ein Kürzen möglich. Es gelten jedoch andere Kürzungsregeln als von rationalen oder reellen Zahlen gewohnt

Daraus folgt unmittelbar, dass wenn der Modul eine Primzahl und diese kein Teiler von ist, gilt

Falls der Modul eine zusammengesetzte Zahl oder Teiler von ist, gilt nur

Für jeden Teiler von folgt aus , dass .

Sind ganze Zahlen ungleich null und ist ihr kleinstes gemeinsames Vielfaches, dann gilt

für alle

Potenzen[Bearbeiten | Quelltext bearbeiten]

Ist eine natürliche Zahl, dann gilt

Sind und teilerfremd, dann gilt nach dem Satz von Euler

wobei die Eulersche φ-Funktion bezeichnet. Daraus folgt außerdem

, falls

Ein Spezialfall davon ist der kleine Fermat’sche Satz, demzufolge für alle Primzahlen die Kongruenz

erfüllt ist.

Abgeleitete Rechenregeln[Bearbeiten | Quelltext bearbeiten]

  1. Für gilt:
  2. Ist ein Teiler von , dann gilt:
  3. Für jede ungerade Zahl gilt
  4. Für jede ganze Zahl gilt entweder oder oder
  5. Für jede ganze Zahl gilt
  6. Für jede ganze Zahl gilt entweder oder oder
  7. Für jede ganze Zahl gilt entweder oder
  8. Ist sowohl eine Quadratzahl als auch eine Kubikzahl (z. B. ) dann gilt entweder oder oder oder
  9. Sei eine Primzahl mit . Dann gilt
  10. Sei eine ungerade ganze Zahl. Ferner sei . Dann gilt:
  11. Sei . Ferner seien und Primzahlzwillinge. Dann gilt:

Lösbarkeit von linearen Kongruenzen[Bearbeiten | Quelltext bearbeiten]

Eine lineare Kongruenz der Form

ist genau dann in lösbar, wenn die Zahl teilt. In diesem Fall besitzt die Kongruenz genau Lösungen in , und die Lösungen sind zueinander kongruent modulo .

Auch für große kann man die Lösungen effizient ermitteln, indem man den erweiterten euklidischen Algorithmus auf und anwendet, der neben auch zwei Zahlen und berechnet, die als Linearkombination von und ausdrücken:

.

Eine Lösung erhält man dann mit , und die übrigen Lösungen unterscheiden sich von um ein Vielfaches von .

Beispiel: ist lösbar, denn teilt die Zahl , und es gibt Lösungen im Bereich . Der erweiterte euklidische Algorithmus liefert , was die Lösung ergibt. Die Lösungen sind kongruent modulo . Somit ist die Lösungsmenge

.

Eine simultane Kongruenz wie

ist sicher dann lösbar, wenn gilt:

  • für alle ist durch teilbar, d. h. jede Kongruenz ist für sich lösbar
  • die sind paarweise zueinander teilerfremd

Der Beweis des Chinesischen Restsatzes liefert den Lösungsweg für solche simultanen Kongruenzen.

Beziehung zur Modulo-Funktion[Bearbeiten | Quelltext bearbeiten]

Sind zwei Zahlen kongruent modulo einer Zahl , ergibt sich bei der Division durch derselbe Rest.

Mithilfe der vor allem in der Informatik verbreiteten Modulo-Funktion kann man dies so schreiben:

.

Man beachte, dass dies mit der in der Informatik üblichen Modulo-Funktion nur für positive und richtig ist. Damit die Gleichung tatsächlich für alle und äquivalent zur Kongruenz wird, muss man die durch

definierte Modulo-Funktion verwenden. ( ist die Gaußklammer.) Mit dieser Definition gilt beispielsweise .

Anwendungen[Bearbeiten | Quelltext bearbeiten]

Kongruenzen bzw. Restklassen sind oft hilfreich, wenn man Berechnungen mit sehr großen Zahlen durchführen muss.

Eine wichtige Aussage über Kongruenzen von Primzahlen ist der kleine Satz von Fermat bzw. der fermatsche Primzahltest.

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Quellen[Bearbeiten | Quelltext bearbeiten]

  1. Peter Bundschuh: Einführung in die Zahlentheorie. 5. Auflage. Springer, Berlin 2002, ISBN 3-540-43579-4
  2. Song Y. Yan: Number theory for computing. 2. Auflage. Springer, 2002, ISBN 3-540-43072-5, S. 111–117