Formelsammlung Mathematik: Kongruenzrechnung

Kleiner fermatscher Satz

$a^{p-1}\equiv 1\text{mod}pp|a$

Satz von Euler-Fermat

$a^{\phi (n)}\equiv 1\text{mod}na\perp n$

Satz von Wilson

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

Verallgemeinerung des Satzes von Wilson durch Gauß

Es sei $P(n):=\prod _{\genfrac{}{}{0ex}{}{1<k<n}{(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$.

Eisensteins Kongruenz über den Fermat-Quotienten

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

Kongruenz von Babbage

$(\genfrac{}{}{0ex}{}{2p-1}{p-1})\equiv 1\text{mod}{p}^{2}p\in {\mathbb{P}}^{\ge 3}$

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

[Summe von Kehrwerten]

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

[Kongruenz von Babbage, Exponent drei]

$(\genfrac{}{}{0ex}{}{2p-1}{p-1})\equiv 1\text{mod}{p}^{3}p\in {\mathbb{P}}^{\ge 5}$

Kongruenz von Ljunggren

$(\genfrac{}{}{0ex}{}{np}{mp})\equiv (\genfrac{}{}{0ex}{}{n}{m})\text{mod}{p}^{3}p\in {\mathbb{P}}^{\ge 5}$

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

$(\genfrac{}{}{0ex}{}{(p-1)/2}{(p-1)/4})\equiv 2ap(\genfrac{}{}{0ex}{}{(p-1)/2}{(p-1)/4})\equiv (1+\frac{2^{p-1}-1}{2})(2a-\frac{p}{2a})\text{mod}{p}^2$

Kongruenz von Morley

$(-1{)}^{\frac{p-1}{2}}(\genfrac{}{}{0ex}{}{p-1}{(p-1)/2})\equiv 4^{p-1}\text{mod}{p}^{3}p\in {\mathbb{P}}^{\ge 5}$

Kongruenz von Jacobi

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

Pepin Test

$3^{\frac{1}{2}(F_n-1)}\equiv -1\text{mod}{F}_n⟺F_n\in \mathbb{P},F_n=2^{2^n}+1$

2n≡2m mod 2^k

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

Touchards Kongruenz

$B_{n+p^m}\equiv m{B}_n+B_{n+1}\text{mod}p$

Kummersche Kongruenz

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

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

[Binomialkoeffizient und p-adische Darstellung]

Ist p eine Primzahl und sind $𝒂=(a_0,...,a_r),𝒃=(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 $(\genfrac{}{}{0ex}{}{\alpha }{\beta })\equiv (\genfrac{}{}{0ex}{}{𝒂}{𝒃})\text{mod}p$, wobei $(\genfrac{}{}{0ex}{}{𝒂}{𝒃})=(\genfrac{}{}{0ex}{}{a_0}{b_0})(\genfrac{}{}{0ex}{}{a_1}{b_1})\cdots (\genfrac{}{}{0ex}{}{a_r}{b_r})$ ist.