Pseudoprimzahlen: Formelsammlung

Formelsammlung

Um die Pseudoprimzahlen zu verstehen, muss man ein paar Dinge wissen.

Der kleine Fermatsche Satz

Für jede Primzahl$p$und jede natürliche Zahl $a\ge 2$ gilt

• $a^p\equiv a(\mathrm{mod}p)$.

Für jede Primzahl $p>2$ und jede zu $p$ teilerfremde natürliche Zahl $a\ge 2$ gilt

• $a^{p-1}\equiv 1(\mathrm{mod}p)$.

Kongruenz

Zwei Zahlen, die bei Division durch den gleichen Divisor den gleichen Modulo zurückliefern, sind zueinander kongruent. Bei Addition von ganzzahligen Vielfachen des Divisors bleibt die Kongruenz erhalten:

• $(b\cdot n+m)\equiv n+m\equiv m(\mathrm{mod}n)$
• $(b\cdot n-1)\equiv n-1\equiv -1(\mathrm{mod}n)$.

Eulersche φ-Funktion

Die Eulersche φ-Funktion $\phi (n)$ gibt zu jeder natürlichen Zahl $n$ die Anzahl der zu $n$ teilerfremden Zahlen, die nicht größer als $n$ sind, an. Da die Eulersche φ-Funktion $\phi (n)$ auch ein Vielfaches der Carmichael-Funktion $\lambda (n)$ ist, gilt $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$ für jedes zu $n$ teilerfremde $a$.

Die Eulersche φ-Funktion wird wie folgt berechnet:

• $\phi (1)=1$
• $\phi (p^r)=p^{r-1}\cdot (p-1)\text{für }p\text{ prim},r\ge 1$
• $\phi (p_1^{r_1}\cdot p_2^{r_2}\cdot \dots \cdot p_s^{r_s})=\phi (p_1^{r_1})\cdot \phi (p_2^{r_2})\cdot \dots \cdot \phi (p_s^{r_s})=\prod _{i=1}^s{p}_i^{r_i-1}(p_i-1)$

Satz von Euler

• $a^{\phi (n)}\equiv 1(\mathrm{mod}n)\mathrm{\forall }a,n\in \mathbb{N}\text{mit}\gcd (a,n)=1$

Carmichael-Funktion

Der Funktionswert der Carmichael-Funktion $\lambda (n)$ einer natürlichen Zahl $n$ ist die kleinste natürliche Zahl, mit der für jede zu $n$ teilerfremde Basis $a$ mit $a>1$ gilt: $a^{\lambda (n)}\equiv 1(\mathrm{mod}n)$.

Die Carmichael-Funktion wird wie folgt berechnet:

• $\lambda (1)=1,$
• $\lambda (2)=1,$
• $\lambda (4)=2,$
• $\lambda (2^r)=2^{r-2}\text{ für }r>2$
• $\lambda (p^r)=p^{r-1}\cdot (p-1)\text{für }p>2\text{prim},r\ge 1$
• $\lambda (p_1^{r_1}{p}_2^{r_2}\cdot \cdot \cdot p_s^{r_s})=\mathrm{kgV}\{\lambda (p_1^{r_1}),\lambda (p_2^{r_2}),\dots ,\lambda (p_s^{r_s})\}$

Die allgemeinen Lucas-Folgen

Die beiden allgemeinen Lucas-Folgen $U(P,Q)$ und $V(P,Q)$, deren jeweilige einzelne Glieder

$U_n(P,Q)=\frac{a^n-b^n}{a-b}$ und

$V_n(P,Q)=a^n+b^n$

sind, lassen sich aus der quadratischen Gleichung

$x^2-Px+Q=0$

ableiten, deren beide Lösungen

$a=\frac{P+\sqrt{P^2-4Q}}{2}$ und $b=\frac{P-\sqrt{P^2-4Q}}{2}$ sind.

