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