imported>Elrond: reicht auch in dieser Größe. Wer es größer haben will, kann das Bild anklicken.

2023-02-05T17:29:45Z

reicht auch in dieser Größe. Wer es größer haben will, kann das Bild anklicken.

Neue Seite

[[Datei:Carmicheal+Euler-function.png|mini|300px|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)'']]
<span style="white-space:nowrap">Die '''Carmichael-Funktion''' aus dem Bereich</span> 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 [[Gruppentheorie|gruppentheoretischer]] Sprechweise ist <math>\lambda(n)</math> der [[Gruppenexponent]] der [[Prime Restklassengruppe|(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 [[Rationale Zahl#Dezimalbruchentwicklung|{{nowrap|<math>g</math>-adischen}} Darstellungen]] und spielt bei [[Primzahlen]] und [[Fermatsche Pseudoprimzahl|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 [[Primitivwurzel|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.
{| class="wikitable" style="text-align: center;"
|-
! scope="col" | <math>n</math>
! scope="col" | 1
! scope="col" | 2
! scope="col" | 3
! scope="col" | 4
! scope="col" | 5
! scope="col" | 6
! scope="col" | 7
! scope="col" | 8
! scope="col" | 9
! scope="col" | 10
! scope="col" | 11
! scope="col" | 12
! scope="col" | 13
! scope="col" | 14
! scope="col" | 15
! scope="col" | 16
! scope="col" | 17
! scope="col" | 18
! scope="col" | 19
! scope="col" | 20
! scope="col" | 21
! scope="col" | 22
! scope="col" | 23
! scope="col" | 24
|-
! scope="row" | <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'''
|-
! scope="row" | <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 ==
* [[Satz von Carmichael]]

== Weblinks ==
* {{MathWorld |id=CarmichaelFunction |title=Carmichael Function}}

[[Kategorie:Zahlentheoretische Funktion]]

Carmichael-Funktion - Versionsgeschichte

imported>Elrond: reicht auch in dieser Größe. Wer es größer haben will, kann das Bild anklicken.