Kongruenz (Zahlentheorie)

In der Zahlentheorie heißen zwei ganze Zahlen $a$ und $b$ kongruent modulo $m$ mit einer natürlichen Zahl $m$, wenn die Differenz $(a-b)$ ein ganzes Vielfaches von $m$ ist. Verschiedene Zahlen, die kongruent modulo $m$ sind, können daher durch "Verschiebung" um ein Vielfaches der Zahl $m$ zur Deckung gebracht werden.

Notationen in der Zahlentheorie

Häufig werden für die Aussage „$a$ und $b$ sind kongruent modulo $m$“ die folgenden Schreibweisen benutzt:

$a\equiv b\mod m$

oder

$a\equiv b{\pmod {m}}.\,$

Kongruenz und Reste

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

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

$a{\bmod {m}}=b{\bmod {m}}$.

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

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

definierte Modulo-Funktion verwenden. ($\lfloor .\rfloor$ ist die Gaußklammer.) Mit dieser Definition gilt beispielsweise $(-1){\bmod {7}}=6$.

Beispiele

• $3\equiv 24\mod 7$, denn 7 teilt -21 ($=3-24$)
• $-31\equiv 11\mod 7$, denn 7 teilt -42 ($=-31-11$)
• $-15\equiv -64\mod 7$, denn 7 teilt 49 ($=-15-(-64)$)

Restklassen

Man bezeichnet die Menge aller Zahlen, die modulo einer Zahl $m$ zu einer festen Zahl $a$ kongruent sind, als die Restklasse von $a$ modulo $m$:

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

Es gibt 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, den sog. Restklassenring. Ist $m$ eine Primzahl, so bilden sie einen Körper.

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

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\cdot 3$ zu bestimmen, bildet man die Summe $3+3+3+3$, und landet bei der 12. Stunde. Das Produkt $4\cdot 4$ liefert "16 Uhr", und das ist identisch mit "4 Uhr"; modulo 12 ist also $4\cdot 4=4$.

Die 12 Stundenwerte, zusammen mit den Regeln für Addition und Multiplikation, schreibt man als $(\mathbb {Z} /12\mathbb {Z} ,+,\cdot )$.

Was für 12 geht, funktioniert auch für jede andere natürliche Zahl $n$. In $\mathbb {Z} /4\mathbb {Z} =\{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\equiv b{\pmod {m}}$ und $c\equiv d{\pmod {m}}$ und $b\equiv x{\pmod {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

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

Es ist $333\equiv 3\mod 10$. Daraus folgt mit der Potenzregel ($a=333,b=3,m=10,n=222$): $333^{222}\equiv 3^{222}\mod 10$.

Es gilt $3^{2}\equiv (-1)\mod 10$. Erneute Anwendung der Potenzregel ($a=3^{2},b=-1,m=10,n=111$) liefert: $3^{222}=3^{2\cdot 111}\equiv (-1)^{111}\equiv -1\equiv 9\mod 10$.

Antwort: Die Endziffer lautet 9.

Beispiel 2

Frage: Ist $2^{20}-1$ durch 41 teilbar?

Man sieht leicht: $2^{5}\equiv -9\mod 41$.
Daraus folgt mit der Potenzregel ($a=2^{5},b=-9$): $\left(2^{5}\right)^{4}\equiv (-9)^{4}\equiv 81\cdot 81\mod 41$.
Andererseits gilt: $81\equiv -1\mod 41$. Die Potenzregel liefert $81^{2}\equiv (-1)^{2}\equiv 1\mod 41$.
Insgesamt ergibt sich nun: $2^{20}-1\equiv (81\cdot 81)-1\equiv 1-1\equiv 0\mod 41$

Antwort: $2^{20}-1$ ist durch 41 teilbar.

Beispiel 3

Behauptung: $2^{340}-1$ ist durch 341 teilbar.

Von dieser Eigenschaft ist im Artikel Fermatscher Primzahltest die Rede. Sie besagt, dass die Zahl 341 eine (fermatsche) Pseudoprimzahl zur Basis 2 ist.

Beweis: $2^{10}=1024=3\cdot 341+1\equiv 1\mod 341$

$\Rightarrow 2^{340}=\left(2^{10}\right)^{34}\equiv 1^{34}\equiv 1\mod 341$

$\Rightarrow 2^{340}-1\equiv 1-1\equiv 0\mod 341$

Beispiel 4

Frage: Welches ist der Rest, wenn man die Summe $s(9999):=1!+2!+3!+\ldots +9999!$ durch 12 teilt?
Gesucht wird ein $n$ mit $s(9999)\equiv n\mod 12$.

Es gilt: $1!+2!+3!\equiv 9\mod 12$
und $4!=1\cdot 2\cdot 3\cdot 4\equiv 0\mod 12$
Daraus folgt mit der Multiplikationsregel für $k>3:k!=4!\cdot 5\cdot 6\cdot \ldots \cdot k\equiv 0\cdot 5\cdot 6\cdot \ldots \cdot k\mod 12\equiv 0\mod 12$
Anwendung der Additionsregel liefert $s(9999)=1!+2!+3!+4!+\ldots +9999!\equiv 1!+2!+3!+0\mod 12\equiv 9\mod 12$

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

Siehe auch: Modulo (Rest)

Beispiel 5

Frage: Was ist das Inverse von 71 in 101?

Mit folgendem Algorithmus kann man das Inverse von a in b berechnen:

a - 0 * b = a

71 - 0 * 101 = 71

101 - 1 * 71 = 30

71 - 2 * 30 = 11

30 - 2 * 11 = 8

11 - 1 * 8 = 3

8 - 2 * 3 = 2

3 - 1 * 2 = 1 = ggT

2 - 2 * 1 = 0

x0 - c * x1 = x0 mit x0 = 1, x1 = 0 und für c setze die fetten Zahlen jeweils (von oben nach unten) ein.

1 - 0 * 0 = 1

0 - 1 * 1 = -1

1 - 2 * (-1) = 3

-1 - 2 * 3 = -7

3 - 1 * (-7) = 10

-7 - 2 * 10 = -27

10 - 1 * (-27) = 37 = Inverse.