Kongruenz (Zahlentheorie)

In der Zahlentheorie heißen zwei ganze Zahlen a und b kongruent modulo m , wobei m eine natürliche Zahl ist (N ist in diesem Artikel ohne die 0), wenn m die Differenz (a-b) teilt. Man schreibt:

$a \equiv b \mod{m}$

oder

$a \equiv b \pmod{m}$

oder (seltener)

$a \equiv_m b$ .

Anders formuliert kann man auch sagen, dass zwei Zahlen kongruent modulo einer Zahl m sind, wenn sie bei der Division durch m den selben Rest ergeben.

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

a mod m = b mod m

Dabei ist $m o d$ die durch

$(a\bmod m)= a - \lfloor a/m \rfloor \cdot m$

definierte Modulo-Funktion. ( $\lfloor . \rfloor$ ist die Gaußklammer.) Man beachte, dass mit dieser Definition beispielsweise $( - 1)mod 7 = 6$ gilt.

Beispiele:

3 ≡ 24 mod 7, denn 7 teilt -21 (=3-24)
-31 ≡ 11 mod 7, denn 7 teilt -42 (=-31-11)
-15 ≡ -64 mod 7, denn 7 teilt 49 (=-15-(-64))

Man bezeichnet die Menge aller zu a (modulo m) kongruenten ganzen Zahlen als die Restklasse (s. dort) von a modulo m:

$\bar{a} := \{ x \in \mathbb{Z} : a \equiv x \mod{m}\}$

Es gibt daher genau m Restklassen ( $\bar{0}, \bar{1}, \dots \overline{m-1}$ ) modulo m.

Beispiel:

Modulo 2 sind die beiden Restklassen die Menge der geraden Zahlen ( $\bar{0}$ ) und die Menge der ungeraden Zahlen ( $\bar{1}$ ).

Die Restklassen modulo m bilden einen Ring, der Restklassenring genannt wird. Ist m eine Primzahl, so bilden sie sogar einen Körper.

Die Theorie der Kongruenzen wurde von Carl Friedrich Gauß im Jahre 1801 in seinem Werk Disquisitiones Arithmeticae begründet.

Inhaltsverzeichnis

1 Veranschaulichung am Ziffernblatt der Uhr

2 Elementare Rechenregeln

3 Abgeleitete Rechenregeln

4 Anwendungen

4.1 Beispiel 1
4.2 Beispiel 2
4.3 Beispiel 3
4.4 Beispiel 4

5 Weblinks

Veranschaulichung am Ziffernblatt der Uhr

Veranschaulichen kann man das Rechnen mit Restklassen anhand des Ziffernblattes einer Analoguhr. Die Stunden sind von 1 bis 12 nummeriert, wobei Stunde 12 als Stunde 0 betrachtet wird.

Beginnt man bei Stunde 0 und addiert jeweils eine Stunde, erhält man der Reihe nach jede der 12 Stunden des Ziffernblattes. Man addiert zwei beliebige Stunden miteinander, indem man bei der ersten angegebenen Stunde beginnt und im Uhrzeigersinn die zweite Stundenangabe abzählt: Um 4 + 5 zu ermitteln, beginnt man bei Stunde 4 und zählt 5 Stunden weiter, man landet bei Stunde 9. Berechnet man nun 9 + 5, zählt also von Stunde 9 aus 5 Stunden weiter, landet man bei Stunde 2, es ist also 9 + 5 = 2 in diesem System. Wie kommt dieses Ergebnis zustande? Addiert man einfach die Stundenwerte, erhält man 14; und "14 Uhr" stimmt auf dem zwölfstündigen Ziffernblatt mit "2 Uhr" überein, also ist hier 14 = 2. Das Ergebnis einer Addition ist also die normale Summe, eventuell abzüglich einer 12. Dies entspricht dem Rest bei Division durch 12. Diese Art der Addition heißt "Addition modulo 12". Man erkennt hier, dass die Addition der 12 eine Zahl nicht verändert, 12 + x = x für jede Stunde x. Das erklärt, warum die 12. Stunde hier als Stunde 0 bezeichnet wird.

