Formelsammlung Mathematik: Kongruenzrechnung

↑ Formelsammlung Mathematik

Kleiner fermatscher Satz

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

ohne Beweis (Kleiner fermatscher Satz)

 

Satz von Euler-Fermat

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

ohne Beweis (Satz von Euler-Fermat)

 

Satz von Wilson

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

1. Beweis der Rückrichtung (Satz von Wilson)

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 $\mathbb {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 $\mathbb {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)!$.

 

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},2p^{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$.

ohne Beweis (Verallgemeinerung des Satzes von Wilson durch Gauß)

 

Eisensteins Kongruenz über den Fermat-Quotienten

$\sum _{k=1}^{(p-1)/2}{\frac {1}{k}}\equiv -2q_{p}(2)\;{\text{mod}}\;p$

1. Beweis (Eisensteins Kongruenz über den Fermat-Quotienten $q_{p}(2)={\frac {2^{p-1}-1}{p}}$)

$2^{p-1}=\prod _{k=1}^{(p-1)/2}\left(1+{\frac {p}{2k-1}}\right)=1+\sum _{k=1}^{(p-1)/2}{\frac {p}{2k-1}}+O(p^{2})$

$\Rightarrow {\frac {2^{p-1}-1}{p}}\equiv \sum _{k=1}^{(p-1)/2}{\frac {1}{2k-1}}\equiv -\sum _{k=1}^{(p-1)/2}{\frac {1}{2k}}\;{\text{mod}}\;p$

$\Rightarrow -2\cdot {\frac {2^{p-1}-1}{p}}\equiv \sum _{k=1}^{(p-1)/2}{\frac {1}{k}}\;{\text{mod}}\;p$

 

2. Beweis

Aus ${p \choose k}=p\cdot {\frac {p-1}{1}}\cdot {\frac {p-2}{2}}\cdots {\frac {p-(k-1)}{k-1}}\cdot {\frac {1}{k}}$

folgt ${\frac {1}{p}}\,{p \choose k}\equiv {\frac {0-1}{1}}\cdot {\frac {0-2}{2}}\cdots {\frac {0-(k-1)}{k-1}}\cdot {\frac {1}{k}}=(-1)^{k-1}\cdot {\frac {1}{k}}\;{\text{mod}}\;p$.

Somit ist $\sum _{k=1}^{p-1}{\frac {(-1)^{k}}{k}}\equiv -{\frac {1}{p}}\sum _{k=1}^{p-1}{p \choose k}=-{\frac {1}{p}}\left(2^{p}-2\right)\;{\text{mod}}\;p\quad {\text{(i)}}$.

Auf der anderen Seite ist $\sum _{k=1}^{p-1}{\frac {1}{k}}\equiv \sum _{k=1}^{p-1}k={\frac {p\cdot (p-1)}{2}}\equiv 0\;{\text{mod}}\;p\quad {\text{(ii)}}$.

Addiert man ${\text{(i)}}\,$ und ${\text{(ii)}}\,$, so ist $\sum _{k=1}^{(p-1)/2}{\frac {2}{2k}}\equiv -{\frac {1}{p}}\left(2^{p}-2\right)\;{\text{mod}}\;p$,

gleichbedeutend mit $\sum _{k=1}^{(p-1)/2}{\frac {1}{k}}\equiv -2q_{p}(2)\;{\text{mod}}\;p$.

 

Kongruenz von Babbage

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

ohne Beweis (Kongruenz von Babbage)

 

Kongruenzen von Wolstenholme

$2\sum _{k=1}^{(p-1)/2}{\frac {1}{k^{2}}}\equiv \sum _{k=1}^{p-1}{\frac {1}{k^{2}}}\equiv 0\;{\text{mod}}\;p\qquad p\in \mathbb {P} ^{\geq 5}$

Beweis (Kongruenzen von Wolstenholme)

$2\sum _{k=1}^{(p-1)/2}{\frac {1}{k^{2}}}\equiv \sum _{k=1}^{(p-1)/2}{\frac {1}{k^{2}}}+\sum _{k=1}^{(p-1)/2}{\frac {1}{(p-k)^{2}}}=\sum _{k=1}^{p-1}{\frac {1}{k^{2}}}\;{\text{mod}}\;p$

Da $\sigma :\mathbb {F} _{p}^{\times }\to \mathbb {F} _{p}^{\times }\,,\,k\mapsto {\frac {1}{k}}$ eine Permutation ist, ist

$\sum _{k=1}^{p-1}{\frac {1}{k^{2}}}\equiv \sum _{k=1}^{p-1}k^{2}={\frac {(p-1)\cdot p\cdot (2p-1)}{6}}\equiv 0\;{\text{mod}}\;p$

 

[Summe von Kehrwerten]

$\sum _{k=1}^{p-1}{\frac {1}{k}}\equiv 0\;{\text{mod}}\;p^{2}\qquad p\in \mathbb {P} ^{\geq 5}$

Beweis

$\sum _{k=1}^{p-1}{\frac {1}{k}}=\sum _{k=1}^{(p-1)/2}\left({\frac {1}{k}}+{\frac {1}{p-k}}\right)=\sum _{k=1}^{(p-1)/2}{\frac {p}{k\cdot (p-k)}}$

$\Rightarrow {\frac {1}{p}}\,\sum _{k=1}^{p-1}{\frac {1}{k}}=\sum _{k=1}^{(p-1)/2}{\frac {1}{k\cdot (p-k)}}\equiv -\sum _{k=1}^{(p-1)/2}{\frac {1}{k^{2}}}\equiv 0\;{\text{mod}}\;p$

$\Rightarrow \sum _{k=1}^{p-1}{\frac {1}{k}}\equiv 0\;{\text{mod}}\;p^{2}$

 

[Kongruenz von Babbage, Exponent drei]

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

Beweis

${2p-1 \choose p-1}=\prod _{k=1}^{p-1}\left(1+{\frac {p}{k}}\right)=1+\sum _{k=1}^{p-1}{\frac {p}{k}}+\sum _{1\leq i<j\leq p-1}{\frac {p^{2}}{ij}}+O(p^{3})$

Hierbei ist $\sum _{k=1}^{p-1}{\frac {1}{k}}=O(p^{2})$ und $2\sum _{1\leq i<j\leq p-1}{\frac {1}{ij}}=\left(\sum _{k=1}^{p-1}{\frac {1}{k}}\right)^{2}-\sum _{k=1}^{p-1}{\frac {1}{k^{2}}}=O(p)$.

Also ist ${2p-1 \choose p-1}=1+O(p^{3})$.

 

Kongruenz von Ljunggren

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

ohne Beweis (Kongruenz von Ljunggren)

 

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\,\,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}$

