Formelsammlung Mathematik: Kongruenzrechnung
↑ Formelsammlung Mathematik |
Kleiner fermatscher SatzBearbeiten
Satz von Euler-FermatBearbeiten
Satz von WilsonBearbeiten
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-QuotientenBearbeiten
Aus
folgt .
Somit ist .
Auf der anderen Seite ist .
Addiert man und , so ist ,
gleichbedeutend mit .
Kongruenz von BabbageBearbeiten
Kongruenzen von WolstenholmeBearbeiten
Da eine Permutation ist, ist
[Summe von Kehrwerten]Bearbeiten
[Kongruenz von Babbage, Exponent drei]Bearbeiten
Hierbei ist und .
Also ist .
Kongruenz von LjunggrenBearbeiten
Kongruenz von Gauß und BeukersBearbeiten
- Für eine Primzahl der Form gibt es eine Darstellung mit ungeradem .
Kongruenz von MorleyBearbeiten
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 JacobiBearbeiten
- Ist und mit , so gilt .
Pepin TestBearbeiten
2n≡2m mod 2kBearbeiten
Touchards KongruenzBearbeiten
Kummersche KongruenzBearbeiten
- Ist eine Primzahl und sind zwei positive gerade Zahlen mit , so gilt .
Von Staudt-Clausen-TheoremBearbeiten
- 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 .