Kongruenz (Zahlentheorie)

<math>a\equiv{}b\mod{}m\qquad\mathrm{oder}\qquad{}a\equiv{}b\ (\mathrm{mod}\ m)</math>

Anders formuliert kann man auch sagen 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 -21 (=3-24)
• -31 ≡ 11 mod 7 denn 7 -42 (=-31-11)
• -15 ≡ -64 mod 7 denn 7 49 (=-15-(-64))

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

<math>\bar{a} := \{ x \in \mathbb{Z} a\equiv{}x \mod m\}</math>

Es gibt daher genau m Restklassen (<math>\bar{0} \bar{1} \dots \overline{m-1}</math>) modulo m .

Beispiel:

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

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 anhand des Ziffernblattes einer Analoguhr. Die Stunden von 1 bis 12 nummeriert wobei Stunde als Stunde 0 betrachtet wird.

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

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

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

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

elementare Rechenregeln

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

Gilt a ≡ b (mod m) c ≡ d (mod m) und b x (mod m) so gilt:

• <math>a \equiv a \mod m</math>                        Reflexivität
• <math>b \equiv a \mod m</math>                        Symmetrie
• <math>a \equiv x \mod m</math>                       Transitivität
• <math>na \equiv nb \mod m</math>                  Skalarmultiplikation
• <math>a + c \equiv b + \mod m</math>       Addition
• <math>a - c \equiv b - \mod m</math>       Subtraktion
• <math>ac \equiv bd \mod m</math>                   Multiplikation
• <math>a^n \equiv b^n \mod m</math>                   Potenzregel

Weiterhin gilt für das Rechnen mit

• <math>\overline{a+c} = \bar{a} + \bar{c}</math>                           Addition
• <math>\overline{a-c} = \bar{a} - \bar{c}</math>                           Subtraktion
• <math>\overline{ac} = \bar{a} * \bar{c}</math>                                 Multiplikation

abgeleitete Rechenregeln

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

Anwendungen

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

Ferner sind Kongruenzen bzw. Restklassen oft wenn man Berechnungen mit sehr großen Zahlen muss.

Siehe auch: lineare Kongruenz simultane Kongruenz chinesischer Restsatz

Beispiel 1

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

333 ≡ 3 mod 10
Daraus folgt mit der Potenzregel (a=333 b=3 n=222): 333 ²²² ≡ 3 ²²² mod 10
Es gilt 3 ³ ≡ (-1) mod 10. Erneute Anwendung 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.
Andererseits gilt: 81 ≡ -1 mod 41. Potenzregel liefert 81 ² ≡ (-1) ² mod 41 = 1 mod 41.
Insgesamt ergibt sich nun: 2 ²⁰ -1 ≡ 81·81 mod 41 -1 ≡ mod 41) mod 41 - 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 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 =

Beispiel 4

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

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

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

siehe auch: Modulo

Weblinks

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

Bücher zum Thema Kongruenz (Zahlentheorie)

Dieser Artikel von Wikipedia unterliegt der GNU FDL.