Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Carmichael-Funktion aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Carmichael-Funktion

Die Carmichael-Funktion aus dem Bereich der Mathematik ist eine zahlentheoretische Funktion, die zu jeder natürlichen Zahl n, das kleinste $m=\backslash lambda(n)$ bestimmt, so dass
:$a^m\; \backslash equiv\; 1\; \backslash 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 $\backslash lambda(st)=\backslash lambda(s)\backslash lambda(t)$. In gruppentheoretischer Sprache ist $\backslash lambda(n)$ der Exponent der Restklassengruppe $(\backslash mathbb\; Z/n\backslash mathbb\; Z)^\backslash times$.

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

Berechnung

Die Carmichael-Funktion wird nach folgendem Schema berechnet:
*$\backslash lambda(1)\; =\; 1$
*$\backslash lambda(2)\; =\; 1,\backslash quad\backslash lambda(4)=\backslash lambda(8)=2,\backslash quad\backslash lambda(2^r)\; =\; 2^\{r-2\}\backslash \; \backslash mathrm\{f\backslash ddot\; ur\}\backslash \; r\backslash geq2$
*$\backslash lambda(p^r)\; =\; p^\{r-1\}\backslash cdot(p-1)\backslash quad\backslash mathrm\{f\backslash ddot\; ur\}\backslash \; p>2\backslash \; \backslash mathrm\{prim\},r\backslash geq1$
*$\backslash lambda(p\_1^\{r\_1\}p\_2^\{r\_2\}\backslash cdot\backslash cdot\backslash cdot\; p\_s^\{r\_s\})\; =\; \backslash operatorname\{kgV\}\backslash \{\backslash lambda(p\_1^\{r\_1\}),\backslash lambda(p\_2^\{r\_2\}),...,\backslash lambda(p\_s^\{r\_s\})\backslash \}$

Dabei stehen die $p\_\{i\}$ für Primzahlen und die $r\_i$ für nichtnegative ganze Zahlen.Alternativ kann man $\backslash lambda(x)$ auch folgendermaßen definieren:
Sei $m\; =\; p\_1^\{r\_1\}p\_2^\{r\_2\}\backslash cdot\backslash cdot\backslash cdot\; p\_s^\{r\_s\}$ die Primfaktorzerlegung von $m\backslash in\backslash mathbb\{N\}$ (mit $p\_1\; =\; 2$, falls $m$ gerade):
*$\backslash lambda(m)\; =\; \backslash operatorname\{kgV\}\backslash \{\backslash varphi(p\_1^\{r\_1\}),\backslash varphi(p\_2^\{r\_2\}),...,\backslash varphi(p\_s^\{r\_s\})\backslash \}$ falls $m\; \backslash not\; =\; 0\; \backslash quad\backslash operatorname\{mod\}\backslash quad\; 8$
*$\backslash lambda(m)\; =\; \backslash operatorname\{kgV\}\backslash \{\backslash frac\{\backslash varphi(p\_1^\{r\_1\})\}\{2\},\backslash varphi(p\_2^\{r\_2\}),...,\backslash varphi(p\_s^\{r\_s\})\backslash \}$ falls $m\; =\; 0\; \backslash quad\backslash operatorname\{mod\}\backslash quad\; 8$
Dabei bezeichnet $\backslash phi(x)$ die eulersche φ-Funktion.

Beispiel

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

:$a^4\; \backslash equiv\; 1\; \backslash 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\backslash$, das kleinste $m\; =\; \backslash lambda(n)$ bestimmt, so dass $a^m\; \backslash equiv\; 1\; \backslash mod\; n$ für jedes $a\backslash$ gilt, das teilerfremd zu $n\backslash$ ist, und $c-1\backslash$ zu jeder Carmichael-Zahl $c\backslash$ durch $m\; =\; \backslash lambda(c)$ teilbar ist, folgt aus:
:$a^\{\backslash lambda(c)\}\; \backslash equiv\; 1\; \backslash mod\; c$
auch
:$a^\{c-1\}\; \backslash equiv\; 1\; \backslash mod\; c$Für jede Carmichael-Zahl $c\backslash$ gilt $a^\{c-1\}\; =\; a^\{\backslash lambda(c)\backslash 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; $\backslash lambda(n)$ ist jedoch stets ein Teiler von $\backslash phi(n)$.

*eulersche φ-Funktion:
::$\backslash varphi(105)\; =\; \backslash varphi(3\backslash cdot5\backslash cdot7)\; =\; \backslash varphi(3)\backslash cdot\backslash varphi(5)\backslash cdot\backslash varphi(7)\; =\; 2\backslash cdot4\backslash cdot6\; =\; 48$
*Carmichael-Funktion:
::$\backslash lambda(105)\; =\; \backslash lambda(3\backslash cdot5\backslash cdot7)\; =\; \backslash operatorname\{kgV\}\backslash \{\backslash lambda(3),\backslash lambda(5)\backslash lambda(7)\backslash \}\; =\; \backslash operatorname\{kgV\}\backslash \{2,4,6\backslash \}\; =\; 12$

       VIDEO-NEWS UND ANGEBOTE