Carmichael fonksiyonu

Vikipedi, özgür ansiklopedi
Gezinti kısmına atla Arama kısmına atla

Sayı teorisi içinde, bir pozitif tamsayı n nin Carmichael fonksiyonu ifadesi, daha küçük pozitif tamsayı m olarak tanımlanır böylece

her tamsayı a için bu n e eşasaldır. Başka bir deyiş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 denir.

(OEIS'de A002322 dizisi) ın ilk 26 değeri 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
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
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[değiştir | kaynağı değiştir]

72 = 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 74 = 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[değiştir | kaynağı değiştir]

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'ten daha büyük o Euler totient'in tek yarımına eşittir:

Euler'in fonksiyonu asal kuvvetler için ile verilir

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

burada p1 < p2 < ... < pω asaldır ve ai > 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:

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

burada Carmichael fonksiyonu yukardaki tanımdır. Diğer bir deyiş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[değiştir | kaynağı değiştir]

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 OEISA033949 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[değiştir | kaynağı değiştir]

Bölünebilirlik[değiştir | kaynağı değiştir]

Düzen[değiştir | kaynağı değiştir]

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

.

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

Birimin ilkel m-inci kökleri[değiştir | kaynağı değiştir]

Diyelimki ve eşasal olsun ve Diyelimki enküçük üstel ile olsun, bunlar gözönüne alındığında

.

Bu, birimin ilkel kökleriin sırası modül tamsayıların halkası içinde 'in bölenleridir.

Üstel döngü uzunluğu[değiştir | kaynağı değiştir]

Bir sayı için asal çarpan altında 'un maksimum asal üsteli ise tüm için ('ya eş-asal olmayan içerik) ve tüm ,

Özel olarak, for kareserbest (),tüm için

Ortalama ve tipik değer[değiştir | kaynağı değiştir]

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

.[2][3]

Burada

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

burada A bir sabittir,[3][4]

Alt sınır[değiştir | kaynağı değiştir]

Herhangi yeterince büyük sayı N için ve herhangi için, burada en çok

pozitif tamsayılar böylece .[5]

pozitif tamsayıların herhangi dizisi ,herhangi sabit , ve herhangi yeterince büyük i olsun:

.[6][7]

Küçük değerler[değiştir | kaynağı değiştir]

bir c sabiti ve herhangi yeterince büyük pozitif A için, burada bir tamsayı var böylece .[7] Daha ötesi, n formundur

bazıları için kare-serbest tamsayı .[6]

Ayrıca bakınız[değiştir | kaynağı değiştir]

Notlar[değiştir | kaynağı değiştir]

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

Kaynakça[değiştir | kaynağı değiştir]