Kongruenz (Zahlentheorie)

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

Beispiele

Beispiel 1

Beispielsweise ist 5 kongruent 11 modulo 3, da ${\displaystyle 5:3=1{\text{ Rest }}2}$ und ${\displaystyle 11:3=3{\text{ Rest }}2}$, die beiden Reste (2) sind also gleich, bzw. da ${\displaystyle 11-5=6=2\cdot 3}$, die Differenz ist also ein ganzzahliges Vielfaches (2) von 3.

Beispiel 2

Hingegen ist 5 inkongruent 11 modulo 4, da ${\displaystyle 5:4=1{\text{ Rest }}1}$ und ${\displaystyle 11:4=2{\text{ Rest }}3}$; die beiden Reste sind hier nicht gleich.

Beispiel 3

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 ${\displaystyle -8:6=-2{\text{ Rest }}4}$.

Schreibweise

Für die Aussage „${\displaystyle a}$ und ${\displaystyle b}$ sind kongruent modulo ${\displaystyle m}$“ verwendet man folgende Schreibweisen:

• ${\displaystyle a\equiv b\mod m}$
• ${\displaystyle a\equiv b\mod m\mathbb {Z} }$
• ${\displaystyle a\equiv b{\pmod {m}}}$
• ${\displaystyle a\equiv b\quad (m)}$
• ${\displaystyle a\equiv _{m}b}$

Diese Schreibweisen können dabei als Kurzform der (zu obiger Aussage gleichwertigen) Aussage „Divisionsrest von ${\displaystyle a}$ durch ${\displaystyle m}$ ist gleich Divisionsrest von ${\displaystyle b}$ durch ${\displaystyle m}$“, also von

${\displaystyle (a{\bmod {m}})=(b{\bmod {m}})}$,

gesehen werden (wobei in letztgenannter Gleichung ${\displaystyle \operatorname {mod} }$ die mathematische Modulo-Funktion ist, die den Rest einer ganzzahligen Division ermittelt, hier also den Rest von ${\displaystyle {\tfrac {a}{m}}}$ bzw. ${\displaystyle {\tfrac {b}{m}}}$; bei der mathematischen Modulo-Funktion hat das Ergebnis, also der Rest, immer dasselbe Vorzeichen wie ${\displaystyle m}$).