Zwischen den Allgemeinen Lucas-Folgen und den Primzahlen gibt es einen Zusammenhang: Wenn die natürliche Zahl $n$ eine Primzahl ist, dann teilt sie$V_n(P,Q)-P$ für alle Folgen, deren $P>0$ und $Q=\pm 1$ sind.

Wenn $n$ eine zusammengesetze Zahl ist, und trotzdem $V_n(P,Q)-P$ teilt, ist $n$ eine Pseudoprimzahl zu $V_n(P,Q)$.

Beziehungen zwischen den Folgegliedern

Einige Beziehungen zwischen den Folgegliedern der allgemeinen Lucas-Folgen, der Fibonacci-Zahlen $F_n=U_n(1,-1)$ und der Lucas-Zahlen $L_n=V_n(1,-1)$:

$\begin{array}{cc}\text{Allgemein}& (P,Q)=(1,-1)\\ (P^2-4Q)U_n=V_{n+1}-Q{V}_{n-1}=2V_{n+1}-P{V}_n& 5F_n=L_{n+1}+L_{n-1}=2L_{n+1}-L_n\\ V_n=U_{n+1}-Q{U}_{n-1}=2U_{n+1}-P{U}_n& L_n=F_{n+1}+F_{n-1}=2F_{n+1}-F_n\\ U_{2n}=U_n{V}_n& F_{2n}=F_n{L}_n\\ V_{2n}=V_n^2-2Q^n& L_{2n}=L_n^2-2(-1{)}^n\\ U_{m+n}=U_n{U}_{m+1}-Q{U}_m{U}_{n-1}=\frac{U_m{V}_n+U_n{V}_m}{2}& F_{m+n}=F_n{F}_{m+1}+F_m{F}_{n-1}=\frac{F_m{L}_n+F_n{L}_m}{2}\\ V_{m+n}=V_m{V}_n-Q^n{V}_{m-n}=D{U}_m{U}_n+Q^n{V}_{m-n}& L_{m+n}=L_m{L}_n-(-1{)}^n{L}_{m-n}=5F_m{F}_n+(-1{)}^n{L}_{m-n}\\ V_n^2-D{U}_n^2=4Q^n& L_n^2-5F_n^2=4(-1{)}^n\\ U_n^2-U_{n-1}{U}_{n+1}=Q^{n-1}& F_n^2-F_{n-1}{F}_{n+1}=(-1{)}^{n-1}\\ V_n^2-V_{n-1}{V}_{n+1}=D{Q}^{n-1}& L_n^2-L_{n-1}{L}_{n+1}=5(-1{)}^{n-1}\\ D{U}_n=V_{n+1}-Q{V}_{n-1}& F_n=\frac{L_{n+1}+L_{n-1}}{5}\\ V_{m+n}=\frac{V_m{V}_n+D{U}_m{U}_n}{2}& L_{m+n}=\frac{L_m{L}_n+5F_m{F}_n}{2}\\ U_{m+n}=U_m{V}_n-Q^n{U}_{m-n}& F_{n+m}=F_m{L}_n-(-1{)}^n{F}_{m-n}\\ 2^{n-1}{U}_n=(\genfrac{}{}{0ex}{}{n}{1})P^{n-1}+(\genfrac{}{}{0ex}{}{n}{3})P^{n-3}D+\cdots & 2^{n-1}{F}_n=(\genfrac{}{}{0ex}{}{n}{1})+5(\genfrac{}{}{0ex}{}{n}{3})+\cdots \\ 2^{n-1}{V}_n=P^n+(\genfrac{}{}{0ex}{}{n}{2})P^{n-2}D+(\genfrac{}{}{0ex}{}{n}{4})P^{n-4}{D}^2+\cdots & 2^{n-1}{L}_n=1+5(\genfrac{}{}{0ex}{}{n}{2})+5^2(\genfrac{}{}{0ex}{}{n}{4})+\cdots \end{array}$