Pseudoprimzahlen: Formelsammlung

Pseudoprimzahlen

Anhänge
Geschichte
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen

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\geq 2\$ gilt

• $a^{p}\equiv a{\pmod {p}}\$.

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

• $a^{p-1}\equiv 1{\pmod {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{\pmod {n}}$
• $(b\cdot n-1)\equiv n-1\equiv -1{\pmod {n}}$.

Eulersche φ-Funktion

Die Eulersche φ-Funktion $\varphi (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 $\varphi (n)$ auch ein Vielfaches der Carmichael-Funktion $\lambda (n)\$ ist, gilt $a^{\varphi (n)}\equiv 1{\pmod {n}}$ für jedes zu $n\$ teilerfremde $a\$.

Die Eulersche φ-Funktion wird wie folgt berechnet:

• $\varphi (1)=1$
• $\varphi (p^{r})=p^{r-1}\cdot (p-1)\quad {\text{für }}p{\text{ prim}},r\geq 1$
• $\varphi (p_{1}^{r_{1}}\cdot p_{2}^{r_{2}}\cdot \dots \cdot p_{s}^{r_{s}})=\varphi (p_{1}^{r_{1}})\cdot \varphi (p_{2}^{r_{2}})\cdot \dots \cdot \varphi (p_{s}^{r_{s}})=\prod _{i=1}^{s}p_{i}^{r_{i}-1}(p_{i}-1)$

Satz von Euler

• $a^{\varphi (n)}\equiv 1{\pmod {n}}\quad \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{\pmod {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)\quad {\text{für }}p>2\ {\text{prim}},r\geq 1$
• $\lambda (p_{1}^{r_{1}}p_{2}^{r_{2}}\cdot \cdot \cdot p_{s}^{r_{s}})=\operatorname {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}{r|l}{\text{Allgemein}}&(P,Q)=(1,-1)\\\hline (P^{2}-4Q)U_{n}={V_{n+1}-QV_{n-1}}=2V_{n+1}-PV_{n}&5F_{n}={L_{n+1}+L_{n-1}}=2L_{n+1}-L_{n}\\V_{n}=U_{n+1}-QU_{n-1}=2U_{n+1}-PU_{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}-QU_{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}=DU_{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}-DU_{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}=DQ^{n-1}&L_{n}^{2}-L_{n-1}L_{n+1}=5(-1)^{n-1}\\DU_{n}=V_{n+1}-QV_{n-1}&F_{n}={\frac {L_{n+1}+L_{n-1}}{5}}\\V_{m+n}={\frac {V_{m}V_{n}+DU_{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}={n \choose 1}P^{n-1}+{n \choose 3}P^{n-3}D+\cdots &2^{n-1}F_{n}={n \choose 1}+5{n \choose 3}+\cdots \\2^{n-1}V_{n}=P^{n}+{n \choose 2}P^{n-2}D+{n \choose 4}P^{n-4}D^{2}+\cdots &2^{n-1}L_{n}=1+5{n \choose 2}+5^{2}{n \choose 4}+\cdots \end{array}}$