Formelsammlung
Um die Pseudoprimzahlen zu verstehen, muss man ein paar Dinge wissen.
Der kleine Fermatsche Satz
Bearbeiten
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
⋅
n
+
m
)
≡
n
+
m
≡
m
(
mod
n
)
{\displaystyle (b\cdot n+m)\equiv n+m\equiv m{\pmod {n}}}
(
b
⋅
n
−
1
)
≡
n
−
1
≡
−
1
(
mod
n
)
{\displaystyle (b\cdot n-1)\equiv n-1\equiv -1{\pmod {n}}}
.
Eulersche φ-Funktion
Bearbeiten
Der Funktionswert der Carmichael-Funktion
λ
(
n
)
{\displaystyle \lambda (n)\ }
einer natürlichen Zahl
n
{\displaystyle n\ }
ist die kleinste natürliche Zahl, mit der für jede zu
n
{\displaystyle n\ }
teilerfremde Basis
a
{\displaystyle a\ }
mit
a
>
1
{\displaystyle a>1\ }
gilt:
a
λ
(
n
)
≡
1
(
mod
n
)
{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}
.
Die Carmichael-Funktion wird wie folgt berechnet:
λ
(
1
)
=
1
,
{\displaystyle \lambda (1)=1,\ }
λ
(
2
)
=
1
,
{\displaystyle \lambda (2)=1,}
λ
(
4
)
=
2
,
{\displaystyle \lambda (4)=2,}
λ
(
2
r
)
=
2
r
−
2
für
r
>
2
{\displaystyle \lambda (2^{r})=2^{r-2}{\text{ für }}r>2}
λ
(
p
r
)
=
p
r
−
1
⋅
(
p
−
1
)
für
p
>
2
prim
,
r
≥
1
{\displaystyle \lambda (p^{r})=p^{r-1}\cdot (p-1)\quad {\text{für }}p>2\ {\text{prim}},r\geq 1}
λ
(
p
1
r
1
p
2
r
2
⋅
⋅
⋅
p
s
r
s
)
=
kgV
{
λ
(
p
1
r
1
)
,
λ
(
p
2
r
2
)
,
…
,
λ
(
p
s
r
s
)
}
{\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 allgemeinen Lucas-Folgen
Bearbeiten
Die beiden allgemeinen Lucas-Folgen
U
(
P
,
Q
)
{\displaystyle U(P,Q)\ }
und
V
(
P
,
Q
)
{\displaystyle V(P,Q)\ }
, deren jeweilige einzelne Glieder
U
n
(
P
,
Q
)
=
a
n
−
b
n
a
−
b
{\displaystyle U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}}
und
V
n
(
P
,
Q
)
=
a
n
+
b
n
{\displaystyle V_{n}(P,Q)=a^{n}+b^{n}\ }
sind, lassen sich aus der quadratischen Gleichung
x
2
−
P
x
+
Q
=
0
{\displaystyle x^{2}-Px+Q=0\ }
ableiten, deren beide Lösungen
a
=
P
+
P
2
−
4
Q
2
{\displaystyle a={\frac {P+{\sqrt {P^{2}-4Q}}}{2}}\ }
und
b
=
P
−
P
2
−
4
Q
2
{\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
n
{\displaystyle n\ }
eine Primzahl ist, dann teilt sie
V
n
(
P
,
Q
)
−
P
{\displaystyle \ V_{n}(P,Q)-P\ }
für alle Folgen, deren
P
>
0
{\displaystyle P>0\ }
und
Q
=
±
1
{\displaystyle Q=\pm 1}
sind.
Wenn
n
{\displaystyle n\ }
eine zusammengesetze Zahl ist, und trotzdem
V
n
(
P
,
Q
)
−
P
{\displaystyle V_{n}(P,Q)-P\ }
teilt, ist
n
{\displaystyle n\ }
eine Pseudoprimzahl zu
V
n
(
P
,
Q
)
{\displaystyle V_{n}(P,Q)}
.
Beziehungen zwischen den Folgegliedern
Bearbeiten
Einige Beziehungen zwischen den Folgegliedern der allgemeinen Lucas-Folgen, der Fibonacci-Zahlen
F
n
=
U
n
(
1
,
−
1
)
{\displaystyle F_{n}=U_{n}(1,-1)}
und der Lucas-Zahlen
L
n
=
V
n
(
1
,
−
1
)
{\displaystyle L_{n}=V_{n}(1,-1)}
:[1]
Allgemein
(
P
,
Q
)
=
(
1
,
−
1
)
(
P
2
−
4
Q
)
U
n
=
V
n
+
1
−
Q
V
n
−
1
=
2
V
n
+
1
−
P
V
n
5
F
n
=
L
n
+
1
+
L
n
−
1
=
2
L
n
+
1
−
L
n
V
n
=
U
n
+
1
−
Q
U
n
−
1
=
2
U
n
+
1
−
P
U
n
L
n
=
F
n
+
1
+
F
n
−
1
=
2
F
n
+
1
−
F
n
U
2
n
=
U
n
V
n
F
2
n
=
F
n
L
n
V
2
n
=
V
n
2
−
2
Q
n
L
2
n
=
L
n
2
−
2
(
−
1
)
n
U
m
+
n
=
U
n
U
m
+
1
−
Q
U
m
U
n
−
1
=
U
m
V
n
+
U
n
V
m
2
F
m
+
n
=
F
n
F
m
+
1
+
F
m
F
n
−
1
=
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
=
5
F
m
F
n
+
(
−
1
)
n
L
m
−
n
V
n
2
−
D
U
n
2
=
4
Q
n
L
n
2
−
5
F
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
=
L
n
+
1
+
L
n
−
1
5
V
m
+
n
=
V
m
V
n
+
D
U
m
U
n
2
L
m
+
n
=
L
m
L
n
+
5
F
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
1
)
P
n
−
1
+
(
n
3
)
P
n
−
3
D
+
⋯
2
n
−
1
F
n
=
(
n
1
)
+
5
(
n
3
)
+
⋯
2
n
−
1
V
n
=
P
n
+
(
n
2
)
P
n
−
2
D
+
(
n
4
)
P
n
−
4
D
2
+
⋯
2
n
−
1
L
n
=
1
+
5
(
n
2
)
+
5
2
(
n
4
)
+
⋯
{\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}}}