Die Carmichael-Funktion λ(n)
english

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 = p1a1 ... pkak, so gilt λ(n) = kgV[λ(p1a1), ..., λ(pkak)], wo

λ(piai) = { 2ai - 2   wenn pi = 2 und ai > 2,
piai - 1 (pi - 1)   sonst.

(kgV = kleinstes gemeinsames Vielfaches). Ein Beispiel möge die Formel etwas erläutern: Sei n = 12, mit der Primzahlzerlegung 12 = 22·3; dann ist λ(12) = kgV[λ(22), λ(3)], mit λ(22) = 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 AppletDuke starten, das die Euler- und die Carmichael-Funktionswerte berechnet.

Literatur


© de Vries 2002-2009 federstrich english