Carmichael-Funktion

zahlentheoretische Funktion

Die Carmichael-Funktion aus dem Bereich der Mathematik ist eine zahlentheoretische Funktion, die zu jeder natürlichen Zahl n das kleinste bestimmt, so dass:

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)

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

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
 
  gilt für alle  , die teilerfremd zur Zahl 15 sind.

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

Bearbeiten

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

Bearbeiten
Bearbeiten