Carmichael-Funktion
Die Carmichael-Funktion aus dem Bereich der Mathematik ist eine zahlentheoretische Funktion, die zu jeder natürlichen Zahl n das kleinste <math>m=:\lambda(n)</math> bestimmt, so dass:
- <math>g^m \equiv 1 \bmod n</math>
für jedes <math>g</math> gilt, das teilerfremd zu <math>n</math> ist. In gruppentheoretischer Sprechweise ist <math>\lambda(n)</math> der Gruppenexponent der (primen) Restklassengruppe <math>(\mathbb Z/n\mathbb Z)^\times</math>.
Die Carmichael-Funktion geht auf den Mathematiker Robert Daniel Carmichael zurück. Sie ist die maximale Periodenlänge des Bruches <math>1/n</math> in seinen {{#if:trim|<math>g</math>-adischen}} Darstellungen und spielt bei Primzahlen und fermatschen Pseudoprimzahlen eine Rolle.
Berechnung
Die Carmichael-Funktion lässt sich nach folgendem Schema berechnen:
- <math>\begin{align}
\lambda(1) &= 1\\ \lambda(2) &= 1\\ \lambda(4) &= 2\\ \lambda(2^k) &= 2^{k-2} \quad \mathrm{f\ddot ur}\ k > 2\\ \lambda(p^k) &= p^{k-1}\cdot(p-1) \quad \mathrm{f\ddot ur}\ p\geq3\ \mathrm{prim},k>0\\ \lambda(p_1^{k_1}p_2^{k_2}\cdot\cdot\cdot p_s^{k_s}) &= \operatorname{kgV}\bigl(\lambda(p_1^{k_1}),\lambda(p_2^{k_2}),...,\lambda(p_s^{k_s})\bigr) \end{align}</math> Dabei stehen die <math>p_{i}</math> für paarweise verschiedene Primzahlen und die <math>k_i</math> für positive ganze Zahlen.
Die folgende Formel kommt zum selben Ergebnis:
Sei <math>m = p_1^{k_1}p_2^{k_2}\cdot\cdot\cdot p_s^{k_s}</math> die Primfaktorzerlegung von <math>m\in\mathbb{N}</math> (mit <math>p_1 = 2</math>, falls <math>m</math> gerade):
- <math>\lambda(m) = \operatorname{kgV}\bigl(\varphi(p_1^{k_1}),\varphi(p_2^{k_2}),...,\varphi(p_s^{k_s})\bigr)</math> falls <math>m \not\equiv 0 \bmod 8</math>
- <math>\lambda(m) = \operatorname{kgV}\bigl(\varphi(p_1^{k_1})/2,\varphi(p_2^{k_2}),...,\varphi(p_s^{k_s})\bigr)</math> falls <math>m \equiv 0 \bmod 8</math>
Dabei bezeichnet <math>\varphi(x)</math> die Eulersche φ-Funktion. Für Potenzen ungerader Primzahlen <math>p</math> gilt <math>\lambda(p^k) = \varphi(p^k)</math>
Beispiel
- <math>\lambda(15) = \lambda(3 \cdot 5) = \operatorname{kgV}\bigl(\varphi(3),\varphi(5)\bigr) = \operatorname{kgV}\bigl(2,4\bigr) = 4</math>
- <math>g^4 \equiv 1 \bmod 15</math> gilt für alle <math>g </math>, 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 <math>\lambda(n)=\varphi(n)</math>, existieren auch Primitivwurzeln modulo <math>n</math>. Im Allgemeinen unterscheiden sich beide Funktionen; <math>\lambda(n)</math> ist jedoch stets ein Teiler von <math>\varphi(n)</math>.
- Eulersche φ-Funktion:
- <math>\varphi(105) = \varphi(3\cdot5\cdot7) = \varphi(3)\cdot\varphi(5)\cdot\varphi(7) = 2\cdot4\cdot6 = 48</math>
- Carmichael-Funktion:
- <math>\lambda(105) = \lambda(3\cdot5\cdot7) = \operatorname{kgV}\bigl(\varphi(3),\varphi(5),\varphi(7)\bigr) = \operatorname{kgV}\bigl(2,4,6\bigr) = 12</math>
Die ersten Werte von <math>\lambda(n)</math> und <math>\varphi(n)</math> bis <math>n=24</math> in Gegenüberstellung – fett gedruckt, wenn verschieden.
| <math>n</math> | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| <math>\lambda(n)</math> | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 2 | 6 | 4 | 10 | 2 | 12 | 6 | 4 | 4 | 16 | 6 | 18 | 4 | 6 | 10 | 22 | 2 |
| <math>\varphi(n)</math> | 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 <math>n </math> das kleinste <math>m = \lambda(n)</math> bestimmt, so dass <math>g^m \equiv 1 \bmod n</math> für jedes <math>g\ </math> gilt, das teilerfremd zu <math>n\ </math> ist, und für jede Carmichael-Zahl <math>c </math> die Differenz <math>c-1\ </math> durch <math>\lambda(c) </math> teilbar ist, folgt aus:
- <math>g^{\lambda(c)} \equiv 1 \bmod c</math>
auch
- <math>g^{c-1} \equiv 1 \bmod c</math>.
Für eine Carmichael-Zahl <math>c </math> ist die Zahl
- <math>d := \tfrac{c-1}{\lambda(c)}</math>
also ganz, und es gilt für alle zu <math>c </math> teilerfremden <math>g</math>
- <math>g^{c-1} = g^{\lambda(c)\cdot d} \equiv 1 \bmod c</math>.
Siehe auch
Weblinks
- {{#if: | {{{author}}} | Eric W. Weisstein }}: Carmichael Function. In: MathWorld (englisch). {{#if: CarmichaelFunction | {{#ifeq: {{#property:P2812}} | CarmichaelFunction | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}