Carmichael-Funktion

Die Carmichael-Funktion λ(n)

Die Carmichael-Funktion λ ist eine zahlentheoretische Funktion, die sehr eng mit der Euler-Funktion φ(n) zusammen hängt. Wie diese hat λ eine tiefe Beziehung zu Primzahlen und zu der Ordnung ganzer Zahlen. Der Name der Funktion geht zurück auf den US-amerikanischen Mathematiker Robert D. Carmichael (1879-1967) (s. auch hier).

Die Definition der Carmichael-Funktion λ: IN → IN ist einigermaßen kompliziert: Ist die Primfaktorzerlegung von n gegeben durch n = p₁^a₁ ... p_k^a_k, so gilt λ(n) = kgV[λ(p₁^a₁), ..., λ(p_k^a_k)], wo

λ(p_i^a_i) =	{	2^{a_i - 2}	wenn p_i = 2 und a_i > 2,
		p_i^{a_i - 1} (p_i - 1)	sonst.

(kgV = kleinstes gemeinsames Vielfaches). Ein Beispiel möge die Formel etwas erläutern: Sei n = 12, mit der Primzahlzerlegung 12 = 2²·3; dann ist λ(12) = kgV[λ(2²), λ(3)], mit λ(2²) = 1 und λ(3) = 2, also λ(12) = 2. Mit entsprechendem Aufwand ermittelt man die folgende Wertetabelle für die ersten natürlichen Zahlen (zum Vergleich sind die Werte der Euler-Funktion φ mit aufgeführt):

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
λ(n)	1	1	2	2	4	2	6	2	6	4	10	2	12	6	4
φ(n)	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8

Eine der Eigenschaften der Carmichael-Funktion, die der Tabelle zu entnehmen ist, lässt sich für allgemein jede natürliche Zahl n beweisen: Der Wert der Carmichael-Funktion λ(n) teilt stets den Wert der Euler-Funktion φ(n), in Symbolen λ(n) | φ(n). Der Wert der Carmichael-Funktion für eine Primzahl p ist vergleichsweise einfach zu ermitteln:

λ(p) = p - 1 (p prim).

(Beachten Sie dass in diesem Fall λ(p) = φ(p).) Z.B. ist λ(7) = 6, oder λ(13) = 12. Ist n das Produkt zweier Primzahlen p und q, n = pq, so gilt λ(pq) = kgV(p-1, q-1). Beispiel: λ(15) = kgV(3-1, 5-1) = 4. Ferner gilt der folgende wichtige Satz.

Satz von Carmichael. Für zwei natürliche teilerfremde Zahlen m, n gilt

m^λ(n) = 1 mod n.

Für festes n ist λ(n) der kleinste Exponent mit dieser Eigenschaft für alle m ∈ IN.

Sie können hier ein Applet starten, das die Euler- und die Carmichael-Funktionswerte berechnet.

Literatur

Friedhelm Padberg: Elementare Zahlentheorie. Spektrum Akademischer Verlag, Heidelberg Berlin 1996
Hans Riesel: Prime Numbers and Computer Methods for Factorization. Birkhäuser Boston Basel Berlin 1994