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 ganze Zahlen
und
kongruent modulo
(= eine weitere ganze Zahl), wenn sie sich um ein ganzzahliges Vielfaches von
unterscheiden; andernfalls inkongruent modulo
. Ist
dann sind zwei ganze Zahlen genau dann kongruent, wenn sie bei der Division durch
denselben Rest haben.
Jede Kongruenz modulo einer ganzen Zahl ist eine Kongruenzrelation auf dem Ring der ganzen Zahlen, wobei der Modul
sogar Gleichheit erzwingt.
Beispiele
11 ist kongruent 5 modulo 3, da
und
ist und somit die beiden Reste gleich sind. Alternativ erkennt man es daran, dass die Differenz
ein ganzzahliges Vielfaches des Moduls 3 ist (
).
Hingegen ist 11 inkongruent 5 modulo 4, da
und
; die beiden Reste sind nicht gleich, und die Differenz 11 - 5 = 6 ist auch nicht durch 4 teilbar (genauso wenig wie die Differenz der errechneten Reste 3 - 1 = 2).
−8 und 10 sind kongruent modulo 6, denn
und
. Auch ist die Differenz von -8 und 10, nämlich -18, durch 6 teilbar.
Bei der Prüfung, ob die Reste gleich sind, muss man die in der Mathematik übliche Konvention anwenden, nach der das Vorzeichen des Rests (wenn er nicht 0 ist) das Vorzeichen des Divisors ist. Man darf also nicht
rechnen, wie es bei Ganzzahlberechnungen im Computer in der Regel geschieht.
Schreibweise
Für die Aussage „
und
sind kongruent modulo
“ verwendet man folgende Schreibweisen:
![{\displaystyle a\equiv b\mod m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87b390cd70524a8f7c2ad75e856de8a1850e13e6)
![{\displaystyle a\equiv b\mod m\mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac8e563be51cd87455433203b0dfc00758818d4e)
![{\displaystyle a\equiv b{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad3dfcf6e055fce344fa935fbed43aacd9bcc613)
![{\displaystyle a\equiv b\quad (m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27af66acde63667b2f8bb9914890c5a8520450a9)
![{\displaystyle a\equiv _{m}b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71643235c85f27cc0c2ff43275c778b124374bfb)
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
).
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
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]
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:
![{\displaystyle a\equiv b{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad3dfcf6e055fce344fa935fbed43aacd9bcc613)
![{\displaystyle \Leftrightarrow m\mid (a-b)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84ae0cdc337de3b7db750368bb79a451e4b6b27e)
![{\displaystyle \Leftrightarrow \exists k\in \mathbb {Z} :a=km+b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5f34620dbd6ae8a1641464ef5a77b8b91571780)
![{\displaystyle a\not \equiv b{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6c9ed21ddd5b52e1ec39a0e13c45189a922f0a8)
![{\displaystyle \Leftrightarrow m\nmid (a-b)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46a2a700acf29fe466dccd52dacfc5e32da8f24a)
![{\displaystyle \Leftrightarrow \forall k\in \mathbb {Z} :a\neq km+b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e3adfea700524c728f0c83e1e6193c547a79790)
Restklassen
Eine Kongruenzrelation ist eine spezielle Äquivalenzrelation. Sie hat also die folgenden Eigenschaften:
- Reflexivität
für alle ![{\displaystyle a\in \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/175ebd03e0644b0967a63d648c2843a5e883257b)
- Symmetrie
für alle ![{\displaystyle a,b\in \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6271473ca60d1b6878a1430d12324319bebe7ee)
- Transitivität
und
für alle ![{\displaystyle a,b,c\in \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f75bbcddb8e6be5b4825aeda775edf3ebe76fa94)
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.
Rechenregeln
Im Folgenden seien
,
,
,
,
und
ganze Zahlen. Dabei sei
,
und
. Dann gelten folgende Rechenregeln:
![{\displaystyle ca\equiv ca'{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5d3718001b3da012a7fed6d923dd815382f660e)
![{\displaystyle a+b\equiv a'+b'{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75cfc9813f8d1898e2ab3089b833b9a491d9bd0d)
![{\displaystyle a-b\equiv a'-b'{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0868b8a728963fec4f65f70fc93fbdbbb4f1542)
![{\displaystyle ab\equiv a'b'{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb3f8ab56864afb27272affcb39ad8e46e1adf02)
Ist
ein Polynom über den ganzen Zahlen, dann gilt:
![{\displaystyle f(a)\equiv f(a'){\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9d50845836d899067c1577a7fc7ff7137ed2628)
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):
![{\displaystyle ca\equiv cb{\pmod {m}}\Leftrightarrow a\equiv b{\pmod {\frac {m}{\operatorname {ggT} (c,m)}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3f767fbffc866810b07a3b0d074dd504e57505d)
Daraus folgt unmittelbar, dass – wenn
eine Primzahl
und diese kein Teiler von
ist – gilt:
![{\displaystyle ca\equiv cb{\pmod {p}}\Leftrightarrow a\equiv b{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/262cfda474716e5dec4e8ea24c3138c795a2b7cf)
Falls
eine zusammengesetzte Zahl oder ein Teiler von
ist, gilt nur:
![{\displaystyle ca\equiv cb{\pmod {m}}\Leftarrow a\equiv b{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be7fe6377103c8f33c7ab34047a916195d054f03)
Für jeden Teiler
von
folgt aus
, dass
.
Sind
ganze Zahlen ungleich null und ist
ihr kleinstes gemeinsames Vielfaches, dann gilt:
für alle ![{\displaystyle \kappa =1,2,\dotsc ,k\quad \Leftrightarrow \quad a\equiv a'{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/60eba189b416a381c34b119a62091cd0725e9c0c)
Potenzen
Ist
eine natürliche Zahl, dann gilt:
![{\displaystyle a^{n}\equiv (a')^{n}{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/69bf270cb583f8c093a30699bc8f402ad62b107c)
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
![{\displaystyle a^{p}\equiv a{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ff656f721894b9a50a2b1d18538463a6a4ec15f)
erfüllt ist.
Abgeleitete Rechenregeln
- Für
gilt: ![{\displaystyle t\cdot a\equiv t\cdot b{\pmod {|t|\cdot m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a11a86353cc94497131111010d7a6a668892f940)
- Ist
ein Teiler von
, dann gilt: ![{\displaystyle a\equiv b{\pmod {k}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c65b7d21d029fb34826e6b1d8241c2764449071)
- Für jede ungerade Zahl
gilt: ![{\displaystyle a^{2}\equiv 1{\pmod {8}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/180eedfe08cd3b21a2127f0c3c26468c9af9d939)
- Für jede ganze Zahl gilt entweder
oder
oder
. - Für jede ganze Zahl
gilt: ![{\displaystyle a^{3}\equiv a{\pmod {6}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08371d9cb55589ffa4ebb0171ae70e5d8762be34)
- Für jede ganze Zahl gilt entweder
oder
oder
. - Für jede ganze Zahl gilt entweder
oder
. - Ist
sowohl eine Quadratzahl als auch eine Kubikzahl (z. B.
), dann gilt entweder
oder
oder
oder
. - Sei
eine Primzahl mit
. Dann gilt:
![{\displaystyle {2n \choose n}\equiv 0{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8abe481448d103b2189c7a8c98ad280a624ec2b8)
- Sei
eine ungerade ganze Zahl. Ferner sei
. Dann gilt: ![{\displaystyle a^{2^{n}}\equiv 1{\pmod {2^{n+2}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aaf6149a37c03aa34ad53231afa017473d8f9afe)
- Sei
. Ferner seien
und
Primzahlzwillinge. Dann gilt: ![{\displaystyle p\cdot q\equiv -1{\pmod {9}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c33e8bf73264f7da86d5dfcd020a15e6b1718fa)
Lösbarkeit von linearen Kongruenzen
Lineare Kongruenz
Eine lineare Kongruenz der Form
![{\displaystyle ax\equiv c{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6353ea6d8022ab8b55e73f0760ea12eb04b0d2ce)
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:
![{\displaystyle g=\operatorname {ggT} (a,m)=s\cdot a+t\cdot m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b1020f50ce52d7578534d79ecd2b604e9e77e16d)
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 Kongruenz
Eine simultane Kongruenz wie
![{\displaystyle \qquad a_{1}x\equiv c_{1}{\pmod {m_{1}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76a43c741442acaaa7292f5f5286453a8d14fef0)
![{\displaystyle \qquad a_{2}x\equiv c_{2}{\pmod {m_{2}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e26ead2271300b235d46bcbc6e312ae3ce413ed)
![{\displaystyle \qquad a_{3}x\equiv c_{3}{\pmod {m_{3}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a44695e0fff0ce60b3f4cb9a2ce1ea0209d17fb)
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-Funktion
Allgemein
Mit
,
, 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d0f98cde9196964e13bcae99b53a3eb5d0a6ff03)
Programmierung
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
![{\displaystyle (a{\bmod {m}}):=a-\left\lfloor {\frac {a}{m}}\right\rfloor \cdot m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7943219852b0a7ee2f982fd4269b09e576075ed)
definierte mathematische Modulo-Funktion
verwenden, deren Ergebnis immer dasselbe Vorzeichen wie
hat (
ist die Gaußklammer). Mit dieser Definition gilt beispielsweise
.
Anwendungen
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
Weblinks
Quellen
- ↑ Peter Bundschuh: Einführung in die Zahlentheorie. 5. Auflage. Springer, Berlin 2002, ISBN 3-540-43579-4
- ↑ Song Y. Yan: Number theory for computing. 2. Auflage. Springer, 2002, ISBN 3-540-43072-5, S. 111–117