Kongruenz (Zahlentheorie)

In der Zahlentheorie heißen zwei ganze Zahlen a und b kongruent modulo m (wobei m eine positive ganze Zahl ist), wenn m die Differenz (a-b) teilt. Man schreibt:

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.

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 von a modulo m:

Es gibt daher genau m Restklassen () modulo m.

Beispiel:

Modulo 2 sind die beiden Restklassen die Menge der geraden Zahlen () und die Menge der ungeraden Zahlen ().

Die Restklassen modulo m bilden einen Ring. 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.

Table of contents

1 elementare Rechenregeln 2 abgeleitete Rechenregeln 3 Anwendungen 3.1 Beispiel 1 3.2 Beispiel 2 3.3 Beispiel 3 3.4 Beispiel 4 4 Weblinks

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:

•                       Reflexivität
•                       Symmetrie
•                      Transitivität
•                 Skalarmultiplikation
•      Addition
•      Subtraktion
•                  Multiplikation
•                  Potenzregel

Weiterhin gilt für das Rechnen mit Restklassen:

•                           Addition
•                           Subtraktion
•                                 Multiplikation

abgeleitete Rechenregeln

1. Für t ≠ 0 gilt:      t · a ≡ t · b mod |t| · m
   
   
2. Ist k ein Teiler von m, dann gilt:      a ≡ b mod k
   
   
3. 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
   
   
4. Sei c · a ≡ c · b mod p mit eine Primzahl p, wobei p kein Teiler von c ist. Dann gilt: a ≡ b mod p
   
   
5. Sei a ≡ b mod n und c > 0. Dann gilt: c·a ≡ c·b mod (c·n)
   
   
6. 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)
   
   
7. Für jede ungerade Zahl a gilt a² ≡ 1 mod 8
   Mit anderen Worten: Teilt man a² durch 8, dann bleibt als Rest 1.
   
   
8. 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.
   
   
9. 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.
   
   
10. 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.
    
    
11. 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
    
    
12. 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
    
    
13. Sei p eine Primzahl mit n < p < 2n. Dann gilt
    :
    
    
14. Sei a eine ungerade ganze Zahl. Ferner sei n > 0. Dann gilt: a²ⁿ ≡ 1 mod 2ⁿ⁺²
    
    
15. 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
    
    
16. Es gelte a ≡ b mod x und a ≡ c mod y sowie n = ggT(x,y). Daraus folgt: b ≡ c mod n
    
    
17. 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²²²?

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=74) liefert: 3²²² = 3^3*74 ≡ (-1)⁷⁴ mod 10 = 1.

Antwort: Die Endziffer lautet 1.

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.
Andrerseits 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.

Weblinks

• http://www.heldermann-verlag.de/ebooks/Burton/E4%20Kapitel%204.pdf