Carmichael-Funktion

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 Sprechweise ist \lambda(n) der Gruppenexponent 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[Bearbeiten]

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

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


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}\{\varphi(p_1^{k_1}),\varphi(p_2^{k_2}),...,\varphi(p_s^{k_s})\} falls m \not\equiv 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 \equiv 0 \mod 8

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

Beispiel[Bearbeiten]

\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[Bearbeiten]

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

Zu jeder Carmichael-Zahl c\ gibt es ein d\ , so dass für jedes a\ gilt a^{c-1} = a^{\lambda(c)\cdot d}. Man nehme d := \tfrac{c-1}{\lambda(c)}.

Die Carmichael-Funktion und die eulersche φ-Funktion[Bearbeiten]

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