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

$a^{m}\equiv 1\mod n$

für jedes a gilt, das teilerfremd zu n ist. Sie ist jedoch keine zahlentheoretische Funktion im engeren Sinne, d.h. es gilt für teilerfremde $s,t$ nicht notwendigerweise $\lambda (st)=\lambda (s)\lambda (t)$. In gruppentheoretischer Sprache ist $\lambda (n)$ der Exponent der Restklassengruppe $(\mathbb {Z} /n\mathbb {Z} )^{\times }$.

Die Carmichael-Funktion geht auf den Mathematiker Robert Daniel Carmichael zurück. Eine Bedeutung spielt die Funktion bei Primzahlen und fermatschen Pseudoprimzahlen.

Berechnung

Die Carmichael-Funktion wird nach folgendem Schema berechnet:

• $\lambda (1)=1$
• $\lambda (2)=1,\quad \lambda (4)=\lambda (8)=2,\quad \lambda (2^{r})=2^{r-2}\ \mathrm {f{\ddot {u}}r} \ r\geq 2$
• $\lambda (p^{r})=p^{r-1}\cdot (p-1)\quad \mathrm {f{\ddot {u}}r} \ p>2\ \mathrm {prim} ,r\geq 1$
• $\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}}),...,\lambda (p_{s}^{r_{s}})\}$

Dabei stehen die $p_{i}$ für Primzahlen und die $r_{i}$ für nichtnegative ganze Zahlen.

Alternativ kann man $\lambda (x)$ auch folgendermaßen definieren: Sei Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle m = p_1^{r_1}p_2^{r_2}\cdot\cdot\cdot p_s^{r_s}} die Primfaktorzerlegung von $m\in \mathbb {N}$ (mit $p_{1}=2$, falls $m$ gerade):

• $\lambda (m)=\operatorname {kgV} \{\phi (p_{1}^{r_{1}}),\phi (p_{2}^{r_{2}}),...,\phi (p_{s}^{r_{s}})\}$ falls $m\not =0\quad \operatorname {mod} \quad 8$
• $\lambda (m)=\operatorname {kgV} \{{\frac {\phi (p_{1}^{r_{1}})}{2}},\phi (p_{2}^{r_{2}}),...,\phi (p_{s}^{r_{s}})\}$ falls $m=0\quad \operatorname {mod} \quad 8$

Dabei bezeichnet $\phi (x)$ die Euler'sche Phi-Funktion.

Beispiel

$\lambda (15)=\lambda (3*5)=\operatorname {kgV} \{\lambda (3),\lambda (5)\}=\operatorname {kgV} \{2,4\}=4$

$a^{4}\equiv 1\mod 15$ gilt für alle a, die teilerfremd zur Zahl 15 sind.

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 $a^{m}\equiv 1\mod n$ für jedes $a\$ gilt, das teilerfremd zu $n\$ ist, und $c-1\$ zu jeder Carmichael-Zahl $c\$ durch $m=\lambda (c)$ teilbar ist, folgt aus:

$a^{\lambda (c)}\equiv 1\mod c$

auch

$a^{c-1}\equiv 1\mod c$

Für jede Carmichael-Zahl $c\$ gilt $a^{c-1}=a^{\lambda (c)\cdot d}$

Die Carmichael-Funktion und die eulersche φ-Funktion

Für die Eins und jede ungerade Primzahlpotenz sind die Carmichael-Funktion und die eulersche φ-Funktion identisch. Im Allgemeinen unterscheiden sich beide Funktionen; $\lambda (n)$ ist jedoch stets ein Teiler von $\phi (n)$.

• eulersche φ-Funktion:

$\phi (105)=\phi (3\cdot 5\cdot 7)=\phi (3)\cdot \phi (5)\cdot \phi (7)=2\cdot 4\cdot 6=48$

• Carmichael-Funktion:

$\lambda (105)=\lambda (3\cdot 5\cdot 7)=\operatorname {kgV} \{\lambda (3),\lambda (5)\lambda (7)\}=\operatorname {kgV} \{2,4,6\}=12$