mini|300px|Werte der Carmichael-Funktion λ (schwarz) und der eulerschen φ-Funktion (rot) für die ersten 288 Zahlen. Der Punkt (n, λ(n)) ist zweifarbig, wenn λ(n) = φ(n) Die Carmichael-Funktion aus dem Bereich der Mathematik ist eine zahlentheoretische Funktion, die zu jeder natürlichen Zahl n das kleinste bestimmt, so dass:
für jedes gilt, das teilerfremd zu ist. In gruppentheoretischer Sprechweise ist der Gruppenexponent der (primen) Restklassengruppe .
Die Carmichael-Funktion geht auf den Mathematiker Robert Daniel Carmichael zurück. Sie ist die maximale Periodenlänge des Bruches in seinen Darstellungen und spielt bei Primzahlen und fermatschen Pseudoprimzahlen eine Rolle.
Berechnung
Die Carmichael-Funktion lässt sich nach folgendem Schema berechnen:
Dabei stehen die für paarweise verschiedene Primzahlen und die für positive ganze Zahlen.
Die folgende Formel kommt zum selben Ergebnis:
Sei die Primfaktorzerlegung von (mit , falls gerade): falls falls Dabei bezeichnet die Eulersche φ-Funktion. Für Potenzen ungerader Primzahlen gilt
Beispiel
gilt für alle , die teilerfremd zur Zahl 15 sind.
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 , existieren auch Primitivwurzeln modulo . Im Allgemeinen unterscheiden sich beide Funktionen; ist jedoch stets ein Teiler von .
Eulersche φ-Funktion:
Carmichael-Funktion:
Die ersten Werte von und bis in Gegenüberstellung – fett gedruckt, wenn verschieden. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 1 2 2 4 2 6 2 6 4 10 2 12 6 4 4 16 6 18 4 6 10 22 2 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8 12 10 22 8
Die Carmichael-Funktion und die Carmichael-Zahl Da die Carmichael-Funktion zu jeder natürlichen Zahl das kleinste bestimmt, so dass für jedes gilt, das teilerfremd zu ist, und für jede Carmichael-Zahl die Differenz durch teilbar ist, folgt aus:
auch . Für eine Carmichael-Zahl ist die Zahl
also ganz, und es gilt für alle zu teilerfremden .
Siehe auch Satz von Carmichael
Weblinks
Kategorie:Zahlentheoretische Funktion