Formelsammlung Mathematik: Kongruenzrechnung

Aus Wikibooks

Wechseln zu: Navigation, Suche

Zurück zur Formelsammlung Mathematik

Inhaltsverzeichnis

1 Kleiner Fermatscher Satz
2 Satz von Euler-Fermat
3 Satz von Wilson
4 Verallgemeinerung des Satzes von Wilson durch Gauß
5 Kongruenz von Babbage
6 Kongruenz von Wolstenholme
7 Kongruenz von Ljunggren
8 Kongruenz von Gauß und Beukers
9 Kongruenz von Morley
10 Kongruenz von Jacobi
11 Pepin's Test
12 Kongruenz mit Eulerzahlen
13 Touchards Kongruenz
14 Kummersche Kongruenz
15 Clausen von Staudt Kongruenz
16 Lucas Kongruenz

[Bearbeiten] Kleiner Fermatscher Satz

$a^{p-1}\equiv 1 \, \text{mod} \, p \qquad p\!\!\not| a$

[Bearbeiten] Satz von Euler-Fermat

$a^{\varphi(n)}\equiv 1 \, \text{mod} \, n \qquad (a,n)=1$

[Bearbeiten] Satz von Wilson

$(p-1)!\equiv -1 \, \text{mod} \, p \iff p\in\Bbb{P}$

1. Beweis der Rückrichtung

Bei der Formel $n!=\sum_{k=0}^n (-1)^k\, {n\choose k}\, (x-k)^n$ setze $n=p-1\,$ und $x=0\,$ .

$(p-1)!=\sum_{k=1}^{p-1} (-1)^k \, {p-1 \choose k}\, (-k)^{p-1}$

Unter Verwendung des kleinen Fermatschen Satzes ist

$(p-1)!\equiv \sum_{k=1}^{p-1} (-1)^k \, {p-1\choose k}=(1-1)^{p-1}-1=-1 \mod \, p$

2. Beweis der Rückrichtung

Im Körper $\Bbb{F}_p$ sind $1,2,...,p-1\,$ invertierbar.

Da $X^2-1=0\,$ nur zwei Lösungen besitzt, sind $1\,$ und $p-1\,$ die einzigen Elemente, die zu sich selbst invers sind.

Im Produkt $2\cdot 3\cdots (p-2)$ kommt bei jedem Faktor auch der inverse Faktor an einer anderen Stelle vor.

Also ist $(p-2)!\equiv 1 \, \text{mod} \, p$ und somit $(p-1)!\equiv -1 \, \text{mod} \, p$ .

3. Beweis der Rückrichtung

Das Polynom $X^{p-1}-1\,$ hat in $\Bbb{F}_p$ nach dem kleinen Fermatschen Satz die Nullstellen $1,2,...,p-1\,$ .

Also gilt die Faktorisierung $X^{p-1}-1=(X-1)(X-2)\cdots (X-(p-1))$ .

Setzt man $X=0\,$ so ist $-1=(-1)(-2)\cdots (-(p-1))=(-1)^{p-1}\, (p-1)!$ .

[Bearbeiten] Verallgemeinerung des Satzes von Wilson durch Gauß

Es sei $P(n):=\prod\limits_{1<k<n \atop (k,n)=1} k$

Ist $n\,$ gleich $4\,$ oder von der Form $p^k,2 p^k\,$ , wobei $p\,$ eine ungerade Primzahl ist, so gilt $P(n)\equiv -1 \, \text{mod} \, n$ .

In allen anderen Fällen ist $P(n)\equiv 1 \, \text{mod} \, n$ .

[Bearbeiten] Kongruenz von Babbage

${2p-1 \choose p-1} \equiv 1 \, \text{mod} \, p^2 \qquad p\in\Bbb{P}^{\ge 3}$

[Bearbeiten] Kongruenz von Wolstenholme

${2p-1 \choose p-1} \equiv 1 \, \text{mod} \, p^3 \qquad p\in\Bbb{P}^{\ge 5}$

[Bearbeiten] Kongruenz von Ljunggren

${np \choose mp} \equiv {n\choose m} \, \text{mod} \, p^3 \qquad p\in\Bbb{P}^{\ge 5}$

[Bearbeiten] Kongruenz von Gauß und Beukers

Für eine Primzahl $p\,$ der Form $4n+1\,$ gibt es eine Darstellung $p=a^2+b^2\,$ mit ungeradem $a\equiv 1 \, \text{mod} \, 4$ .

${(p-1)/2 \choose (p-1)/4} \equiv 2a \, \text{mod} \, p \qquad {(p-1)/2 \choose (p-1)/4} \equiv \left(1+\frac{2^{p-1}-1}{2}\right)\left(2a-\frac{p}{2a}\right) \, \text{mod} \, p^2$

[Bearbeiten] Kongruenz von Morley

$(-1)^{\frac{p-1}{2}} {p-1 \choose (p-1)/2} \equiv 4^{p-1} \, \text{mod} \, p^3 \qquad p\in\Bbb{P}^{\ge 5}$

[Bearbeiten] Kongruenz von Jacobi

Ist $p\equiv 1 \, \text{mod} \, 3$ und $4p=\Lambda^2+27 B^2\,$ mit $\Lambda\equiv 1 \, \text{mod} \, 3$ so gilt

${2(p-1)/3 \choose (p-1)/3} \equiv -\Lambda \, \text{mod} \, p$

[Bearbeiten] Pepin's Test

$3^{\frac12 (F_n-1)} \equiv -1 \, \text{mod} \, F_n \iff F_n\in\Bbb{P} \quad , \quad F_n=2^{2^n}+1$

[Bearbeiten] Kongruenz mit Eulerzahlen

$2n\equiv 2m \, \text{mod} \, 2^k \, \Rightarrow \, E_{2n}-E_{2m}=-(2n-2m) \, \text{mod} \, 2^{k+1}$

[Bearbeiten] Touchards Kongruenz

$B_{n+p^m}\equiv m B_n+B_{n+1} \; \text{mod} \; p$

[Bearbeiten] Kummersche Kongruenz

Ist $p\,$ eine Primzahl und sind $k,\ell$ zwei positive gerade Zahlen mit $k\equiv \ell\not\equiv 0 \, \text{mod} \, p-1$ so gilt $\frac{B_k}{k}\equiv\frac{B_\ell}{\ell} \; \text{mod} \; p$ .

[Bearbeiten] Clausen von Staudt Kongruenz

Ist $k\,$ eine positive gerade Zahl so gilt $B_k\equiv -\sum_{p-1|k} \frac{1}{p} \; \text{mod} \; \Bbb{Z}$ .

[Bearbeiten] Lucas Kongruenz

Ist $p\,$ eine Primzahl, sind $\boldsymbol{a}=(a_0,...,a_n), \boldsymbol{b}=(b_0,...,b_n)$ Tupel natürlicher Zahlen

und ist $\alpha=\sum_{k=0}^n a_k\, p^k \, , \, \beta=\sum_{k=0}^n b_k\, p^k$ so gilt ${\alpha\choose \beta}={\boldsymbol{a} \choose \boldsymbol{b}} \; \text{mod} \; p$ .