Carmichael-Funktion

Die Carmichael-Funktion lässt sich nach folgendem Schema berechnen:

${\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 ${\displaystyle p_{i}}$ für paarweise verschiedene Primzahlen und die ${\displaystyle k_{i}}$ für positive ganze Zahlen.

Die folgende Formel kommt zum selben Ergebnis:

Sei ${\displaystyle m=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdot \cdot \cdot p_{s}^{k_{s}}}$ die Primfaktorzerlegung von ${\displaystyle m\in \mathbb {N} }$ (mit ${\displaystyle p_{1}=2}$, falls ${\displaystyle m}$ gerade):

• ${\displaystyle \lambda (m)=\operatorname {kgV} {\bigl (}\varphi (p_{1}^{k_{1}}),\varphi (p_{2}^{k_{2}}),...,\varphi (p_{s}^{k_{s}}){\bigr )}}$ falls ${\displaystyle m\not \equiv 0{\bmod {8}}}$
• ${\displaystyle \lambda (m)=\operatorname {kgV} {\bigl (}\varphi (p_{1}^{k_{1}})/2,\varphi (p_{2}^{k_{2}}),...,\varphi (p_{s}^{k_{s}}){\bigr )}}$ falls ${\displaystyle m\equiv 0{\bmod {8}}}$

Dabei bezeichnet ${\displaystyle \varphi (x)}$ die Eulersche φ-Funktion. Für Potenzen ungerader Primzahlen ${\displaystyle p}$ gilt ${\displaystyle \lambda (p^{k})=\varphi (p^{k})}$

${\displaystyle \lambda (15)=\lambda (3\cdot 5)=\operatorname {kgV} {\bigl (}\varphi (3),\varphi (5){\bigr )}=\operatorname {kgV} {\bigl (}2,4{\bigr )}=4}$

${\displaystyle g^{4}\equiv 1{\bmod {1}}5}$ gilt für alle ${\displaystyle g}$, die teilerfremd zur Zahl 15 sind.

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 ${\displaystyle \lambda (n)=\varphi (n)}$, existieren auch Primitivwurzeln modulo ${\displaystyle n}$. Im Allgemeinen unterscheiden sich beide Funktionen; ${\displaystyle \lambda (n)}$ ist jedoch stets ein Teiler von ${\displaystyle \varphi (n)}$.

• Eulersche φ-Funktion:

  ${\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:

  ${\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 ${\displaystyle \lambda (n)}$ und ${\displaystyle \varphi (n)}$ bis ${\displaystyle n=24}$ in Gegenüberstellung – fett gedruckt, wenn verschieden.

${\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
${\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
${\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 ${\displaystyle n}$ das kleinste ${\displaystyle m=\lambda (n)}$ bestimmt, so dass ${\displaystyle g^{m}\equiv 1{\bmod {n}}}$ für jedes ${\displaystyle g\ }$ gilt, das teilerfremd zu ${\displaystyle n\ }$ ist, und für jede Carmichael-Zahl ${\displaystyle c}$ die Differenz ${\displaystyle c-1\ }$ durch ${\displaystyle \lambda (c)}$ teilbar ist, folgt aus:

${\displaystyle g^{\lambda (c)}\equiv 1{\bmod {c}}}$

auch

${\displaystyle g^{c-1}\equiv 1{\bmod {c}}}$.

Für eine Carmichael-Zahl ${\displaystyle c}$ ist die Zahl

${\displaystyle d:={\tfrac {c-1}{\lambda (c)}}}$

also ganz, und es gilt für alle zu ${\displaystyle c}$ teilerfremden ${\displaystyle g}$

${\displaystyle g^{c-1}=g^{\lambda (c)\cdot d}\equiv 1{\bmod {c}}}$.

• Satz von Carmichael

• Eric W. Weisstein: Carmichael Function. In: MathWorld (englisch).