Weitere Beispiele für die Anwendung von Kongruenzen

Beispiel 1

Für jede ganze Zahl aa gilt a3≡amod  6a^3 \equiv a \mod 6Mit anderen Worten: Teilt man a3a^3 durch 6, dann bleibt als Rest die Zahl a mod 6 selbst.
Es ist a3−a=a(a2−1)=a(a−1)(a+1)a^3-a=a(a^2-1)=a(a-1)(a+1). Dieses Produkt ist sowohl durch 2 als auch durch 3 teilbar, daher auch durch 6. Damit gilt a3−a≡0mod  6a^3-a\equiv 0\mod 6.

Beispiel 2

Für welche natürlichen Zahlen nn ist 5n−4n5^n-4^n durch 61 teilbar?
Durch Probieren findet man sehr schnell: 61∣125−62=53−4361|125-62=5^3-4^3 und vermutet damit, dass 61∣5n−4n61|5^n-4^n genau dann, wenn 3∣n3|n gilt.
Es ist 53=125≡3mod  615^3=125\equiv 3\mod 61 und auch 43=64≡3mod  614^3=64\equiv 3\mod 61 und daher 53k≡3kmod  615^{3k}\equiv 3^k\mod 61 und 43k≡3kmod  614^{3k}\equiv 3^k\mod 61, also 53k−43k≡0mod  615^{3k}-4^{3k}\equiv 0\mod 61.
Bleibt zu zeigen, dass Zahlen der Form 53k+1−43k+15^{3k+1}-4^{3k+1} und 53k+2−43k+25^{3k+2}-4^{3k+2} nicht durch 6161 teilbar sind.
53k+1−43k+1=53k⋅5−43k⋅45^{3k+1}-4^{3k+1}=5^{3k}\cdot 5-4^{3k}\cdot 4 ≡3k⋅5−3k⋅4\equiv 3^k\cdot 5-3^k\cdot 4 =3k⋅1=3kmod  61=3^k\cdot 1=3^k\mod 61. Nun sind 3 und 61 teilerfremd, daher ist das Ergebnis dieser Kongruenz niemals 0.
53k+2−43k+2=53k⋅25−43k⋅165^{3k+2}-4^{3k+2}=5^{3k}\cdot 25-4^{3k}\cdot 16 ≡3k⋅25−3k⋅16\equiv 3^k\cdot 25-3^k\cdot 16 =3k⋅9=3k+2mod  61=3^k\cdot 9=3^{k+2}\mod 61 und weil 3 und 61 teilerfremd sind...
 
 

Beispiel 3

Sei p>3p > 3. Ferner seien pp und q=p+2q = p + 2 Primzahlzwillinge. Dann gilt: p⋅q≡−1mod  9p \cdot q \equiv -1 \mod 9
Notwendigerweise müssen die Primzahlzwillinge die Form p=2k+2p=2k+2 und p+2=3k+4p+2=3k+4 haben. (Ist p=3k+1p=3k+1, so wäre p+2p+2 durch 3 teilbar.)
p⋅q=(3k+2)(3k+4)=9k2+18k+8≡8mod  9p\cdot q=(3k+2)(3k+4)=9k^2+18k+8\equiv 8\mod 9.

Hochtechnologie ist im wesentlichen mathematische Technologie.

Enquete-Kommission der Amerikanischen Akademie der Wissenschaften

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
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