ohne Beweis (Kongruenz von Gauß und Beukers)

 

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 \mathbb {P} ^{\geq 5}$

Beweis (Kongruenz von Morley)

$2^{p-1}=\prod _{k=1}^{(p-1)/2}\left(1+{\frac {p}{2k-1}}\right)=1+\sum _{k=1}^{(p-1)/2}{\frac {p}{2k-1}}+\sum _{1\leq k<j\leq (p-1)/2}{\frac {p}{2k-1}}\,{\frac {p}{2j-1}}+O(p^{3})$

Setzt man $Z=\sum _{k=1}^{(p-1)/2}{\frac {1}{2k-1}}$ und $T=\sum _{k=1}^{(p-1)/2}{\frac {1}{(2k-1)^{2}}}$, so ist $Z^{2}-T=2\sum _{1\leq k<j\leq (p-1)/2}{\frac {1}{2k-1}}\,{\frac {1}{2j-1}}$

und $2T=\sum _{k=1}^{(p-1)/2}{\frac {1}{(2k-1)^{2}}}+\sum _{k=1}^{(p-1)/2}{\frac {1}{(p-2k)^{2}}}\equiv \sum _{k=1}^{p-1}{\frac {1}{k^{2}}}\equiv 0\;{\text{mod}}\;p$.

Also ist $2^{p-1}\equiv 1+pZ+{\frac {p^{2}}{2}}(Z^{2}-T)\equiv 1+pZ+{\frac {p^{2}}{2}}Z^{2}\;{\text{mod}}\;p^{3}$,

und damit ist $4^{p-1}\equiv \left(1+pZ+{\frac {p^{2}}{2}}Z^{2}\right)^{2}=1+2pZ+2p^{2}Z^{2}+p^{3}Z^{3}+{\frac {p^{4}}{2}}Z^{4}\equiv 1+2pZ+2p^{2}Z^{2}\;{\text{mod}}\;p^{3}$.


Auf der anderen Seite ist $(-1)^{(p-1)/2}{p-1 \choose (p-1)/2}=\prod _{k=1}^{(p-1)/2}{\frac {1+{\frac {p}{2k-1}}}{1-{\frac {p}{2k-1}}}}$.

Dabei ist $\left(1-{\frac {p}{2k-1}}\right)\left(1+{\frac {p}{2k-1}}+{\frac {p^{2}}{(2k-1)^{2}}}\right)=1-{\frac {p^{3}}{(2k-1)^{3}}}\equiv 1\;{\text{mod}}\;p^{3}$.

