Carmichael-Funktion

Werte der Carmichael-Funktion λ (schwarz) und der eulerschen φ-Funktion (rot) für die ersten 356 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:

{\displaystyle g^{m}\equiv 1{\bmod {n}}}

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 g-adischen Darstellungen und spielt bei Primzahlen und fermatschen Pseudoprimzahlen eine Rolle.

Berechnung

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

{\displaystyle {\begin{aligned}\lambda (1)&=1\\\lambda (2)&=1\\\lambda (4)&=2\\\lambda (2^{k})&=2^{k-2}\quad \mathrm {f{\ddot {u}}r} \ k>2\\\lambda (p^{k})&=p^{k-1}\cdot (p-1)\quad \mathrm {f{\ddot {u}}r} \ p\geq 3\ \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{aligned}}}

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):

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

Beispiel

{\displaystyle \lambda (15)=\lambda (3\cdot 5)=\operatorname {kgV} {\bigl (}\varphi (3),\varphi (5){\bigr )}=\operatorname {kgV} {\bigl (}2,4{\bigr )}=4}
{\displaystyle g^{4}\equiv 1{\bmod {1}}5} 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)=\varphi (n), existieren auch Primitivwurzeln modulo n. Im Allgemeinen unterscheiden sich beide Funktionen; \lambda (n) ist jedoch stets ein Teiler von \varphi(n).

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 {\displaystyle g^{m}\equiv 1{\bmod {n}}} für jedes g\ gilt, das teilerfremd zu n\ ist, und für jede Carmichael-Zahl c die Differenz c-1\ durch {\displaystyle \lambda (c)} teilbar ist, folgt aus:

{\displaystyle g^{\lambda (c)}\equiv 1{\bmod {c}}}

auch

{\displaystyle g^{c-1}\equiv 1{\bmod {c}}}.

Für eine Carmichael-Zahl c ist die Zahl

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

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

{\displaystyle g^{c-1}=g^{\lambda (c)\cdot d}\equiv 1{\bmod {c}}}.
Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung: Jena, den: 17.03. 2020