Werte der Carmichael-Funktion λ (schwarz) und der eulerschen φ -Funktion (rot) für die ersten 288 Zahlen. Der Punkt (n , λ(n) ) ist zweifarbig, wenn λ(n) = φ(n) Die Carmichael-Funktion aus dem Bereich der Mathematik ist eine zahlentheoretische Funktion , die zu jeder natürlichen Zahl n das kleinste
m
=:
λ
(
n
)
{\displaystyle m=:\lambda (n)}
g
m
≡
1
mod
n
{\displaystyle g^{m}\equiv 1{\bmod {n}}}
für jedes
g
{\displaystyle g}
teilerfremd zu
n
{\displaystyle n}
gruppentheoretischer Sprechweise ist
λ
(
n
)
{\displaystyle \lambda (n)}
Gruppenexponent der (primen) Restklassengruppe
(
Z
/
n
Z
)
×
{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}
Die Carmichael-Funktion geht auf den Mathematiker Robert Daniel Carmichael zurück.
Sie ist die maximale Periodenlänge des Bruches
1
/
n
{\displaystyle 1/n}
g
{\displaystyle g}
Primzahlen und fermatschen Pseudoprimzahlen eine Rolle.
Die Carmichael-Funktion lässt sich nach folgendem Schema berechnen:
λ
(
1
)
=
1
λ
(
2
)
=
1
λ
(
4
)
=
2
λ
(
2
k
)
=
2
k
−
2
f
u
¨
r
k
>
2
λ
(
p
k
)
=
p
k
−
1
⋅
(
p
−
1
)
f
u
¨
r
p
≥
3
p
r
i
m
,
k
>
0
λ
(
p
1
k
1
p
2
k
2
⋅
⋅
⋅
p
s
k
s
)
=
kgV
(
λ
(
p
1
k
1
)
,
λ
(
p
2
k
2
)
,
.
.
.
,
λ
(
p
s
k
s
)
)
{\displaystyle {\begin{aligned}\lambda (1)&=1\\\lambda (2)&=1\\\lambda (4)&=2\\\lambda (2^{k})&=2^{k-2}\quad \mathrm {f{\ddot {u}}r} \ k>2\\\lambda (p^{k})&=p^{k-1}\cdot (p-1)\quad \mathrm {f{\ddot {u}}r} \ p\geq 3\ \mathrm {prim} ,k>0\\\lambda (p_{1}^{k_{1}}p_{2}^{k_{2}}\cdot \cdot \cdot p_{s}^{k_{s}})&=\operatorname {kgV} {\bigl (}\lambda (p_{1}^{k_{1}}),\lambda (p_{2}^{k_{2}}),...,\lambda (p_{s}^{k_{s}}){\bigr )}\end{aligned}}}
Dabei stehen die
p
i
{\displaystyle p_{i}}
k
i
{\displaystyle k_{i}}
Die folgende Formel kommt zum selben Ergebnis:
Sei
m
=
p
1
k
1
p
2
k
2
⋅
⋅
⋅
p
s
k
s
{\displaystyle m=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdot \cdot \cdot p_{s}^{k_{s}}}
Primfaktorzerlegung von
m
∈
N
{\displaystyle m\in \mathbb {N} }
p
1
=
2
{\displaystyle p_{1}=2}
m
{\displaystyle m}
λ
(
m
)
=
kgV
(
φ
(
p
1
k
1
)
,
φ
(
p
2
k
2
)
,
.
.
.
,
φ
(
p
s
k
s
)
)
{\displaystyle \lambda (m)=\operatorname {kgV} {\bigl (}\varphi (p_{1}^{k_{1}}),\varphi (p_{2}^{k_{2}}),...,\varphi (p_{s}^{k_{s}}){\bigr )}}
m
≢
0
mod
8
{\displaystyle m\not \equiv 0{\bmod {8}}}
λ
(
m
)
=
kgV
(
φ
(
p
1
k
1
)
/
2
,
φ
(
p
2
k
2
)
,
.
.
.
,
φ
(
p
s
k
s
)
)
{\displaystyle \lambda (m)=\operatorname {kgV} {\bigl (}\varphi (p_{1}^{k_{1}})/2,\varphi (p_{2}^{k_{2}}),...,\varphi (p_{s}^{k_{s}}){\bigr )}}
m
≡
0
mod
8
{\displaystyle m\equiv 0{\bmod {8}}}
Dabei bezeichnet
φ
(
x
)
{\displaystyle \varphi (x)}
Eulersche φ-Funktion . Für Potenzen ungerader Primzahlen
p
{\displaystyle p}
λ
(
p
k
)
=
φ
(
p
k
)
{\displaystyle \lambda (p^{k})=\varphi (p^{k})}
λ
(
15
)
=
λ
(
3
⋅
5
)
=
kgV
(
φ
(
3
)
,
φ
(
5
)
)
=
kgV
(
2
,
4
)
=
4
{\displaystyle \lambda (15)=\lambda (3\cdot 5)=\operatorname {kgV} {\bigl (}\varphi (3),\varphi (5){\bigr )}=\operatorname {kgV} {\bigl (}2,4{\bigr )}=4}
g
4
≡
1
mod
1
5
{\displaystyle g^{4}\equiv 1{\bmod {1}}5}
g
{\displaystyle g}
Für die Zahlen Eins, Zwei, Vier, für jede ungerade Primzahlpotenz und für alle Doppelten von ungeraden Primzahlpotenzen sind die Carmichael-Funktion und die Eulersche φ-Funktion identisch. Genau dann, wenn
λ
(
n
)
=
φ
(
n
)
{\displaystyle \lambda (n)=\varphi (n)}
Primitivwurzeln modulo
n
{\displaystyle n}
λ
(
n
)
{\displaystyle \lambda (n)}
φ
(
n
)
{\displaystyle \varphi (n)}
Eulersche φ-Funktion:
φ
(
105
)
=
φ
(
3
⋅
5
⋅
7
)
=
φ
(
3
)
⋅
φ
(
5
)
⋅
φ
(
7
)
=
2
⋅
4
⋅
6
=
48
{\displaystyle \varphi (105)=\varphi (3\cdot 5\cdot 7)=\varphi (3)\cdot \varphi (5)\cdot \varphi (7)=2\cdot 4\cdot 6=48}
Carmichael-Funktion:
λ
(
105
)
=
λ
(
3
⋅
5
⋅
7
)
=
kgV
(
φ
(
3
)
,
φ
(
5
)
,
φ
(
7
)
)
=
kgV
(
2
,
4
,
6
)
=
12
{\displaystyle \lambda (105)=\lambda (3\cdot 5\cdot 7)=\operatorname {kgV} {\bigl (}\varphi (3),\varphi (5),\varphi (7){\bigr )}=\operatorname {kgV} {\bigl (}2,4,6{\bigr )}=12}
Die ersten Werte von
λ
(
n
)
{\displaystyle \lambda (n)}
φ
(
n
)
{\displaystyle \varphi (n)}
n
=
24
{\displaystyle n=24}
n
{\displaystyle n}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
λ
(
n
)
{\displaystyle \lambda (n)}
1
1
2
2
4
2
6
2 6
4
10
2 12
6
4 4 16
6
18
4 6 10
22
2
φ
(
n
)
{\displaystyle \varphi (n)}
1
1
2
2
4
2
6
4 6
4
10
4 12
6
8 8 16
6
18
8 12 10
22
8
Da die Carmichael-Funktion zu jeder natürlichen Zahl
n
{\displaystyle n}
m
=
λ
(
n
)
{\displaystyle m=\lambda (n)}
g
m
≡
1
mod
n
{\displaystyle g^{m}\equiv 1{\bmod {n}}}
g
{\displaystyle g\ }
n
{\displaystyle n\ }
Carmichael-Zahl
c
{\displaystyle c}
c
−
1
{\displaystyle c-1\ }
λ
(
c
)
{\displaystyle \lambda (c)}
g
λ
(
c
)
≡
1
mod
c
{\displaystyle g^{\lambda (c)}\equiv 1{\bmod {c}}}
auch
g
c
−
1
≡
1
mod
c
{\displaystyle g^{c-1}\equiv 1{\bmod {c}}}
Für eine Carmichael-Zahl
c
{\displaystyle c}
d
:=
c
−
1
λ
(
c
)
{\displaystyle d:={\tfrac {c-1}{\lambda (c)}}}
also ganz, und es gilt für alle zu
c
{\displaystyle c}
g
{\displaystyle g}
g
c
−
1
=
g
λ
(
c
)
⋅
d
≡
1
mod
c
{\displaystyle g^{c-1}=g^{\lambda (c)\cdot d}\equiv 1{\bmod {c}}}