Somit ist $\left(1-{\frac {p}{2k-1}}\right)^{-1}=1+{\frac {p}{2k-1}}+{\frac {p^{2}}{(2k-1)^{2}}}\;{\text{mod}}\;p^{3}$,

und damit ${\frac {1+{\frac {p}{2k-1}}}{1-{\frac {p}{2k-1}}}}=1+{\frac {2p}{2k-1}}+{\frac {2p^{2}}{(2k-1)^{2}}}\;{\text{mod}}\;p^{3}$,

und damit $\prod _{k=1}^{(p-1)/2}\left(1+{\frac {2p}{2k-1}}+{\frac {2p^{2}}{(2k-1)^{2}}}\right)=1+\sum _{k=1}^{(p-1)/2}\left(1+{\frac {2p}{2k-1}}+{\frac {2p^{2}}{(2k-1)^{2}}}\right)$

$+\sum _{1\leq k<j\leq (p-1)/2}\left(1+{\frac {2p}{2k-1}}+{\frac {2p^{2}}{(2k-1)^{2}}}\right)\left(1+{\frac {2p}{2j-1}}+{\frac {2p^{2}}{(2j-1)^{2}}}\right)+O(p^{3})$

$\equiv 1+2pZ+2p^{2}T+4p^{2}\sum _{1\leq k<j\leq (p-1)/2}{\frac {1}{2k-1}}\,{\frac {1}{2j-1}}\equiv 1+2pZ+2p^{2}T+2p^{2}(Z^{2}-T)\equiv 1+2pZ+2p^{2}Z^{2}\;{\text{mod}}\;p^{3}$.

 

Kongruenz von Jacobi

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

ohne Beweis (Kongruenz von Jacobi)

 

Pepin Test

$3^{{\frac {1}{2}}(F_{n}-1)}\equiv -1\,{\text{mod}}\,F_{n}\iff F_{n}\in \mathbb {P} \quad ,\quad F_{n}=2^{2^{n}}+1$

ohne Beweis (Pepin Test)

 

2n≡2m mod 2^k

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

ohne Beweis

 

Touchards Kongruenz

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

ohne Beweis (Touchards Kongruenz)

 

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$.

ohne Beweis (Kummersche Kongruenz)

 

Von Staudt-Clausen-Theorem

Ist $k\,$ eine positive gerade Zahl, so gilt $B_{k}\equiv -\sum _{p-1|k}{\frac {1}{p}}\;{\text{mod}}\;\mathbb {Z}$.

ohne Beweis (Von Staudt-Clausen-Theorem)

 

[Binomialkoeffizient und p-adische Darstellung]

Ist p eine Primzahl und sind ${\boldsymbol {a}}=(a_{0},...,a_{r})\,,\,{\boldsymbol {b}}=(b_{0},...,b_{r})$ Tupel natürlicher Zahlen, so dass

$\alpha =a_{0}+a_{1}p+a_{2}p^{2}+...+a_{r}p^{r}\,$ und $\beta =b_{0}+b_{1}p+b_{2}p^{2}+...+b_{r}p^{r}\,$ die p-adischen Zifferndarstellungen

der natürlichen Zahlen $\alpha \,$ und $\beta \,$ sind, so gilt ${\alpha \choose \beta }\equiv {{\boldsymbol {a}} \choose {\boldsymbol {b}}}\;{\text{mod}}\;p$, wobei ${{\boldsymbol {a}} \choose {\boldsymbol {b}}}={a_{0} \choose b_{0}}{a_{1} \choose b_{1}}\cdots {a_{r} \choose b_{r}}$ ist.

Beweis

In Anbetracht der Gleichung

$(1)\quad \beta \,{\alpha \choose \beta }=\alpha {\alpha -1 \choose \beta -1}$

ist

$(2)\quad b_{0}{\alpha \choose \beta }\equiv \beta {\alpha \choose \beta }\,{\stackrel {1}{=}}\,\alpha {\alpha -1 \choose \beta -1}\equiv a_{0}{\alpha -1 \choose \beta -1}\;{\text{mod}}\;p$.



1.Fall: $a_{0},b_{0}\neq 0\,$

Unter der Induktionsvoraussetzung ${\alpha -1 \choose \beta -1}={a_{0}-1 \choose b_{0}-1}{a_{1} \choose b_{1}}\cdots {a_{r} \choose b_{r}}\;{\text{mod}}\;p$ ist

