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. 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:

$\begin{align} \lambda(1) &= 1\\ \lambda(2) &= 1\\ \lambda(4) &= 2\\ \lambda(2^k) &= 2^{k-2} \quad \mathrm{f\ddot ur}\ k > 2\\ \lambda(p^k) &= p^{k-1}\cdot(p-1) \quad \mathrm{f\ddot ur}\ p\geq3\ \mathrm{prim},k>0\\ \lambda(p_1^{k_1}p_2^{k_2}\cdot\cdot\cdot p_s^{k_s}) &= \operatorname{kgV}\{\lambda(p_1^{k_1}),\lambda(p_2^{k_2}),...,\lambda(p_s^{k_s})\} \end{align}$

Dabei stehen die $p_{i}$ für paarweise verschiedene Primzahlen und die $k_i$ für positive ganze Zahlen.

Alternativ kann man $\lambda(x)$ auch folgendermaßen definieren: 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}\{\varphi(p_1^{k_1}),\varphi(p_2^{k_2}),...,\varphi(p_s^{k_s})\}$ falls $m \not = 0 \mod 8$
• $\lambda(m) = \operatorname{kgV}\{\varphi(p_1^{k_1})/2,\varphi(p_2^{k_2}),...,\varphi(p_s^{k_s})\}$ falls $m = 0 \mod 8$

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

Beispiel

$\lambda(15) = \lambda(3 \cdot 5) = \operatorname{kgV}\{\varphi(3),\varphi(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 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\cdot5\cdot7) = \varphi(3)\cdot\varphi(5)\cdot\varphi(7) = 2\cdot4\cdot6 = 48$

• Carmichael-Funktion:

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