Formelsammlung Mathematik: Kongruenzrechnung
↑ Formelsammlung Mathematik |
Kleiner fermatscher Satz Bearbeiten
Satz von Euler-Fermat Bearbeiten
Satz von Wilson Bearbeiten
Bei der Formel
setze und .
Unter Verwendung des kleinen fermatschen Satzes ist
Im Körper sind invertierbar.
Da nur zwei Lösungen besitzt, sind und
die einzigen Elemente, die zu sich selbst invers sind.
Im Produkt kommt bei jedem Faktor auch der inverse Faktor an
einer anderen Stelle vor.
Also ist und somit .
Das Polynom hat in nach dem kleinen fermatschen Satz die Nullstellen .
Also gilt die Faktorisierung .
Setzt man so ist .
Verallgemeinerung des Satzes von Wilson durch Gauß Bearbeiten
- Es sei .
- Ist gleich oder von der Form , wobei eine ungerade Primzahl ist, so gilt .
- In allen anderen Fällen ist .
Eisensteins Kongruenz über den Fermat-Quotienten Bearbeiten
Aus
folgt .
Somit ist .
Auf der anderen Seite ist .
Addiert man und , so ist ,
gleichbedeutend mit .
Kongruenz von Babbage Bearbeiten
Kongruenzen von Wolstenholme Bearbeiten
Da eine Permutation ist, ist
[Summe von Kehrwerten] Bearbeiten
[Kongruenz von Babbage, Exponent drei] Bearbeiten
Hierbei ist und .
Also ist .
Kongruenz von Ljunggren Bearbeiten
Kongruenz von Gauß und Beukers Bearbeiten
- Für eine Primzahl der Form gibt es eine Darstellung mit ungeradem .
Kongruenz von Morley Bearbeiten
Setzt man und , so ist
und .
Also ist ,
und damit ist .
Auf der anderen Seite ist .
Dabei ist .
Somit ist ,
und damit ,
und damit
.
Kongruenz von Jacobi Bearbeiten
- Ist und mit , so gilt .
Pepin Test Bearbeiten
2n≡2m mod 2k Bearbeiten
Touchards Kongruenz Bearbeiten
Kummersche Kongruenz Bearbeiten
- Ist eine Primzahl und sind zwei positive gerade Zahlen mit , so gilt .
Von Staudt-Clausen-Theorem Bearbeiten
- Ist eine positive gerade Zahl, so gilt .
[Binomialkoeffizient und p-adische Darstellung] Bearbeiten
- Ist p eine Primzahl und sind Tupel natürlicher Zahlen, so dass
- und die p-adischen Zifferndarstellungen
- der natürlichen Zahlen und sind, so gilt , wobei ist.
In Anbetracht der Gleichung
ist
.
1.Fall:
Unter der Induktionsvoraussetzung ist
.
Kürzt man heraus, so ist .
2.Fall:
Aus folgt
und wegen ist auch .
3.Fall:
Hier ist und , also und .
Es gilt , wobei ist.
Daher ist
, was nach Induktionsvoraussetzung
ist.
Wegen ist damit auch .
4.Fall:
Es gilt .
Wegen ist
,
und daher ist . Kürzt man heraus, so ist .
Nach dem 3.Fall ist , was nach Induktionsvoraussetzung
ist. Und nachdem ist, gilt also .