$b_{0}{\alpha \choose \beta }\,{\stackrel {2}{\equiv }}\,a_{0}{\alpha -1 \choose \beta -1}=a_{0}{a_{0}-1 \choose b_{0}-1}{a_{1} \choose b_{1}}\cdots {a_{r} \choose b_{r}}\,{\stackrel {1}{=}}\,b_{0}{a_{0} \choose b_{0}}{a_{1} \choose b_{1}}\cdots {a_{r} \choose b_{r}}\;{\text{mod}}\;p$.

Kürzt man $b_{0}\,$ heraus, so ist ${\alpha \choose \beta }\equiv {{\boldsymbol {a}} \choose {\boldsymbol {b}}}\;{\text{mod}}\;p$.


2.Fall: $a_{0}=0,b_{0}\neq 0\,$

Aus $b_{0}{\alpha \choose \beta }\,{\stackrel {2}{\equiv }}\,a_{0}{\alpha -1 \choose \beta -1}=0\;{\text{mod}}\;p$ folgt ${\alpha \choose \beta }\equiv 0\;{\text{mod}}\;p$

und wegen ${a_{0} \choose b_{0}}=0$ ist auch ${{\boldsymbol {a}} \choose {\boldsymbol {b}}}={a_{0} \choose b_{0}}{a_{1} \choose b_{1}}\cdots {a_{r} \choose b_{r}}\equiv 0\;{\text{mod}}\;p$.


3.Fall: $a_{0}=b_{0}=0\,$

Hier ist $\alpha =np\,$ und $\beta =mp\,$, also $n=a_{1}+a_{2}p+...+a_{r}p^{r-1}\,$ und $m=b_{1}+b_{2}p+...+b_{r}p^{r-1}\,$.

Es gilt $(np)!=n!\,p^{n}\,A_{n}$, wobei $A_{n}={\frac {(np)!}{n!\,p^{n}}}\equiv ((p-1)!)^{n}\equiv (-1)^{n}\;{\text{mod}}\;p$ ist.

Daher ist ${\alpha \choose \beta }={np \choose mp}={\frac {(np)!}{(mp)!\,((n-m)p)!}}={\frac {n!\,p^{n}\,A_{n}}{m!\,p^{m}\,A_{m}\,\,(n-m)!\,p^{n-m}\,A_{n-m}}}$

$={n \choose m}{\frac {A_{n}}{A_{m}\,A_{n-m}}}\equiv {n \choose m}\;{\text{mod}}\;p$, was nach Induktionsvoraussetzung $\equiv {a_{1} \choose b_{1}}\cdots {a_{r} \choose b_{r}}\;{\text{mod}}\;p$ ist.

Wegen ${a_{0} \choose b_{0}}={0 \choose 0}=1$ ist damit auch ${\alpha \choose \beta }\equiv {{\boldsymbol {a}} \choose {\boldsymbol {b}}}\;{\text{mod}}\;p$.


4.Fall: $a_{0}\neq 0,b_{0}=0\;$

Es gilt $(\alpha -\beta )(\alpha -\beta -1)\cdots (\alpha -\beta -a_{0}+1){\alpha \choose \beta }=\alpha (\alpha -1)\cdots (\alpha -a_{0}+1){\alpha -a_{0} \choose \beta }$.

Wegen $\beta \equiv b_{0}=0\;{\text{mod}}\;p$ ist $(\alpha -\beta )(\alpha -\beta -1)\cdots (\alpha -\beta -a_{0}+1)$

$\equiv \alpha (\alpha -1)\cdots (\alpha -a_{0}+1)\equiv a_{0}(a_{0}-1)\cdots 1=a_{0}!\not \equiv 0\;{\text{mod}}\;p$,

und daher ist $a_{0}!\,{\alpha \choose \beta }\equiv a_{0}!\,{\alpha -a_{0} \choose \beta }\;{\text{mod}}\;p$. Kürzt man $a_{0}!\,$ heraus, so ist ${\alpha \choose \beta }\equiv {\alpha -a_{0} \choose \beta }\;{\text{mod}}\;p$.

Nach dem 3.Fall ist ${\alpha -a_{0} \choose \beta }\equiv {(\alpha -a_{0})/p \choose (\beta -b_{0})/p}\;{\text{mod}}\;p$, was nach Induktionsvoraussetzung

$\equiv {a_{1} \choose b_{1}}\cdots {a_{r} \choose b_{r}}\;{\text{mod}}\;p$ ist. Und nachdem ${a_{0} \choose b_{0}}=1$ ist, gilt also ${\alpha \choose \beta }\equiv {{\boldsymbol {a}} \choose {\boldsymbol {b}}}\;{\text{mod}}\;p$.