Formelsammlung Mathematik: Kongruenzrechnung

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

${\displaystyle (p-1)!=\sum _{k=1}^{p-1}(-1)^{k}\,{p-1 \choose k}\,(-k)^{p-1}}$

Unter Verwendung des kleinen fermatschen Satzes ist

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

Im Körper ${\displaystyle \mathbb {F} _{p}}$ sind ${\displaystyle 1,2,...,p-1\,}$ invertierbar.

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

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

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

Das Polynom ${\displaystyle X^{p-1}-1\,}$ hat in ${\displaystyle \mathbb {F} _{p}}$ nach dem kleinen fermatschen Satz die Nullstellen ${\displaystyle 1,2,...,p-1\,}$.

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

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

${\displaystyle 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})}$

${\displaystyle \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}$

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

Aus ${\displaystyle {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 ${\displaystyle {\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 ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle {\text{(i)}}\,}$ und ${\displaystyle {\text{(ii)}}\,}$, so ist ${\displaystyle \sum _{k=1}^{(p-1)/2}{\frac {2}{2k}}\equiv -{\frac {1}{p}}\left(2^{p}-2\right)\;{\text{mod}}\;p}$,

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

${\displaystyle 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 ${\displaystyle \sigma :\mathbb {F} _{p}^{\times }\to \mathbb {F} _{p}^{\times }\,,\,k\mapsto {\frac {1}{k}}}$ eine Permutation ist, ist

${\displaystyle \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}$

${\displaystyle \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)}}}$

${\displaystyle \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}$

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

${\displaystyle {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 ${\displaystyle \sum _{k=1}^{p-1}{\frac {1}{k}}=O(p^{2})}$ und ${\displaystyle 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 ${\displaystyle {2p-1 \choose p-1}=1+O(p^{3})}$.

${\displaystyle 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 ${\displaystyle Z=\sum _{k=1}^{(p-1)/2}{\frac {1}{2k-1}}}$ und ${\displaystyle T=\sum _{k=1}^{(p-1)/2}{\frac {1}{(2k-1)^{2}}}}$, so ist ${\displaystyle Z^{2}-T=2\sum _{1\leq k<j\leq (p-1)/2}{\frac {1}{2k-1}}\,{\frac {1}{2j-1}}}$

und ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle (-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 ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle {\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 ${\displaystyle \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)}$

${\displaystyle +\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})}$

${\displaystyle \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}}$.

In Anbetracht der Gleichung

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

ist

${\displaystyle (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: ${\displaystyle a_{0},b_{0}\neq 0\,}$

Unter der Induktionsvoraussetzung ${\displaystyle {\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

${\displaystyle 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 ${\displaystyle b_{0}\,}$ heraus, so ist ${\displaystyle {\alpha \choose \beta }\equiv {{\boldsymbol {a}} \choose {\boldsymbol {b}}}\;{\text{mod}}\;p}$.


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

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

und wegen ${\displaystyle {a_{0} \choose b_{0}}=0}$ ist auch ${\displaystyle {{\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: ${\displaystyle a_{0}=b_{0}=0\,}$

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

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

Daher ist ${\displaystyle {\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}}}}$

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

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


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

Es gilt ${\displaystyle (\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 ${\displaystyle \beta \equiv b_{0}=0\;{\text{mod}}\;p}$ ist ${\displaystyle (\alpha -\beta )(\alpha -\beta -1)\cdots (\alpha -\beta -a_{0}+1)}$

${\displaystyle \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 ${\displaystyle a_{0}!\,{\alpha \choose \beta }\equiv a_{0}!\,{\alpha -a_{0} \choose \beta }\;{\text{mod}}\;p}$. Kürzt man ${\displaystyle a_{0}!\,}$ heraus, so ist ${\displaystyle {\alpha \choose \beta }\equiv {\alpha -a_{0} \choose \beta }\;{\text{mod}}\;p}$.

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

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