Formelsammlung
Um die Pseudoprimzahlen zu verstehen, muss man ein paar Dinge wissen.
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}}}
.
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 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)}
.
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}}}