Carmichael-Funktion

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 -adischen 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