Geschichte

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 ${\displaystyle \mp }$ und nicht ${\displaystyle \equiv }$.[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 Definition

In der Zahlentheorie wird die Kongruenz auf eine Teilbarkeitsaussage zurückgeführt. Seien dazu ${\displaystyle a}$, ${\displaystyle b}$ und ${\displaystyle m\neq 0}$ ganze Zahlen, d. h. Elemente aus ${\displaystyle \mathbb {Z} }$.

• Zwei Zahlen ${\displaystyle a}$ und ${\displaystyle b}$ heißen kongruent modulo ${\displaystyle m}$, wenn ${\displaystyle m}$ die Differenz ${\displaystyle a-b}$ teilt.
• Zwei Zahlen ${\displaystyle a}$ und ${\displaystyle b}$ heißen inkongruent modulo ${\displaystyle m}$, wenn ${\displaystyle m}$ die Differenz ${\displaystyle a-b}$ nicht teilt.

Unter Verwendung d​er mathematischen Notation lassen s​ich diese beiden Aussagen w​ie folgt schreiben:

• ${\displaystyle a\equiv b{\pmod {m}}}$

${\displaystyle \Leftrightarrow m\mid (a-b)}$

${\displaystyle \Leftrightarrow \exists k\in \mathbb {Z} :a=km+b}$

• ${\displaystyle a\not \equiv b{\pmod {m}}}$

${\displaystyle \Leftrightarrow m\nmid (a-b)}$

${\displaystyle \Leftrightarrow \forall k\in \mathbb {Z} :a\neq km+b}$

Restklassen

Eine Kongruenzrelation i​st eine spezielle Äquivalenzrelation. Sie h​at also d​ie folgenden Eigenschaften:

Reflexivität

${\displaystyle a\equiv a{\pmod {m}}}$ für alle ${\displaystyle a\in \mathbb {Z} }$

Symmetrie

${\displaystyle a\equiv b{\pmod {m}}\Rightarrow b\equiv a{\pmod {m}}}$ für alle ${\displaystyle a,b\in \mathbb {Z} }$

Transitivität

${\displaystyle a\equiv b{\pmod {m}}}$ und ${\displaystyle b\equiv c{\pmod {m}}\Rightarrow a\equiv c{\pmod {m}}}$ für alle ${\displaystyle a,b,c\in \mathbb {Z} }$

Die Äquivalenzklassen der Kongruenzrelation heißen Restklassen. Will man auch ${\displaystyle m}$ angeben, so spricht man von Restklassen ${\displaystyle ({\text{mod }}m)}$. Eine Restklasse, die das Element ${\displaystyle a}$ enthält, wird oft mit ${\displaystyle [a]}$ bezeichnet.

Wie j​ede Äquivalenzrelation definiert e​ine Kongruenzrelation e​ine Partition i​hrer Trägermenge: Die Restklassen z​u zwei Elementen s​ind entweder gleich o​der disjunkt, ersteres g​enau dann, w​enn die Elemente kongruent sind:

${\displaystyle [a]=[b]\quad \iff \quad a\equiv b{\pmod {m}}\quad \iff \quad a\in [b]\quad \iff \quad b\in [a]}$.

Ausgestattet mit den von ${\displaystyle \mathbb {Z} (+,\cdot )}$ induzierten Verknüpfungen bilden die Restklassen einen Ring, den sogenannten Restklassenring. Er wird für ${\displaystyle m}$ mit ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ bezeichnet.

Bemerkung

• Da eine Division durch ${\displaystyle m}$ bisher nicht vorkommt, kann man für die formale Definition (im vorigen Abschnitt) wie auch für die Äquivalenzrelation (in diesem Abschnitt) ${\displaystyle m=0}$ zulassen.
• Da es im Ring ${\displaystyle \mathbb {Z} }$ keine echten Nullteiler gibt, degeneriert die Relation ${\displaystyle \equiv ({\text{mod }}0)}$ zum trivialen Fall, zur Gleichheit:

${\displaystyle a\equiv b{\pmod {0}}\quad \Rightarrow \quad a=b}$       für alle ${\displaystyle a,b\in \mathbb {Z} }$.

• Der unitäre Ring der Charakteristik ${\displaystyle m}$ ist isomorph zu ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$. Diese Eigenschaft wird auch für den Fall ${\displaystyle m=0}$ gebraucht. Dann ist ${\displaystyle \mathbb {Z} /m\mathbb {Z} =\mathbb {Z} /0\mathbb {Z} =\mathbb {Z} }$. Dieser Ring wird nicht als Restklassenring im engeren Sinn angesehen.
• Die interessanten Fälle sind die Fälle ${\displaystyle m\neq 0}$, was man als Standard annehmen kann.
• Der Restklassenring ${\displaystyle \mathbb {Z} /1\mathbb {Z} }$ ist der Nullring, der nur aus einem Element besteht.

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

Rechenregeln

Im Folgenden seien ${\displaystyle a}$, ${\displaystyle a'}$, ${\displaystyle b}$, ${\displaystyle b'}$, ${\displaystyle c}$ und ${\displaystyle m}$ ganze Zahlen. Dabei sei ${\displaystyle m\neq 0}$, ${\displaystyle a\equiv a'{\pmod {m}}}$ und ${\displaystyle b\equiv b'{\pmod {m}}}$. Dann gelten folgende Rechenregeln:

${\displaystyle ca\equiv ca'{\pmod {m}}}$

${\displaystyle a+b\equiv a'+b'{\pmod {m}}}$

${\displaystyle a-b\equiv a'-b'{\pmod {m}}}$

${\displaystyle ab\equiv a'b'{\pmod {m}}}$

Ist ${\displaystyle f\in \mathbb {Z} [X]}$ ein Polynom über den ganzen Zahlen, dann gilt:

${\displaystyle f(a)\equiv f(a'){\pmod {m}}}$

Auch bei Kongruenzen ist ein Kürzen möglich. Es gelten jedoch andere Kürzungsregeln als von rationalen oder reellen Zahlen gewohnt (${\displaystyle \operatorname {ggT} }$ … größter gemeinsamer Teiler):

${\displaystyle ca\equiv cb{\pmod {m}}\Leftrightarrow a\equiv b{\pmod {\frac {m}{\operatorname {ggT} (c,m)}}}}$

Daraus folgt unmittelbar, dass – wenn ${\displaystyle m}$ eine Primzahl ${\displaystyle p}$ und diese kein Teiler von ${\displaystyle c}$ ist – gilt:

${\displaystyle ca\equiv cb{\pmod {p}}\Leftrightarrow a\equiv b{\pmod {p}}}$

Falls ${\displaystyle m}$ eine zusammengesetzte Zahl oder ein Teiler von ${\displaystyle c}$ ist, gilt nur:

${\displaystyle ca\equiv cb{\pmod {m}}\Leftarrow a\equiv b{\pmod {m}}}$

Für jeden Teiler ${\displaystyle d}$ von ${\displaystyle m}$ folgt aus ${\displaystyle a\equiv b{\pmod {m}}}$, dass ${\displaystyle a\equiv b{\pmod {d}}}$.

Sind ${\displaystyle m_{1},m_{2},\dotsc ,m_{k}}$ ganze Zahlen ungleich null und ist ${\displaystyle m}$ ihr kleinstes gemeinsames Vielfaches, dann gilt:

${\displaystyle a\equiv a'{\pmod {m_{\kappa }}}}$ für alle ${\displaystyle \kappa =1,2,\dotsc ,k\quad \Leftrightarrow \quad a\equiv a'{\pmod {m}}}$

Potenzen

Ist ${\displaystyle n\in \mathbb {N} _{0}}$ eine natürliche Zahl, dann gilt:

${\displaystyle a^{n}\equiv (a')^{n}{\pmod {m}}}$

Sind ${\displaystyle a}$ und ${\displaystyle m}$ teilerfremd, dann gilt nach dem Satz von Euler

${\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}}}$,

wobei ${\displaystyle \varphi (m)}$ die Eulersche φ-Funktion bezeichnet. Daraus folgt außerdem

${\displaystyle a^{n}\equiv a^{n'}{\pmod {m}}}$, falls ${\displaystyle n\equiv n'{\pmod {\varphi (m)}}}$.

Ein Spezialfall davon ist der kleine fermatsche Satz, demzufolge für alle Primzahlen ${\displaystyle p}$ die Kongruenz

${\displaystyle a^{p}\equiv a{\pmod {p}}}$

erfüllt ist.

Abgeleitete Rechenregeln

1. Für ${\displaystyle t\neq 0}$ gilt: ${\displaystyle t\cdot a\equiv t\cdot b{\pmod {|t|\cdot m}}}$
2. Ist ${\displaystyle k}$ ein Teiler von ${\displaystyle m}$, dann gilt: ${\displaystyle a\equiv b{\pmod {k}}}$
3. Für jede ungerade Zahl ${\displaystyle a}$ gilt: ${\displaystyle a^{2}\equiv 1{\pmod {8}}}$
4. Für jede ganze Zahl gilt entweder ${\displaystyle a^{3}\equiv 0{\pmod {9}}}$ oder ${\displaystyle a^{3}\equiv 1{\pmod {9}}}$ oder ${\displaystyle a^{3}\equiv 8{\pmod {9}}}$.
5. Für jede ganze Zahl ${\displaystyle a}$ gilt: ${\displaystyle a^{3}\equiv a{\pmod {6}}}$
6. Für jede ganze Zahl gilt entweder ${\displaystyle a^{3}\equiv 0{\pmod {7}}}$ oder ${\displaystyle a^{3}\equiv 1{\pmod {7}}}$ oder ${\displaystyle a^{3}\equiv 6{\pmod {7}}}$.
7. Für jede ganze Zahl gilt entweder ${\displaystyle a^{4}\equiv 0{\pmod {5}}}$ oder ${\displaystyle a^{4}\equiv 1{\pmod {5}}}$.
8. Ist ${\displaystyle a}$ sowohl eine Quadratzahl als auch eine Kubikzahl (z. B. ${\displaystyle a=64}$), dann gilt entweder ${\displaystyle a\equiv 0{\pmod {36}}}$ oder ${\displaystyle a\equiv 1{\pmod {36}}}$ oder ${\displaystyle a\equiv 9{\pmod {36}}}$ oder ${\displaystyle a\equiv 28{\pmod {36}}}$.
9. Sei ${\displaystyle p}$ eine Primzahl mit ${\displaystyle n<p<2n}$. Dann gilt:
   ${\displaystyle {2n \choose n}\equiv 0{\pmod {p}}}$
10. Sei ${\displaystyle a}$ eine ungerade ganze Zahl. Ferner sei ${\displaystyle n>0}$. Dann gilt: ${\displaystyle a^{2^{n}}\equiv 1{\pmod {2^{n+2}}}}$
11. Sei ${\displaystyle p>3}$. Ferner seien ${\displaystyle p}$ und ${\displaystyle q=p+2}$ Primzahlzwillinge. Dann gilt: ${\displaystyle p\cdot q\equiv -1{\pmod {9}}}$

Lösbarkeit von linearen Kongruenzen

Lineare Kongruenz

Eine lineare Kongruenz d​er Form

${\displaystyle ax\equiv c{\pmod {m}}}$

ist genau dann in ${\displaystyle x}$ lösbar, wenn ${\displaystyle g=\operatorname {ggT} (a,m)}$ die Zahl ${\displaystyle c}$ teilt. In diesem Fall besitzt die Kongruenz genau ${\displaystyle g}$ Lösungen in ${\displaystyle \{0,1,\dotsc ,m-1\}}$, und die Lösungen sind zueinander kongruent modulo ${\displaystyle {\tfrac {m}{g}}}$.

Auch für große ${\displaystyle m}$ kann man die Lösungen effizient ermitteln, indem man den erweiterten euklidischen Algorithmus auf ${\displaystyle a}$ und ${\displaystyle m}$ anwendet, der neben ${\displaystyle g}$ auch zwei Zahlen ${\displaystyle s}$ und ${\displaystyle t}$ berechnet, die ${\displaystyle g}$ als Linearkombination von ${\displaystyle a}$ und ${\displaystyle m}$ ausdrücken:

${\displaystyle g=\operatorname {ggT} (a,m)=s\cdot a+t\cdot m}$

Eine Lösung erhält man dann mit ${\displaystyle \textstyle x_{1}={\frac {s\cdot c}{g}}}$, und die übrigen Lösungen unterscheiden sich von ${\displaystyle x_{1}}$ um ein Vielfaches von ${\displaystyle {\tfrac {m}{g}}}$.

Beispiel: ${\displaystyle 4x\equiv 10{\pmod {18}}}$ ist lösbar, denn ${\displaystyle \operatorname {ggT} (4,18)=2}$ teilt die Zahl ${\displaystyle 10}$, und es gibt ${\displaystyle 2}$ Lösungen im Bereich ${\displaystyle 0\leq x<18}$. Der erweiterte euklidische Algorithmus liefert ${\displaystyle 2=-4\cdot 4+1\cdot 18}$, was die Lösung ${\displaystyle \textstyle x_{1}={\frac {-4\cdot 10}{2}}=-20}$ ergibt. Die Lösungen sind kongruent modulo ${\displaystyle \textstyle {\frac {18}{2}}=9}$. Für ${\displaystyle x}$ lautet die Lösungsmenge somit ${\displaystyle \{\cdots ,-20,-11,-2,7,16,25,\cdots \}}$.

Simultane Kongruenz

Eine simultane Kongruenz wie

${\displaystyle \qquad a_{1}x\equiv c_{1}{\pmod {m_{1}}}}$

${\displaystyle \qquad a_{2}x\equiv c_{2}{\pmod {m_{2}}}}$

${\displaystyle \qquad a_{3}x\equiv c_{3}{\pmod {m_{3}}}}$

ist sicher d​ann lösbar, w​enn gilt:

• für alle ${\displaystyle i}$ ist ${\displaystyle c_{i}}$ durch ${\displaystyle g_{i}=\operatorname {ggT} (a_{i},m_{i})}$ teilbar, d. h. jede Kongruenz ist für sich lösbar, und
• die ${\displaystyle {\tfrac {m_{i}}{g_{i}}}}$ sind paarweise zueinander teilerfremd.

Der Beweis d​es Chinesischen Restsatzes liefert d​en Lösungsweg für solche simultanen Kongruenzen.

Beziehung zur Modulo-Funktion

Allgemein

Mit ${\displaystyle a,b,m\in \mathbb {Z} }$, ${\displaystyle m\neq 0}$, gilt allgemein:

${\displaystyle a\equiv b{\pmod {m}}\quad \Leftrightarrow \quad (a{\bmod {m}})=(b{\bmod {m}})\quad \Leftrightarrow \quad (a-b){\bmod {m}}=0}$

Programmierung

Sind zwei Zahlen ${\displaystyle a}$ und ${\displaystyle b}$ kongruent modulo einer Zahl ${\displaystyle m}$, ergibt sich bei der Division durch ${\displaystyle m}$ derselbe Rest.

Mithilfe d​er vor a​llem in d​er Informatik verbreiteten „symmetrischen Variante“ d​er Modulo-Funktion, d​ie in Programmiersprachen o​ft mit d​en Modulo-Operatoren mod o​der % bezeichnet wird, k​ann man d​ies 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 ${\displaystyle a}$ und ${\displaystyle b}$ richtig ist. Damit die Gleichung tatsächlich für alle ${\displaystyle a}$ und ${\displaystyle b}$ äquivalent zur Kongruenz wird, muss man die durch

${\displaystyle (a{\bmod {m}}):=a-\left\lfloor {\frac {a}{m}}\right\rfloor \cdot m}$

definierte mathematische Modulo-Funktion ${\displaystyle \operatorname {mod} }$ verwenden, deren Ergebnis immer dasselbe Vorzeichen wie ${\displaystyle m}$ hat (${\displaystyle \lfloor \cdot \rfloor }$ ist die Gaußklammer). Mit dieser Definition gilt beispielsweise ${\displaystyle (-1){\bmod {7}}=6}$.

Anwendungen

Kongruenzen bzw. Restklassen s​ind oft hilfreich, w​enn man Berechnungen m​it sehr großen Zahlen durchführen muss.

Eine wichtige Aussage über Kongruenzen v​on Primzahlen i​st der kleine Satz v​on Fermat bzw. d​er fermatsche Primzahltest.

Siehe auch

• Chinesischer Restsatz
• Lineare Kongruenz
• Polynomkongruenz
• Simultane Kongruenz
• Modul (Mathematik)

Weblinks

• Christian Spannagel: Kongruenzen und Restklassen. Vorlesungsreihe, 2012.

Quellen

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