Pseudoprimzahlen: Formelsammlung

Formelsammlung

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

Für jede Primzahl${\displaystyle \ p\ }$und jede natürliche Zahl ${\displaystyle a\geq 2\ }$ gilt

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

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

• ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$.

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:

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

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

Die Eulersche φ-Funktion wird wie folgt berechnet:

• ${\displaystyle \varphi (1)=1}$
• ${\displaystyle \varphi (p^{r})=p^{r-1}\cdot (p-1)\quad {\text{für }}p{\text{ prim}},r\geq 1}$
• ${\displaystyle \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)}$

• ${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}\quad \forall \ a,n\in \mathbb {N} \ {\text{mit}}\ \gcd(a,n)=1}$

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

Die Carmichael-Funktion wird wie folgt berechnet:

• ${\displaystyle \lambda (1)=1,\ }$
• ${\displaystyle \lambda (2)=1,}$
• ${\displaystyle \lambda (4)=2,}$
• ${\displaystyle \lambda (2^{r})=2^{r-2}{\text{ für }}r>2}$
• ${\displaystyle \lambda (p^{r})=p^{r-1}\cdot (p-1)\quad {\text{für }}p>2\ {\text{prim}},r\geq 1}$
• ${\displaystyle \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 beiden allgemeinen Lucas-Folgen ${\displaystyle U(P,Q)\ }$ und ${\displaystyle V(P,Q)\ }$, deren jeweilige einzelne Glieder

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

${\displaystyle V_{n}(P,Q)=a^{n}+b^{n}\ }$

sind, lassen sich aus der quadratischen Gleichung

${\displaystyle x^{2}-Px+Q=0\ }$

ableiten, deren beide Lösungen

${\displaystyle a={\frac {P+{\sqrt {P^{2}-4Q}}}{2}}\ }$ und ${\displaystyle \ 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 ${\displaystyle n\ }$ eine Primzahl ist, dann teilt sie${\displaystyle \ V_{n}(P,Q)-P\ }$ für alle Folgen, deren ${\displaystyle P>0\ }$ und ${\displaystyle Q=\pm 1}$ sind.

Wenn ${\displaystyle n\ }$ eine zusammengesetze Zahl ist, und trotzdem ${\displaystyle V_{n}(P,Q)-P\ }$ teilt, ist ${\displaystyle n\ }$ eine Pseudoprimzahl zu ${\displaystyle V_{n}(P,Q)}$.

Einige Beziehungen zwischen den Folgegliedern der allgemeinen Lucas-Folgen, der Fibonacci-Zahlen ${\displaystyle F_{n}=U_{n}(1,-1)}$ und der Lucas-Zahlen ${\displaystyle L_{n}=V_{n}(1,-1)}$:^[1]

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

1. ↑ en:w:Lucas_sequence#Other_relations