Carmichael-Funktion
# Carmichael-Funktion

Die Carmichael-Funktion aus dem Bereich der Mathematik ist eine zahlentheoretische Funktion, die zu jeder natürlichen Zahl n das kleinste $m=:\lambda (n)$ bestimmt, so dass:

    $g^{m}\equiv 1{\bmod {n}}$

für jedes $g$ gilt, das teilerfremd zu $n$ ist. In gruppentheoretischer Sprechweise ist $\lambda (n)$ der Gruppenexponent der (primen) Restklassengruppe $(\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$ in seinen $g$-adischen Darstellungen und spielt bei Primzahlen und fermatschen Pseudoprimzahlen eine Rolle.

## Berechnung

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

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

Die folgende Formel kommt zum selben Ergebnis:

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

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

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

## Beispiel

    $\lambda (15)=\lambda (3\cdot 5)=\operatorname {kgV} {\bigl\varphi (3),\varphi (5){\bigr )}=\operatorname {kgV} {\bigl2,4{\bigr )}=4$
    $g^{4}\equiv 1{\bmod {1}}5$ gilt für alle $g$, die teilerfremd zur Zahl 15 sind.

## Die Carmichael-Funktion und die eulersche φ-Funktion

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

* Eulersche φ-Funktion:

    $\varphi (105)=\varphi (3\cdot 5\cdot 7)=\varphi (3)\cdot \varphi (5)\cdot \varphi (7)=2\cdot 4\cdot 6=48$
* Carmichael-Funktion:

    $\lambda (105)=\lambda (3\cdot 5\cdot 7)=\operatorname {kgV} {\bigl\varphi (3),\varphi (5),\varphi (7){\bigr )}=\operatorname {kgV} {\bigl2,4,6{\bigr )}=12$

Die ersten Werte von $\lambda (n)$ und $\varphi (n)$ bis $n=24$ in Gegenüberstellung – fett gedruckt, wenn verschieden.

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

## Die Carmichael-Funktion und die Carmichael-Zahl

Da die Carmichael-Funktion zu jeder natürlichen Zahl $n$ das kleinste $m=\lambda (n)$ bestimmt, so dass $g^{m}\equiv 1{\bmod {n}}$ für jedes $g\$ gilt, das teilerfremd zu $n\$ ist, und für jede Carmichael-Zahl $c$ die Differenz $c-1\$ durch $\lambda (c)$ teilbar ist, folgt aus:

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

auch

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

Für eine Carmichael-Zahl $c$ ist die Zahl

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

also ganz, und es gilt für alle zu $c$ teilerfremden $g$

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