Die Multiplikation wird auf die Addition zurückgeführt: Um z.B. 4 · 3 zu bestimmen, bildet man die Summe 3 + 3 + 3 + 3, und landet bei der 12. Stunde. Das Produkt 4 · 4 liefert "16 Uhr", und das ist identisch mit "4 Uhr"; modulo 12 ist also 4 · 4 = 4.

Die 12 Stundenwerte, zusammen mit den Regeln für Addition und Multiplikation, schreibt man als (Z/12Z, +, ·).

Was für 12 geht, funktioniert auch für jede andere natürliche Zahl n. In Z/4Z = {0, 1, 2, 3} ist 1 = 1, 2 = 1 + 1, 3 = 1 + 1 + 1, 0 = 1 + 1 + 1 + 1.

Elementare Rechenregeln

Für das Rechnen mit Kongruenzen lassen sich einige elementare Rechenregeln aufstellen.

Gilt a ≡ b (mod m) und c ≡ d (mod m) und b ≡ x (mod m), so gilt:
$a \equiv a \mod{m}$	Reflexivität
$b \equiv a \mod{m}$	Symmetrie
$a \equiv x \mod{m}$	Transitivität
$na \equiv nb \mod{m}$	Skalarmultiplikation
$a + c \equiv b + d \mod{m}$	Addition
$a - c \equiv b - d \mod{m}$	Subtraktion
$ac \equiv bd \mod{m}$	Multiplikation
$a^n \equiv b^n \mod{m}$	Potenzregel
Weiterhin gilt für das Rechnen mit Restklassen:
$\overline{a+c} = \bar{a} + \bar{c}$	Addition
$\overline{a-c} = \bar{a} - \bar{c}$	Subtraktion
$\overline{ac} = \bar{a} \cdot \bar{c}$	Multiplikation

Abgeleitete Rechenregeln

Für t ≠ 0 gilt: t · a ≡ t · b mod |t| · m
Ist k ein Teiler von m, dann gilt: a ≡ b mod k
Sei c · a ≡ c · b mod n sowie d = ggT(c,n) (größter gemeinsamer Teiler), dann gilt: a ≡ b mod(n/d)
Sind c und n teilerfremd, also d = 1, dann folgt sofort a ≡ b mod n
Sei c · a ≡ c · b mod p mit einer Primzahl p, wobei p kein Teiler von c ist. Dann gilt: a ≡ b mod p
Sei a ≡ b mod n und c > 0. Dann gilt: c·a ≡ c·b mod (c·n)
Sei a ≡ b mod n. Ferner sei d > 0 ein Teiler der ganzen Zahlen a,b. Dann gilt: (a/d) ≡ (b/d) mod(n/d)
Für jede ungerade Zahl a gilt a² ≡ 1 mod 8
Mit anderen Worten: Teilt man a² durch 8, dann bleibt als Rest 1.
Für jede ganze Zahl gilt entweder a³ ≡ 0 mod 9 oder a³ ≡ 1 mod 9 oder a³ ≡ 8 mod 9
Mit anderen Worten: Entweder a³ ist durch 9 teilbar oder es bleibt als Rest 1 oder 8.
Für jede ganze Zahl a gilt a³ ≡ a mod 6
Mit anderen Worten: Teilt man a³ durch 6, dann bleibt als Rest die Zahl a selbst.
Für jede ganze Zahl gilt entweder a³ ≡ 0 mod 7 oder a³ ≡ 1 mod 7 oder a³ ≡ 6 mod 7
Mit anderen Worten: Entweder a³ ist durch 7 teilbar oder es bleibt als Rest 1 oder 6.
Für jede ganze Zahl gilt entweder a⁴ ≡ 0 mod 5 oder a⁴ ≡ 1 mod 5
Mit anderen Worten: Entweder a⁴ ist durch 5 teilbar oder es bleibt als Rest 1
Ist a sowohl eine Quadratzahl als auch eine Kubikzahl (z.B. a = 64) dann gilt entweder a ≡ 0 mod 36 oder a ≡ 1 mod 36 oder a ≡ 9 mod 36 oder a ≡ 28 mod 36
Sei p eine Primzahl mit n < p < 2n. Dann gilt
${2n \choose n} \equiv 0 \mod{p}$
Sei a eine ungerade ganze Zahl. Ferner sei n > 0. Dann gilt: a^2ⁿ ≡ 1 mod 2ⁿ⁺²
Seien a·b ≡ c·d mod n , b ≡ d mod n sowie ggT(b,n) = 1 (d.h. b und n sind teilerfremd). Dann gilt: a ≡ c mod n
Es gelte a ≡ b mod x und a ≡ c mod y sowie n = ggT(x,y). Daraus folgt: b ≡ c mod n
Sei p > 3. Ferner seien p und q = p + 2 Primzahlzwillinge. Dann gilt: p·q ≡ -1 mod 9

