Beispiele für die Anwendung von Kongruenzen

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.

Beispiel 1

Mit welcher Ziffer endet die Zahl 333222333^{222}?
Es ist 333≡3mod  10333 \equiv 3 \mod 10. Daraus folgt mit der Potenzregel (a=333a=333, b=3b=3, m=10m=10, n=222n=222): 333222≡3222mod  10333^{222} \equiv 3^{222} \mod 10.
Es gilt 32≡(−1)mod  103^2 \equiv (-1) \mod 10. Erneute Anwendung der Potenzregel (a=32a=3^2, b=−1b=-1, m=10m=10, n=111n=111) liefert: 3222=32⋅111≡(−1)111≡−1≡9mod  103^{222} = 3^{2 \cdot 111} \equiv (-1)^{111} \equiv -1 \equiv 9 \mod 10.
Die Endziffer lautet 9.

Beispiel 2

Ist 220−12^{20} - 1 durch 41 teilbar?
Man sieht leicht: 32=25≡−9mod  4132=2^5 \equiv -9 \mod 41.
Daraus folgt mit der Potenzregel (a=25a = 2^5, b=−9b = -9): (25)4≡(−9)4≡81⋅81mod  41\braceNT{2^5}^4 \equiv (-9)^4\equiv 81 \cdot 81 \mod 41.
Andererseits gilt: 81≡−1mod  4181 \equiv -1 \mod 41. Die Potenzregel liefert 812≡(−1)2≡1mod  4181^2 \equiv (-1)^2\equiv 1 \mod 41.
Insgesamt ergibt sich nun: 220−1≡(81⋅81)−1≡1−1≡1−1≡0mod  412^{20} - 1 \equiv (81 \cdot 81) - 1 \equiv 1 - 1 \equiv 1 - 1 \equiv 0 \mod 41
220−12^{20} - 1 ist durch 41 teilbar.

Beispiel 3

Behauptung: 2340−12^{340} - 1 ist durch 341 teilbar.
Diese Eigenschaft besagt, dass die Zahl 341 eine fermatsche Pseudoprimzahl zur Basis 2 ist.
210=1024=3⋅341+1≡1mod  3412^{10} = 1024 = 3 \cdot 341 + 1 \equiv 1 \mod 341
⇒2340=(210)34≡134≡1mod  341\Rightarrow 2^{340} = \braceNT{2^{10}}^{34} \equiv 1^{34}\equiv 1 \mod 341
⇒2340−1≡1−1≡0mod  341\Rightarrow 2^{340} - 1 \equiv 1 - 1 \equiv 0 \mod 341

Beispiel 4

Welches ist der Rest, wenn man die Summe
s(9999):=1!+2!+3!+…+9999!s(9999) := 1! + 2! + 3! + \ldots +9999!
durch 12 teilt?
Gesucht wird ein nn mit s(9999)≡nmod  12s(9999) \equiv n \mod 12.
Es gilt: 1!+2!+3!≡9mod  121! + 2! + 3! \equiv 9 \mod 12 und 4!=1⋅2⋅3⋅4≡0mod  124! = 1 \cdot 2 \cdot 3 \cdot 4 \equiv 0 \mod 12
Daraus folgt mit der Multiplikationsregel für k>3:k!=4!⋅5⋅6⋅…⋅k≡0⋅5⋅6⋅…⋅kmod  12≡0mod  12k > 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!+…+9999!s(9999) = 1! + 2! + 3! + 4! + \ldots + 9999! ≡1!+2!+3!+0mod  12≡9mod  12\equiv 1! + 2! + 3! + 0 \mod 12 \equiv 9 \mod 12
Wenn man s(9999)s(9999) durch 12 teilt, dann bleibt als Rest 9 übrig. Aus der Herleitung folgt allgemeiner: s(k)≡9mod  12s(k) \equiv 9 \mod 12 für alle k≥3k \geq 3.
 
 

Es gibt jedoch noch einen anderen Grund für die hohe Wertschätzung der Mathematik; sie allein bietet den Naturwissenschaften ein gewisses Maß an Sicherheit, das ohne Mathematik nicht erreichbar wäre.

Albert Einstein

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Kongruenz (Zahlentheorie) aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Elementare Zahlentheorie