Hauptmenü öffnen

Kongruenz (Zahlentheorie)

Begriff aus der Mathematik

Die Kongruenz ist in der Zahlentheorie eine Beziehung zwischen ganzen Zahlen. Man nennt zwei ganze Zahlen und kongruent modulo (= eine weitere Zahl), wenn sie bei der Division durch beide denselben Rest haben. Das ist genau dann der Fall, wenn sie sich um ein ganzzahliges Vielfaches von unterscheiden. Stimmen die Reste hingegen nicht überein, so nennt man die Zahlen inkongruent modulo . Jede Kongruenz modulo einer ganzen Zahl ist eine Kongruenzrelation auf dem Ring der ganzen Zahlen.

BeispieleBearbeiten

Beispiel 1Bearbeiten

Beispielsweise ist 5 kongruent 11 modulo 3, da   und  , die beiden Reste (2) sind also gleich, bzw. da  , die Differenz ist also ein ganzzahliges Vielfaches (2) von 3.

Beispiel 2Bearbeiten

Hingegen ist 5 inkongruent 11 modulo 4, da   und  ; die beiden Reste sind hier nicht gleich.

Beispiel 3Bearbeiten

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  .

SchreibweiseBearbeiten

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

  •  
  •  
  •  
  •  
  •  

Diese Schreibweisen können dabei als Kurzform der (zu obiger Aussage gleichwertigen) Aussage „Divisionsrest von   durch   ist gleich Divisionsrest von   durch  “, also von

 ,

gesehen werden (wobei in letztgenannter Gleichung   die mathematische Modulo-Funktion ist, die den Rest einer ganzzahligen Division ermittelt, hier also den Rest von   bzw.  ; bei der mathematischen Modulo-Funktion hat das Ergebnis, also der Rest, immer dasselbe Vorzeichen wie  ).

BedeutungBearbeiten

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

GeschichteBearbeiten

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 Qin Jiushao (秦九韶) kannte schon Kongruenzen und die damit einhergehende Theorie, wie aus seinem 1247 veröffentlichten Buch „Shushu Jiuzhang“ (chinesisch 數書九章 / 数书九章, Pinyin Shùshū Jiǔzhāng ‚Mathematische Abhandlung in neun Kapiteln‘) hervorgeht.[2]

Formale DefinitionBearbeiten

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:

  •  
 
 
  •  
 
 

RestklassenBearbeiten

Eine Kongruenzrelation ist eine spezielle Äquivalenzrelation. Sie hat also die folgenden Eigenschaften:

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

Die Äquivalenzklassen der Kongruenzrelation heißen Restklassen. Will man auch   angeben, so spricht man von Restklassen  . Eine Restklasse, die das Element   enthält, wird oft mit   bezeichnet.

Wie jede Äquivalenzrelation definiert eine Kongruenzrelation eine Partition ihrer Trägermenge: Die Restklassen zu zwei Elementen sind entweder gleich oder disjunkt, ersteres genau dann, wenn die Elemente kongruent sind:

 .

Ausgestattet mit den von   induzierten Verknüpfungen bilden die Restklassen einen Ring, den sogenannten Restklassenring. Er wird für   mit   bezeichnet.

Bemerkung
  • Da eine Division durch   bisher nicht vorkommt, kann man für die formale Definition (im vorigen Abschnitt) wie auch für die Äquivalenzrelation (in diesem Abschnitt)   zulassen.
  • Da es im Ring   keine echten Nullteiler gibt, degeneriert die Relation   zum trivialen Fall, zur Gleichheit:
        für alle  .
  • Der unitäre Ring der Charakteristik   ist isomorph zu  . Diese Eigenschaft wird auch für den Fall   gebraucht. Dann ist  . Dieser Ring wird nicht als Restklassenring im engeren Sinn angesehen.
  • Die interessanten Fälle sind die Fälle  , was man als Standard annehmen kann.
  • Der Restklassenring   ist der Nullring, der nur aus einem Element besteht.

Ist   nicht trivial, also  , dann befinden sich in einer Restklasse alle Zahlen, die den gleichen Rest bei der Division durch   aufweisen. Dann entspricht auch der Absolutwert von  , also  , der Anzahl der Restklassen. Beispielsweise existieren für 2 die beiden Restklassen der geraden und der ungeraden Zahlen.

RechenregelnBearbeiten

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 ( größter gemeinsamer Teiler):

 

Daraus folgt unmittelbar, dass – wenn   eine Primzahl   und diese kein Teiler von   ist – gilt:

 

Falls   eine zusammengesetzte Zahl oder ein 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  

PotenzenBearbeiten

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 fermatsche Satz, demzufolge für alle Primzahlen   die Kongruenz

 

erfüllt ist.

Abgeleitete RechenregelnBearbeiten

  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 KongruenzenBearbeiten

Lineare KongruenzBearbeiten

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  . Für   lautet die Lösungsmenge somit  .

Simultane KongruenzBearbeiten

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, und
  • die   sind paarweise zueinander teilerfremd.

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

Beziehung zur Modulo-FunktionBearbeiten

AllgemeinBearbeiten

Mit  ,  , gilt allgemein:

 

ProgrammierungBearbeiten

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

Mithilfe der vor allem in der Informatik verbreiteten „symmetrischen Variante“ der Modulo-Funktion, die in Programmiersprachen oft mit den Modulo-Operatoren mod oder % bezeichnet wird, kann man dies so schreiben:

(a mod m) = (b mod m) bzw. (a % m) = (b % m)

Man beachte, dass dies mit der in der Informatik üblichen symmetrischen 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 mathematische Modulo-Funktion   verwenden, deren Ergebnis immer dasselbe Vorzeichen wie   hat (  ist die Gaußklammer). Mit dieser Definition gilt beispielsweise  .

AnwendungenBearbeiten

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 auchBearbeiten

WeblinksBearbeiten

QuellenBearbeiten

  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