Anwendungen

Mit Hilfe von Kongruenzen lassen sich zum Beispiel die Teilbarkeitsregeln leicht beweisen. Eine wichtige Aussage über Kongruenzen von Primzahlen ist der kleine Satz von Fermat bzw. der Fermatsche Primzahltest.

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

Siehe auch: lineare Kongruenz, simultane Kongruenz, chinesischer Restsatz

Beispiel 1

Frage: Mit welcher Ziffer endet die Zahl 333²²²?

Es ist 333 ≡ 3 mod 10. Daraus folgt mit der Potenzregel (a=333, b=3, m=10, n=222): 333²²² ≡ 3²²² mod 10.

Es gilt 3² ≡ (-1) mod 10. Erneute Anwendung der Potenzregel (a=3², b=-1, m=10, n=111) liefert: 3²²² = 3^2*111 ≡ (-1)¹¹¹ = -1 ≡ 9 mod 10.

Antwort: Die Endziffer lautet 9.

Beispiel 2

Frage: Ist 2²⁰-1 durch 41 teilbar?

Man sieht leicht: 2⁵ ≡ -9 mod 41.
Daraus folgt mit der Potenzregel (a=2⁵, b=-9): (2⁵)⁴ ≡ (-9) ⁴mod 41 = 81·81 mod 41.
Andererseits gilt: 81 ≡ -1 mod 41. Die Potenzregel liefert 81² ≡ (-1)² mod 41 = 1 mod 41.
Insgesamt ergibt sich nun: 2²⁰-1 ≡ 81·81 mod 41 -1 ≡ (1 mod 41) mod 41 - 1 = 1 - 1 = 0

Antwort: 2²⁰-1 ist durch 41 teilbar.

Beispiel 3

Behauptung: 2³⁴⁰-1 ist durch 341 teilbar.

Von dieser Eigenschaft ist im Artikel Fermatscher Primzahltest die Rede. Sie besagt, dass die Zahl 341 pseudoprim zur Basis 2 ist.

Beweis: 2¹⁰ = 1024 = 3·341 + 1 ≡ 1 mod 341.
2³⁴⁰ = (2¹⁰)³⁴ ≡ 1¹⁷ mod 341 = 1 mod 341
Daraus folgt: 2³⁴⁰-1 ≡ 1 mod 341 -1 = 0

Beispiel 4

Frage: Welches ist der Rest, wenn man die Summe s(9999) := 1! + 2! + 3! + ... +9999! durch 12 teilt?
Gesucht ist als n mit s(9999) ≡ n mod 12.

Es gilt: 4! = 1·2·3·4 ≡ 0 mod 12.
Daraus folgt mit der Multiplikationsregel für k > 3: k! = 4!·5·6···k ≡ 0·5·6··k mod 12 = 0 mod 12.
Anwendung der Additionsregel liefert s(9999) = 1! + 2! + 3! + 4! + ... + 9999! ≡ 1! + 2! + 3! + 0 mod 12 = 9 mod 12.

Antwort: Wenn man s(9999) durch 12 teilt, dann bleibt als Rest 9 übrig.
Aus der Herleitung folgt allgemeiner: s(k) ≡ 9 mod 12 für alle k > 3.

Siehe auch: Modulo (Rest)

Weblinks

Die Theorie der Kongruenzen (pdf-Datei)