Carmichael fonksiyonu

sayı teorisi içinde, bir pozitif tamsayı n nin Carmichael fonksiyonu ${\displaystyle \lambda (n)}$ ifadesi, daha küçük pozitif tamsayı m olarak tanımlanır böylece

${\displaystyle a^{m}\equiv 1{\pmod {n}}}$

her tamsayı a için bu n e eşasaldır. Başka bir değişle, in daha cebirsel terimler içinde, bu tamsayıların modul n çarpım grubunun üstel tanımıdır .Carmichael fonksiyonu ayrıca indirgenmiş totient fonksiyonu olarak bilinr veya en az evrensel üs işlevi, ve bazen ayrıca ${\displaystyle \psi (n)}$ denir.

${\displaystyle \lambda }$ (OEIS'de A002322 dizisi) ın ilk 26 değeri ${\displaystyle \varphi }$ Euler'in totient fonksiyonuyla karşılaştırılırsa:

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26
${\displaystyle \lambda (n)}$	1	1	2	2	4	2	6	2	6	4	10	2	12	6	4	4	16	6	18	4	6	10	22	2	20	12
${\displaystyle \varphi (n)}$	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8	12	10	22	8	20	12

Sayısal örnekler

7² = 49 ≡ 1 (mod 8) çünkü 7 ve 8 eşasal (burada enbüyük ortak bölen eşit 1'dir; bunda ortak çarpanlar yok) ve the value of Carmichael's fonksiyonu değeri 8'de 2'dir. Euler's totient fonksiyonu is 4 de 8 çünkü burada are 4 sayısından daha az dır ve to 8 (1, 3, 5, ve 7)'ya eşasaldır. oysa 7⁴ = 2401 ≡ 1 (mod 8) bu doğrudur, olarak Euler's teoremi ile gösterilir,dördüncü güç 7 yükselterek Carmichael fonksiyonunu 7 karesine eşit belirtmek gereksiz çünkü 1 (mod 8)dir. 2'den daha fazla üstlere 7 yetiştirilmesi döngüsü 7, 1, 7, 1, tekrar ....^[1]

Carmichael teoremi

Bir tek asalın bir gücü için, Bir tek asal iki güç, ve 2 ve 4 için, λ(n) Euler totient φ(n)'ye eşittir; for powers of 2'ninkuvvetleri için 4'den daha büyük o Euler totient'in tek yarımına eşittir:

${\displaystyle \lambda (n)={\begin{cases}\;\;\varphi (n)&{\mbox{if }}n=2,3,4,5,7,9,11,13,17,19,23,25,27,\dots \\{\tfrac {1}{2}}\varphi (n)&{\text{if }}n=8,16,32,64,\dots \end{cases}}}$

Euler'in fonksiyonu asal kuvvetler için ile verilir

${\displaystyle \varphi (p^{k})=p^{k-1}(p-1).\;}$

aritmetiğin temel teoremi ile herhangi n > 1 bir eşsiz yol içinde yazılabilir

${\displaystyle n=p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{\omega (n)}^{a_{\omega (n)}}}$

burada p₁ < p₂ < ... < p_ω asaldır ve a_i > 0. (n = 1 boş çarpıma karşı gelir.)

Genel için n, λ(n) is her asal kuvvet çarpanlarının λ'nın enküçük ortak katıdır:

${\displaystyle \lambda (n)=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{\omega (n)}^{a_{\omega (n)}})].}$

Carmichaelin teoreminde eğer a nye eşasal durumunda,ise

${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}},}$

burada ${\displaystyle \lambda }$ Carmichael fonksiyonu yukardaki tanımdır. Diğer bir değişle, Bu formüllerin doğruluğunu iddiası herhangi modul n'in ilkel kökleri veÇinli kalan teoremi dikkate alarak sağlanabilir.

sonuçların hiyerarşisi

Since λ(n) divides φ(n), Euler's totient function, the Carmichael function is a stronger result than the classical Euler's theorem. Clearly Carmichael's theorem is related to Euler's theorem, because the exponent of a finite abelian group must divide the order of the group, by elementary group theory. The two functions differ already in small cases: λ(15) = 4 while φ(15) = 8 (see Şablon:OEIS2C for the associated n).

Fermat'ın küçük teoremi n bir asal sayı p içindeki Euler teoremi'nin özel durumudur . Carmichael'in teoremi için bir asal p aynı sonucu verir,çünkü bu sıra için konu içindeki grup bir siklik gruptur ve hem de p − 1 için üsteldir .

Carmichael fonksiyonunun özellikleri

Bölünebilirlik

${\displaystyle a|b\Rightarrow \lambda (a)|\lambda (b)}$

Düzen

tüm pozitif tamsayılar için $a$ ve $b$ şunlara uyar

