Die Carmichael Funktion aus dem Bereich der Mathematik ist eine zahlentheoretische Funktion die zu jeder naturlichen Zahl n das kleinste m l n displaystyle m lambda n bestimmt so dass Werte der Carmichael Funktion l schwarz und der eulerschen f Funktion rot fur die ersten 288 Zahlen Der Punkt n l n ist zweifarbig wenn l n f n g m 1 mod n displaystyle g m equiv 1 bmod n fur jedes g displaystyle g gilt das teilerfremd zu n displaystyle n ist In gruppentheoretischer Sprechweise ist l n displaystyle lambda n der Gruppenexponent der primen Restklassengruppe Z n Z displaystyle mathbb Z n mathbb Z times Die Carmichael Funktion geht auf den Mathematiker Robert Daniel Carmichael zuruck Sie ist die maximale Periodenlange des Bruches 1 n displaystyle 1 n in seinen g displaystyle g adischen Darstellungen und spielt bei Primzahlen und fermatschen Pseudoprimzahlen eine Rolle Inhaltsverzeichnis 1 Berechnung 2 Beispiel 3 Die Carmichael Funktion und die eulersche f Funktion 4 Die Carmichael Funktion und die Carmichael Zahl 5 Siehe auch 6 WeblinksBerechnung BearbeitenDie Carmichael Funktion lasst sich nach folgendem Schema berechnen l 1 1 l 2 1 l 4 2 l 2 k 2 k 2 f u r k gt 2 l p k p k 1 p 1 f u r p 3 p r i m k gt 0 l p 1 k 1 p 2 k 2 p s k s kgV l p 1 k 1 l p 2 k 2 l p s k s displaystyle begin aligned lambda 1 amp 1 lambda 2 amp 1 lambda 4 amp 2 lambda 2 k amp 2 k 2 quad mathrm f ddot u r k gt 2 lambda p k amp p k 1 cdot p 1 quad mathrm f ddot u r p geq 3 mathrm prim k gt 0 lambda p 1 k 1 p 2 k 2 cdot cdot cdot p s k s amp operatorname kgV bigl lambda p 1 k 1 lambda p 2 k 2 lambda p s k s bigr end aligned nbsp Dabei stehen die p i displaystyle p i nbsp fur paarweise verschiedene Primzahlen und die k i displaystyle k i nbsp fur positive ganze Zahlen Die folgende Formel kommt zum selben Ergebnis Sei m p 1 k 1 p 2 k 2 p s k s displaystyle m p 1 k 1 p 2 k 2 cdot cdot cdot p s k s nbsp die Primfaktorzerlegung von m N displaystyle m in mathbb N nbsp mit p 1 2 displaystyle p 1 2 nbsp falls m displaystyle m nbsp gerade l m kgV f p 1 k 1 f p 2 k 2 f p s k s displaystyle lambda m operatorname kgV bigl varphi p 1 k 1 varphi p 2 k 2 varphi p s k s bigr nbsp falls m 0 mod 8 displaystyle m not equiv 0 bmod 8 nbsp l m kgV f p 1 k 1 2 f p 2 k 2 f p s k s displaystyle lambda m operatorname kgV bigl varphi p 1 k 1 2 varphi p 2 k 2 varphi p s k s bigr nbsp falls m 0 mod 8 displaystyle m equiv 0 bmod 8 nbsp Dabei bezeichnet f x displaystyle varphi x nbsp die Eulersche f Funktion Fur Potenzen ungerader Primzahlen p displaystyle p nbsp gilt l p k f p k displaystyle lambda p k varphi p k nbsp Beispiel Bearbeitenl 15 l 3 5 kgV f 3 f 5 kgV 2 4 4 displaystyle lambda 15 lambda 3 cdot 5 operatorname kgV bigl varphi 3 varphi 5 bigr operatorname kgV bigl 2 4 bigr 4 nbsp g 4 1 mod 1 5 displaystyle g 4 equiv 1 bmod 1 5 nbsp gilt fur alle g displaystyle g nbsp die teilerfremd zur Zahl 15 sind Die Carmichael Funktion und die eulersche f Funktion BearbeitenFur die Zahlen Eins Zwei Vier fur jede ungerade Primzahlpotenz und fur alle Doppelten von ungeraden Primzahlpotenzen sind die Carmichael Funktion und die Eulersche f Funktion identisch Genau dann wenn l n f n displaystyle lambda n varphi n nbsp existieren auch Primitivwurzeln modulo n displaystyle n nbsp Im Allgemeinen unterscheiden sich beide Funktionen l n displaystyle lambda n nbsp ist jedoch stets ein Teiler von f n displaystyle varphi n nbsp Eulersche f Funktion f 105 f 3 5 7 f 3 f 5 f 7 2 4 6 48 displaystyle varphi 105 varphi 3 cdot 5 cdot 7 varphi 3 cdot varphi 5 cdot varphi 7 2 cdot 4 cdot 6 48 nbsp Carmichael Funktion l 105 l 3 5 7 kgV f 3 f 5 f 7 kgV 2 4 6 12 displaystyle lambda 105 lambda 3 cdot 5 cdot 7 operatorname kgV bigl varphi 3 varphi 5 varphi 7 bigr operatorname kgV bigl 2 4 6 bigr 12 nbsp Die ersten Werte von l n displaystyle lambda n nbsp und f n displaystyle varphi n nbsp bis n 24 displaystyle n 24 nbsp in Gegenuberstellung fett gedruckt wenn verschieden n displaystyle n nbsp 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24l n displaystyle lambda n nbsp 1 1 2 2 4 2 6 2 6 4 10 2 12 6 4 4 16 6 18 4 6 10 22 2f n displaystyle varphi n nbsp 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8 12 10 22 8Die Carmichael Funktion und die Carmichael Zahl BearbeitenDa die Carmichael Funktion zu jeder naturlichen Zahl n displaystyle n nbsp das kleinste m l n displaystyle m lambda n nbsp bestimmt so dass g m 1 mod n displaystyle g m equiv 1 bmod n nbsp fur jedes g displaystyle g nbsp gilt das teilerfremd zu n displaystyle n nbsp ist und fur jede Carmichael Zahl c displaystyle c nbsp die Differenz c 1 displaystyle c 1 nbsp durch l c displaystyle lambda c nbsp teilbar ist folgt aus g l c 1 mod c displaystyle g lambda c equiv 1 bmod c nbsp auch g c 1 1 mod c displaystyle g c 1 equiv 1 bmod c nbsp Fur eine Carmichael Zahl c displaystyle c nbsp ist die Zahl d c 1 l c displaystyle d tfrac c 1 lambda c nbsp also ganz und es gilt fur alle zu c displaystyle c nbsp teilerfremden g displaystyle g nbsp g c 1 g l c d 1 mod c displaystyle g c 1 g lambda c cdot d equiv 1 bmod c nbsp Siehe auch BearbeitenSatz von CarmichaelWeblinks BearbeitenEric W Weisstein Carmichael Function In MathWorld englisch Abgerufen von https de wikipedia org w index php title Carmichael Funktion amp oldid 230587047
