Carmichael-Funktion

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 $m=:\lambda (n)$ bestimmt, so dass:

$g^m\equiv 1modn$

für jedes $g$ gilt, das teilerfremd zu $n$ ist. In gruppentheoretischer Sprechweise ist $\lambda (n)$ der Gruppenexponent der (primen) Restklassengruppe $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$.

Die Carmichael-Funktion geht auf den Mathematiker Robert Daniel Carmichael zurück. Sie ist die maximale Periodenlänge des Bruches $1/n$ in seinen [[Rationale Zahl#Dezimalbruchentwicklung|Vorlage:Nowrap Darstellungen]] und spielt bei Primzahlen und fermatschen Pseudoprimzahlen eine Rolle.

Berechnung

Die Carmichael-Funktion lässt sich nach folgendem Schema berechnen:

$\begin{array}{cc}\lambda (1)& =1\\ \lambda (2)& =1\\ \lambda (4)& =2\\ \lambda (2^k)& =2^{k-2}\mathrm{f}\ddot{\mathrm{u}}\mathrm{r}k>2\\ \lambda (p^k)& =p^{k-1}\cdot (p-1)\mathrm{f}\ddot{\mathrm{u}}\mathrm{r}p\ge 3\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m},k>0\\ \lambda (p_1^{k_1}{p}_2^{k_2}\cdot \cdot \cdot p_s^{k_s})& =\mathrm{kgV}(\lambda (p_1^{k_1}),\lambda (p_2^{k_2}),...,\lambda (p_s^{k_s}))\end{array}$

Dabei stehen die $p_i$ für paarweise verschiedene Primzahlen und die $k_i$ für positive ganze Zahlen.

Die folgende Formel kommt zum selben Ergebnis:

Sei $m=p_1^{k_1}{p}_2^{k_2}\cdot \cdot \cdot p_s^{k_s}$ die Primfaktorzerlegung von $m\in \mathbb{N}$ (mit $p_1=2$, falls $m$ gerade):

• $\lambda (m)=\mathrm{kgV}(\phi (p_1^{k_1}),\phi (p_2^{k_2}),...,\phi (p_s^{k_s}))$ falls $m\equiv ̸0mod8$
• $\lambda (m)=\mathrm{kgV}(\phi (p_1^{k_1})/2,\phi (p_2^{k_2}),...,\phi (p_s^{k_s}))$ falls $m\equiv 0mod8$

Dabei bezeichnet $\phi (x)$ die Eulersche φ-Funktion. Für Potenzen ungerader Primzahlen $p$ gilt $\lambda (p^k)=\phi (p^k)$

Beispiel

$\lambda (15)=\lambda (3\cdot 5)=\mathrm{kgV}(\phi (3),\phi (5))=\mathrm{kgV}(2,4)=4$

$g^4\equiv 1mod15$ gilt für alle $g$, 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 $\lambda (n)=\phi (n)$, existieren auch Primitivwurzeln modulo $n$. Im Allgemeinen unterscheiden sich beide Funktionen; $\lambda (n)$ ist jedoch stets ein Teiler von $\phi (n)$.

• Eulersche φ-Funktion:

  $\phi (105)=\phi (3\cdot 5\cdot 7)=\phi (3)\cdot \phi (5)\cdot \phi (7)=2\cdot 4\cdot 6=48$

• Carmichael-Funktion:

  $\lambda (105)=\lambda (3\cdot 5\cdot 7)=\mathrm{kgV}(\phi (3),\phi (5),\phi (7))=\mathrm{kgV}(2,4,6)=12$

Die ersten Werte von $\lambda (n)$ und $\phi (n)$ bis $n=24$ in Gegenüberstellung – fett gedruckt, wenn verschieden.

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
$\lambda (n)$	1	1	2	2	4	2	6	2	6	4	10	2	12	6	4	4	16	6	18	4	6	10	22	2
$\phi (n)$	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 $n$ das kleinste $m=\lambda (n)$ bestimmt, so dass $g^m\equiv 1modn$ für jedes $g$ gilt, das teilerfremd zu $n$ ist, und für jede Carmichael-Zahl $c$ die Differenz $c-1$ durch $\lambda (c)$ teilbar ist, folgt aus:

$g^{\lambda (c)}\equiv 1modc$

auch

$g^{c-1}\equiv 1modc$.

Für eine Carmichael-Zahl $c$ ist die Zahl

$d:=\frac{c-1}{\lambda (c)}$

also ganz, und es gilt für alle zu $c$ teilerfremden $g$

$g^{c-1}=g^{\lambda (c)\cdot d}\equiv 1modc$.

Siehe auch

• Satz von Carmichael

Weblinks

• Vorlage:MathWorld