Carmichael-Funktion

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

$a^m \equiv 1 \mod n$

für jedes a gilt, das teilerfremd zu n ist. In gruppentheoretischer Sprache ist λ(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 λ(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₁ = 2, falls m gerade):

• $\lambda(m) = \operatorname{kgV}\{\phi(p_1^{k_1}),\phi(p_2^{k_2}),...,\phi(p_s^{k_s})\}$ falls $m \not = 0 \mod 8$
• $\lambda(m) = \operatorname{kgV}\{\phi(p_1^{k_1})/2,\phi(p_2^{k_2}),...,\phi(p_s^{k_s})\}$ falls $m = 0 \mod 8$

Dabei bezeichnet φ(x) die Eulersche φ-Funktion. Für Potenzen ungerader Primzahlen p gilt ϕ(p^k) = λ(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 = λ(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 = λ(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 λ(n) = φ(n), existieren auch Primitivwurzeln modulo n. Im Allgemeinen unterscheiden sich beide Funktionen; λ(n) ist jedoch stets ein Teiler von ϕ(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}\{\lambda(3),\lambda(5)\lambda(7)\} = \operatorname{kgV}\{2,4,6\} = 12$