Das Kefk Network Wiki befindet sich im Testbetrieb.

Carmichael-Funktion

Aus Kefk.

Die Carmichael-Funktion aus dem Bereich der Mathematik ist eine zahlentheoretische Funktion, die zu jeder natürlichen Zahl n, das kleinste $m = λ(n)$ bestimmt, so dass

$a^m \equiv 1 \mod n$

für jedes a gilt, das teilerfremd zu n ist. Sie ist jedoch keine zahlentheoretische Funktion im engeren Sinne, d.h. es gilt für teilerfremde $s, t$ nicht notwendigerweise $λ(s t) = λ(s)λ(t)$ . In gruppentheoretischer Sprache ist $λ(n)$ der Exponent der Restklassengruppe $(\mathbb Z/n\mathbb Z)^\times$ .

Die Carmichael-Funktion geht auf den Mathematiker Robert Daniel Carmichael zurück. Eine Bedeutung spielt die Funktion bei Primzahlen und fermatschen Pseudoprimzahlen.

Inhaltsverzeichnis

1 Berechnung
2 Beispiel
3 Die Carmichael-Funktion und die Carmichael-Zahl
4 Die Carmichael-Funktion und die eulersche φ-Funktion

Berechnung

Die Carmichael-Funktion wird nach folgendem Schema berechnet:

$λ(1) = 1$
$\lambda(2) = 1,\quad\lambda(4)=\lambda(8)=2,\quad\lambda(2^r) = 2^{r-2}\ \mathrm{f\ddot ur}\ r\geq2$
$\lambda(p^r) = p^{r-1}\cdot(p-1)\quad\mathrm{f\ddot ur}\ p>2\ \mathrm{prim},r\geq1$
$\lambda(p_1^{r_1}p_2^{r_2}\cdot\cdot\cdot p_s^{r_s}) = \operatorname{kgV}\{\lambda(p_1^{r_1}),\lambda(p_2^{r_2}),...,\lambda(p_s^{r_s})\}$

Dabei stehen die $p i$ für Primzahlen und die $r i$ für nichtnegative ganze Zahlen.

Alternativ kann man $λ(x)$ auch folgendermaßen definieren: Sei $m = p_1^{r_1}p_2^{r_2}\cdot\cdot\cdot p_s^{r_s}$ die Primfaktorzerlegung von $m\in\mathbb{N}$ (mit $p 1 = 2$ , falls $m$ gerade):

$\lambda(m) = \operatorname{kgV}\{\varphi(p_1^{r_1}),\varphi(p_2^{r_2}),...,\varphi(p_s^{r_s})\}$ falls $m \not = 0 \quad\operatorname{mod}\quad 8$
$\lambda(m) = \operatorname{kgV}\{\frac{\varphi(p_1^{r_1})}{2},\varphi(p_2^{r_2}),...,\varphi(p_s^{r_s})\}$ falls $m = 0 \quad\operatorname{mod}\quad 8$

Dabei bezeichnet $φ(x)$ die eulersche φ-Funktion.

Beispiel

$\lambda(15) = \lambda(3*5) = \operatorname{kgV}\{\lambda(3),\lambda(5)\} = \operatorname{kgV}\{2,4\} = 4$

$a^4 \equiv 1 \mod 15$ gilt für alle a, die teilerfremd zur Zahl 15 sind.

Die Carmichael-Funktion und die Carmichael-Zahl

Da die Carmichael-Funktion zu jeder natürlichen Zahl $n\$ , das kleinste $m = λ(n)$ bestimmt, so dass $a^m \equiv 1 \mod n$ für jedes $a\$ gilt, das teilerfremd zu $n\$ ist, und $c-1\$ zu jeder Carmichael-Zahl $c\$ durch $m = λ(c)$ teilbar ist, folgt aus:

$a^{\lambda(c)} \equiv 1 \mod c$

auch

$a^{c-1} \equiv 1 \mod c$

Für jede Carmichael-Zahl $c\$ gilt $a^{c-1} = a^{\lambda(c)\cdot d}$

Die Carmichael-Funktion und die eulersche φ-Funktion

Für die Eins und jede ungerade Primzahlpotenz sind die Carmichael-Funktion und die eulersche φ-Funktion identisch. Im Allgemeinen unterscheiden sich beide Funktionen; $λ(n)$ ist jedoch stets ein Teiler von $φ(n)$ .