${\displaystyle \lambda (\mathrm {lcm} (a,b))=\mathrm {lcm} (\lambda (a),\lambda (b))}$ .

Bu bir Carmichael fonksiyonunun indirgenmiş tanımının acil kanıtıdır .

Birimin ilkel m-inci kökleri

Diyelimki $a$ ve ${\displaystyle n}$ eşasal olsun ve Diyelimki ${\displaystyle m}$ enküçük üstel ile ${\displaystyle a^{m}\equiv 1{\pmod {n}}}$ olsun, bunlar gözönüne alındığında

${\displaystyle m|\lambda (n)}$ .

Bu, birimin ilkel kökleriin sırası ${\displaystyle n}$ modül tamsayıların halkası içinde ${\displaystyle \lambda (n)}$'in bölenleridir.

Üstel döngü uzunluğu

Bir sayı ${\displaystyle n}$ için asal çarpan altında ${\displaystyle x_{max}}$'un maksimum asal üsteli ise tüm $a$ için (${\displaystyle n}$'ya eş-asal olmayan içerik) ve tüm ${\displaystyle k\geq x_{max}}$,

${\displaystyle a^{k}\equiv a^{k+\lambda (n)}{\pmod {n}}}$

Özel olarak, for kareserbest ${\displaystyle n}$ (${\displaystyle x_{max}=1}$),tüm $a$ için

${\displaystyle a\equiv a^{\lambda (n)+1}{\pmod {n}}}$

Ortalama ve tipik değer

Herhangi x > 16 ve bir B sabiti için:

${\displaystyle {\frac {1}{x}}\sum _{n\leq x}\lambda (n)={\frac {x}{\ln x}}e^{B(1+o(1))\ln \ln x/(\ln \ln \ln x)}}$.^[2][3]

Burada

${\displaystyle B=e^{-\gamma }\prod _{p}\left({1-{\frac {1}{(p-1)^{2}(p+1)}}}\right)\approx 0.34537\ .}$

Tüm sayılar N ve o(N) hariç tüm n ≤ N pozitif tamsayılar:

${\displaystyle \lambda (n)=n/(\ln n)^{\ln \ln \ln n+A+o(1)}\,}$

burada A bir sabittir,^[3][4]

${\displaystyle A=-1+\sum _{p}{\frac {\log p}{(p-1)^{2}}}\approx 0.2269688\ .}$

Alt sınır

Herhangi yeterince büyük sayı N için ve herhangi ${\displaystyle \Delta \geq (\ln \ln N)^{3}}$ için, burada en çok

${\displaystyle Ne^{-0.69(\Delta \ln \Delta )^{1/3}}}$

pozitif tamsayılar ${\displaystyle n\leq N}$ böylece ${\displaystyle \lambda (n)\leq ne^{-\Delta }}$.^[5]

pozitif tamsayıların ${\displaystyle n_{1}<n_{2}<n_{3}<\cdots }$ herhangi dizisi ,herhangi sabit ${\displaystyle 0<c<1/\ln 2}$, ve herhangi yeterince büyük i olsun:

${\displaystyle \lambda (n_{i})>(\ln n_{i})^{c\ln \ln \ln n_{i}}}$.^[6][7]

Küçük değerler

bir c sabiti ve herhangi yeterince büyük pozitif A için, burada bir tamsayı var ${\displaystyle n>A}$ böylece ${\displaystyle \lambda (n)<(\ln A)^{c\ln \ln \ln A}}$.^[7] Daha ötesi, n formundur

${\displaystyle n=\prod _{(q-1)|m{\text{ ve }}q{\text{ asaldır}}}q}$

bazıları için kare-serbest tamsayı ${\displaystyle m<(\ln A)^{c\ln \ln \ln A}}$.^[6]

Ayrıca bakınız

• Carmichael sayıları

Notlar

1. http://www25.brinkster.com/denshade/totient.html
2. Theorem 3 in Erdös (1991)
3. Sándor & Crstici (2004) p.194
4. Theorem 2 in Erdös (1991)
5. Theorem 5 in Friedlander (2001)
6. Theorem 1 in Erdös 1991
7. Sándor & Crstici (2004) p.193

Kaynakça

• Erdős, Paul; Pomerance, Carl; Schmutz, Eric (1991). "Carmichael's lambda function". Acta Arithmetica 58: 363–385. ISSN 0065-1036. MR 1121092. Zbl 0734.11047. 
• Friedlander, John B.; Pomerance, Carl; Shparlinski, Igor E. (2001). "Period of the power generator and small values of the Carmichael function". Mathematics of Computation 70 (236): 1591–1605,1803–1806. ISSN 0025-5718. MR 1836921. Zbl 1029.11043. 
• Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. s. 193–195. ISBN 1-4020-2546-7. Zbl 1079.11001.