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 bestimmt, so dass:

für jedes gilt, das teilerfremd zu n ist. In gruppentheoretischer Sprechweise ist der Gruppenexponent der Restklassengruppe .

Die Carmichael-Funktion geht auf den Mathematiker Robert Daniel Carmichael zurück. Eine Bedeutung spielt die Funktion bei Primzahlen und fermatschen Pseudoprimzahlen.

Berechnung[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

gilt für alle a, die teilerfremd zur Zahl 15 sind.

Die Carmichael-Funktion und die Carmichael-Zahl[Bearbeiten | Quelltext bearbeiten]

Da die Carmichael-Funktion zu jeder natürlichen Zahl das kleinste bestimmt, so dass für jedes gilt, das teilerfremd zu ist, und zu jeder Carmichael-Zahl durch teilbar ist, folgt aus:

auch

Zu jeder Carmichael-Zahl gibt es ein , so dass für jedes gilt . Man nehme .

Die Carmichael-Funktion und die eulersche φ-Funktion[Bearbeiten | Quelltext 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 , existieren auch Primitivwurzeln modulo . Im Allgemeinen unterscheiden sich beide Funktionen; ist jedoch stets ein Teiler von .

  • Eulersche φ-Funktion:
  • Carmichael-Funktion: