- 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:
für jedes a gilt, das teilerfremd zu n ist. In gruppentheoretischer Sprache ist λ(n) der Exponent der Restklassengruppe
.
Die Carmichael-Funktion geht auf den Mathematiker Robert Daniel Carmichael zurück. Eine Bedeutung spielt die Funktion bei Primzahlen und fermatschen Pseudoprimzahlen.
Inhaltsverzeichnis
Berechnung
Die Carmichael-Funktion wird nach folgendem Schema berechnet:
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}" border="0">
Dabei stehen die pi für paarweise verschiedene Primzahlen und die ki für positive ganze Zahlen.
Alternativ kann man λ(x) auch folgendermaßen definieren: Seidie Primfaktorzerlegung von
(mit p1 = 2, falls m gerade):
falls
falls
Dabei bezeichnet φ(x) die Eulersche φ-Funktion. Für Potenzen ungerader Primzahlen p gilt ϕ(pk) = λ(pk)
Beispiel
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
, das kleinste m = λ(n) bestimmt, so dass
für jedes
gilt, das teilerfremd zu
ist, und
zu jeder Carmichael-Zahl
durch m = λ(c) teilbar ist, folgt aus:
auch
Für jede Carmichael-Zahlgilt
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:
- Carmichael-Funktion:
Wikimedia Foundation.