Carmichael numarası - Carmichael number

Gelen sayı teorisi , bir Carmichael numarası bir olan bileşik sayı olan tatmin modüler aritmetik uyum ilişkisi: ${\görüntüleme stili n}$

${\displaystyle b^{n-1}\eşdeğer 1{\pmod {n}}}$

göreli olarak asal olan tüm tamsayılar için . Onlar Robert Carmichael için adlandırılmıştır . Carmichael sayıları , Knödel sayılarının K ₁ alt kümesidir . ${\görüntüleme stili b}$${\görüntüleme stili n}$

Eşdeğer olarak, bir Carmichael sayısı, bunun için bir bileşik sayıdır . ${\görüntüleme stili n}$

${\displaystyle b^{n}\eşdeğer b{\pmod {n}}}$

tüm tamsayılar için . ${\görüntüleme stili b}$

genel bakış

Fermat'ın küçük teoremi eğer belirtiyor p bir olduğunu asal sayı , daha sonra herhangi bir tamsayı b , sayı b ^p  -  b bir tamsayı katı olan p . Carmichael sayıları bu özelliğe sahip bileşik sayılardır. Carmichael sayılarına ayrıca Fermat yalancı asalları veya mutlak Fermat asal sayıları da denir . Bir Carmichael sayısı, gerçekte asal olmasa da, sayıya görece asal olan her b tabanına bir Fermat asallık testinden geçecektir . Bu, Fermat'ın Küçük Teoremi'ne dayalı testleri, Baillie–PSW asallık testi ve Miller–Rabin asallık testi gibi güçlü olası asal testlerden daha az etkili hale getirir .

Ancak, hiçbir Carmichael sayı ya olan Euler-Jacobi pseudoprime veya kuvvetli pseudoprime kendisine aralarında asal her tabanına böylece, teorik olarak, bir Euler veya kuvvetli muhtemel asal testi ya bir Carmichael sayı olduğunu kanıtlamak aslında, kompozit.

Arnault bir 397 basamaklı Carmichael numarası verir bir olan güçlü tümüne pseudoprime asal az 307 den bazlar: ${\ ekran stili N}$

${\displaystyle N=p\cdot (313(p-1)+1)\cdot (353(p-1)+1)}$

nerede

${\görüntüleme stili p=}$29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883

131 basamaklı bir asal sayıdır. 'nin en küçük asal çarpanıdır , dolayısıyla bu Carmichael sayısı aynı zamanda 'den küçük tüm tabanlar için (güçlü olması gerekmez) bir sözde asaldır . ${\görüntüleme stili p}$${\ ekran stili N}$${\görüntüleme stili p}$

Sayılar büyüdükçe, Carmichael sayıları giderek daha nadir hale gelir. Örneğin, 1 ile 10 ²¹ arasında 20.138.200 Carmichael sayısı vardır (yaklaşık 50 trilyon ( 5.10 ¹³ ) sayıda bir).

Korselt'in kriteri

Carmichael sayılarının alternatif ve eşdeğer bir tanımı Korselt'in kriteri ile verilmiştir .

Teorem ( A. Korselt 1899): Pozitif kompozit tamsayı ve ancak eğer bir Carmichael sayıdır olan kare serbest ve herkes için asal bölenler arasında , bu doğrudur .${\görüntüleme stili n}$${\görüntüleme stili n}$ ${\görüntüleme stili p}$${\görüntüleme stili n}$${\displaystyle p-1\orta n-1}$

Bu teoremden, tüm Carmichael sayılarının tek olduğu sonucu çıkar , çünkü karesi olmayan (ve dolayısıyla yalnızca bir asal çarpanı iki olan) herhangi bir çift sayı, en az bir tek asal çarpana sahip olacaktır ve bu nedenle , bir çift bölme ile sonuçlanır. tuhaf, çelişki. (Carmichael sayılarının tekliği, herhangi bir çift bileşik sayı için bir Fermat tanığı olduğu gerçeğinden de kaynaklanır .) Kriterden, Carmichael sayılarının döngüsel olduğu da çıkar . Ek olarak, tam olarak iki asal böleni olan hiçbir Carmichael sayısı yoktur. ${\displaystyle p-1\orta n-1}$${\görüntüleme stili -1}$

keşif

Carmichael sayılarının temel özelliklerini ilk gözlemleyen Korselt olmuştur, ancak herhangi bir örnek vermemiştir. 1910'da Carmichael, "Carmichael numarası" adını açıklayan ilk ve en küçük sayı olan 561'i buldu.

561'in bir Carmichael sayısı olduğu Korselt'in kriteri ile görülebilir. Gerçekten de, karesizdir ve , ve . ${\displaystyle 561=3\cdot 11\cdot 17}$${\ Displaystyle 2\orta 560}$${\displaystyle 10\orta 560}$${\ Displaystyle 16\orta 560}$

Bir sonraki altı Carmichael numaraları (dizisidir A002997 olarak OEIS ):

${\displaystyle 1105=5\cdot 13\cdot 17\qquad (4\mid 1104;\quad 12\orta 1104;\quad 16\orta 1104)}$

${\displaystyle 1729=7\cdot 13\cdot 19\qquad (6\orta 1728;\dört 12\orta 1728;\dört 18\orta 1728)}$

${\displaystyle 2465=5\cdot 17\cdot 29\qquad (4\orta 2464;\dört 16\orta 2464;\dört 28\orta 2464)}$

${\displaystyle 2821=7\cdot 13\cdot 31\qquad (6\orta 2820;\dört 12\orta 2820;\dört 30\orta 2820)}$

${\displaystyle 6601=7\cdot 23\cdot 41\qquad (6\orta 6600;\dört 22\orta 6600;\dört 40\orta 6600)}$

${\displaystyle 8911=7\cdot 19\cdot 67\qquad (6\orta 8910;\dört 18\orta 8910;\dörtlü 66\orta 8910).}$

561'den 8911'e kadar olan bu ilk yedi Carmichael sayısının tümü Çek matematikçi Václav Šimerka  [ de ; cs ] 1885'te (bu nedenle Šimerka Korselt'in kriteri gibi bir şey bulamamış olsa da, yalnızca Carmichael'dan değil, Korselt'ten de önce). Ancak çalışmaları fark edilmeden kaldı.

J. Chernick , 1939'da Carmichael sayılarının bir alt kümesini oluşturmak için kullanılabilecek bir teoremi kanıtladı . Numara onun üç faktör tüm asal olup olmadığını bir Carmichael sayıdır. Bu formülün sonsuz miktarda Carmichael sayısı üretip üretmediği açık bir sorudur ( Dickson'ın varsayımında ima edilmiş olsa da ). ${\displaystyle (6k+1)(12k+1)(18k+1)}$

Paul Erdős , sonsuz sayıda Carmichael sayısının olması gerektiğini sezgisel olarak savundu. 1994'te WR (Kırmızı) Alford , Andrew Granville ve Carl Pomerance , gerçekten sonsuz sayıda Carmichael sayısının var olduğunu göstermek için Olson sabiti üzerinde bir sınır kullandılar . Spesifik olarak, yeterince büyük için 1 ile arasında en az Carmichael sayıları olduğunu gösterdiler . ${\görüntüleme stili n}$${\görüntüleme stili n^{2/7}}$${\görüntüleme stili n}$

Thomas Wright , eğer ve göreceli olarak asal iseler , o zaman aritmetik ilerlemede sonsuz sayıda Carmichael sayısı olduğunu kanıtladı , burada . ${\görüntüleme stili bir}$${\görüntüleme stili m}$${\displaystyle a+k\cdot m}$${\görüntüleme stili k=1,2,\ldots }$

1992'de Löh ve Niebuhr, 1.101.518 faktörlü ve 16 milyondan fazla basamaklı bir tane de dahil olmak üzere çok büyük bazı Carmichael sayıları buldular. Bu, 10.333.229.505 asal çarpana ve 295.486.761.787 basamağa yükseltildi, bu nedenle bilinen en büyük Carmichael sayısı, bilinen en büyük asal sayıdan çok daha büyük .

Özellikleri

çarpanlara ayırma

Carmichael sayılarının en az üç pozitif asal çarpanı vardır. İlk Carmichael numaraları asal faktörlere (sekans olan A006931 içinde OEIS ): ${\görüntüleme stili k=3,4,5,\ldots }$

k
3	${\displaystyle 561=3\cdot 11\cdot 17\,}$
4	${\displaystyle 41041=7\cdot 11\cdot 13\cdot 41\,}$
5	${\displaystyle 825265=5\cdot 7\cdot 17\cdot 19\cdot 73\,}$
6	${\displaystyle 321197185=5\cdot 19\cdot 23\cdot 29\cdot 37\cdot 137\,}$
7	${\displaystyle 5394826801=7\cdot 13\cdot 17\cdot 23\cdot 31\cdot 67\cdot 73\,}$
8	${\displaystyle 232250619601=7\cdot 11\cdot 13\cdot 17\cdot 31\cdot 37\cdot 73\cdot 163\,}$
9	${\displaystyle 9746347772161=7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 31\cdot 37\cdot 41\cdot 641\,}$

4 ana faktör ilk Carmichael numaraları (dizisidir A074379 olarak OEIS ):

ben
1	${\displaystyle 41041=7\cdot 11\cdot 13\cdot 41\,}$
2	${\displaystyle 62745=3\cdot 5\cdot 47\cdot 89\,}$
3	${\displaystyle 63973=7\cdot 13\cdot 19\cdot 37\,}$
4	${\displaystyle 75361=11\cdot 13\cdot 17\cdot 31\,}$
5	${\displaystyle 101101=7\cdot 11\cdot 13\cdot 101\,}$
6	${\displaystyle 126217=7\cdot 13\cdot 19\cdot 73\,}$
7	${\displaystyle 172081=7\cdot 13\cdot 31\cdot 61\,}$
8	${\displaystyle 188461=7\cdot 13\cdot 19\cdot 109\,}$
9	${\displaystyle 278545=5\cdot 17\cdot 29\cdot 113\,}$
10	${\displaystyle 340561=13\cdot 17\cdot 23\cdot 67\,}$

İkinci Carmichael sayısı (1105), herhangi bir küçük sayıdan daha fazla şekilde iki karenin toplamı olarak ifade edilebilir. Üçüncü Carmichael sayısı (1729) Hardy-Ramanujan Sayısıdır : iki küpün (pozitif sayıların) toplamı olarak iki farklı şekilde ifade edilebilen en küçük sayıdır.

dağıtım

' den küçük veya eşit olan Carmichael sayılarının sayısını gösterelim . 10 (sekans güçler tarafından Carmichael sayıların dağılımı A055553 olarak OEIS ): ${\görüntüleme stili C(X)}$${\görüntüleme stili X}$

${\görüntüleme stili n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
${\ Displaystyle C(10^{n})}$	0	0	1	7	16	43	105	255	646	1547	3605	8241	19279	44706	105212	246683	585355	1401644	3381806	8220777	20138200

1953'te Knödel üst sınırı kanıtladı :

${\displaystyle C(X)<X\exp \sol({-k_{1}\left(\log X\log \log X\sağ)^{\frac {1}{2}}}\sağ)}$

bazı sabit için . ${\görüntüleme stili k_{1}}$

1956'da Erdős,

${\displaystyle C(X)<X\exp \left({\frac {-k_{2}\log X\log\log \log X}{\log \log X}}\sağ)}$

bazı sabit için . Ayrıca , bu üst sınırın gerçek büyüme oranına yakın olması gerektiğini öne süren buluşsal bir argüman verdi . ${\görüntüleme stili k_{2}}$${\görüntüleme stili C(X)}$

Diğer yönde, Alford , Granville ve Pomerance 1994'te yeterince büyük X için ,

${\displaystyle C(X)>X^{\frac {2}{7}}.}$

2005 yılında, bu sınır Harman tarafından daha da geliştirildi .

${\displaystyle C(X)>X^{0.332}}$

kim daha sonra üssü geliştirdi . ${\displaystyle 0.7039\cdot 0.4736=0.33336704>1/3}$

Carmichael sayılarının asimptotik dağılımı ile ilgili olarak birkaç varsayım yapılmıştır. 1956'da Erdős , X için yeterince büyük Carmichael sayılarının olduğunu tahmin etti . 1981'de Pomerance, Erdős'in buluşsal argümanlarını keskinleştirdi. ${\displaystyle X^{1-o(1)}}$

${\displaystyle X\cdot L(X)^{-1+o(1)}}$

Carmichael numaraları nereye kadar . ${\görüntüleme stili X}$${\displaystyle L(x)=\exp {\sol({\frac {\log x\log\log\log x}{\log\log x}}\sağ)}}$

Ancak, içinde mevcut hesaplama aralıkları (10'a kadar sıkıştırın böyle Carmichael numaralarının sayımları gibi gerçekleştirilmiştir ²¹ ), bu varsayımlar henüz verilerden ortaya değildir.

genellemeler

Carmichael sayısı kavramı, herhangi bir sayı alanında K bir Carmichael idealine genellenir . Sıfır olmayan herhangi İçin asal ideali içinde , elimizdeki tüm in , norm olduğu ideali . (Bu, Fermat'ın küçük teoremini, p asal olduğunda tüm m tamsayıları için genelleştirir .) Carmichael'de sıfır olmayan bir ideal , eğer bir asal ideal değilse ve herkes için , idealin normu nerededir diye adlandırın . Ne zaman K ise ideal olan anapara ve biz izin verirsek bir olumlu jeneratör olmak sonra idealdir tam olarak ne zaman Carmichael bir olağan anlamda bir Carmichael sayıdır. ${\displaystyle {\mathfrak {p}}}$${\görüntüleme stili {\matematiksel {O}}_{K}}$${\displaystyle \alpha ^{{\rm {N}}({\mathfrak {p}})}\equiv \alpha {\bmod {\mathfrak {p}}}}$${\görüntüleme stili \alfa }$${\görüntüleme stili {\matematiksel {O}}_{K}}$${\displaystyle {\rm {N}}({\mathfrak {p}})}$ ${\displaystyle {\mathfrak {p}}}$${\displaystyle m^{p}\eşdeğer m{\bmod {p}}}$${\görüntüleme stili {\mathfrak {a}}}$${\görüntüleme stili {\matematiksel {O}}_{K}}$${\displaystyle \alpha ^{{\rm {N}}({\mathfrak {a}})}\equiv \alpha {\bmod {\mathfrak {a}}}}$${\displaystyle \alpha \in {\mathcal {O}}_{K}}$${\displaystyle {\rm {N}}({\mathfrak {a}})}$${\görüntüleme stili {\mathfrak {a}}}$${\displaystyle \mathbf {Q} }$${\görüntüleme stili {\mathfrak {a}}}$${\displaystyle {\mathfrak {a}}=(a)}$

Ne zaman K büyükse rationals içeri Carmichael ideallerini yazmak kolaydır : Herhangi asal sayı için p tamamen bölünme olduğu K , Esas İdeal bir Carmichael idealdir. Herhangi bir sayı alanında sonsuz sayıda asal sayı tamamen bölündüğünden, içinde sonsuz sayıda Carmichael ideali vardır . Örneğin, p , 1 mod 4 olan herhangi bir asal sayıysa, Z [ i ] Gauss tamsayılarındaki ideal ( p ) bir Carmichael idealdir. ${\görüntüleme stili {\matematiksel {O}}_{K}}$${\displaystyle p{\mathcal {O}}_{K}}$${\görüntüleme stili {\matematiksel {O}}_{K}}$   

Hem asal hem de Carmichael sayıları aşağıdaki eşitliği sağlar:

${\displaystyle \gcd \sol(\sum _{x=1}^{n-1}x^{n-1},n\sağ)=1.}$

Lucas-Carmichael numarası

Pozitif kompozit tamsayı ve ancak eğer bir Lucas-Carmichael sayıdır olan kare serbest ve herkes için asal bölenler arasında , bu doğrudur . İlk Lucas-Carmichael sayıları: ${\görüntüleme stili n}$${\görüntüleme stili n}$ ${\görüntüleme stili p}$${\görüntüleme stili n}$${\displaystyle p+1\mid n+1}$

399, 935, 2015, 2915, 4991, 5719, 7055, 8855, 12719, 18095, 20705, 20999, 22847, 29315, 31535, 46079, 51359, 60059, 63503, 67199, 73535, 76751, 80189, 81719, 88559, 90.287, ... (dizi A006972 olarak OEIS )

Yarı-Carmichael numarası

Yarı-Carmichael numaraları squarefree bileşik numaraları , n özelliği her ana faktör söz konusu p ve n , p  +  b bölme n  +  b ile pozitif b 0 dışında bir tamsayıdır ise b = -1, bu Carmichael sayılardır ve eğer b = 1, bunlar Lucas–Carmichael sayılarıdır. İlk Yarı-Carmichael sayıları şunlardır:

35, 77, 143, 165, 187, 209, 221, 231, 247, 273, 299, 323, 357, 391, 399, 437, 493, 527, 561, 589, 598, 713, 715, 899, 935, 943, 989, 1015, 1073, 1105, 1147, 1189, 1247, 1271, 1295, 1333, 1517, 1537, 1547, 1591, 1595, 1705, 1729, ... (dizi A257750 olarak OEIS )

Knödel numarası

Bir N - Knödel sayısı , belirli bir için pozitif bir tam sayı , n a, bileşik sayı m özelliği ile her birinin i  <  m, göreceli asal için m tatmin . N = 1 vaka Carmichael sayılardır. ${\displaystyle i^{mn}\eşdeğer 1{\pmod {m}}}$

Daha yüksek dereceli Carmichael sayıları

Carmichael sayıları soyut cebir kavramları kullanılarak genelleştirilebilir .

Bir bileşik tam sayı olduğu yukarıdaki tanımı durumları n tam olarak ne zaman Carmichael N inci güç yükseltme fonksiyonu p _{, n} den halka Z _{, n} tamsayılar modulo n kendi kimlik fonksiyonudur. Kimlik sadece Z'nin _N - cebir Endomorfizma ile Z _{, n} o soran tanımı yeniden ifade böylece p _{, n} bir cebri Endomorfizma olarak Z _{, n} . Yukarıdaki gibi, p _n , n asal olduğunda aynı özelliği sağlar .

N inci güç yükseltme fonksiyonu p _{, n} , aynı zamanda herhangi bir tanımlanır Z _{, n} cebiri A . Bir teorem, n'nin asal olduğunu, ancak ve ancak bu p _n gibi tüm fonksiyonların cebir endomorfizmleri olması durumunda belirtir .

-İn arasında, bu iki durum arasında tanımı yatmaktadır sırası m Carmichael sayısı herhangi bir pozitif tam sayı için m herhangi bir bileşik numarası olarak N , öyle ki p _{, n} , her bir Endomorfizma olan Z _{, n} olarak oluşturulabilir cebiri Z _N - modülü tarafından m elemanlarının . 1. dereceden Carmichael sayıları sadece sıradan Carmichael sayılarıdır.

Bir sipariş 2 Carmichael numarası

Howe'a göre, 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331 bir sipariş 2 Carmichael numarasıdır. Bu ürün 443.372.888.629.441'e eşittir.

Özellikleri

Korselt'in kriteri, Howe tarafından gösterildiği gibi, daha yüksek dereceli Carmichael sayılarına genelleştirilebilir.

Aynı makalede verilen buluşsal bir argüman, herhangi bir m için sonsuz sayıda Carmichael m mertebesinde sayı olduğunu öne sürüyor gibi görünüyor . Ancak, 3 veya daha yüksek sıradaki tek bir Carmichael numarası bilinmemektedir.

Notlar

Referanslar

• Carmichael, RD (1910). "Yeni bir sayı teorisi işlevi hakkında not" . Amerikan Matematik Derneği Bülteni . 16 (5): 232–238. doi : 10.1090/s0002-9904-1910-01892-9 .
• Carmichael, RD (1912). " Fermat kongrüansını sağlayan bileşik sayılar P üzerinde ". Amerikan Matematiksel Aylık . 19 (2): 22–27. doi : 10.2307/2972687 . JSTOR 2972687 .${\displaystyle a^{P-1}\eşdeğer 1{\bmod {P}}}$ 
• Chernick, J. (1939). "Fermat'ın basit teoremi Üzerine" (PDF) . Boğa. Amer. Matematik. Soc . 45 (4): 269-274. doi : 10.1090/S0002-9904-1939-06953-X .
• Korselt, AR (1899). "Sorun chinois". L'Intermediaire des Mathématiciens . 6 : 142-143.
• Löh, G.; Niebuhr, W. (1996). "Büyük Carmichael sayıları oluşturmak için yeni bir algoritma" (PDF) . Matematik. Komp . 65 (214): 823-836. Bibcode : 1996MaCom..65..823L . doi : 10.1090/S0025-5718-96-00692-8 .
• Ribenboim, P. (1989). Asal Sayı Kayıtları Kitabı . Springer. ISBN'si 978-0-387-97042-4.
• Şimerka, V. (1885). "Zbytky z aritmetik posloupnosti (Bir aritmetik ilerlemenin geri kalanında)" . Časopis Pro Pěstování Matematiksel ve Fysiky . 14 (5): 221-225. doi : 10.21136/CPMF.1885.122245 .

Dış bağlantılar

• "Carmichael numarası" , Matematik Ansiklopedisi , EMS Press , 2001 [1994]
• Matematik Ansiklopedisi
• Carmichael numaraları tablosu
• Birçok asal çarpanlı Carmichael sayılarının tabloları
• Aşağıdaki Carmichael sayılarının tabloları ${\görüntüleme stili 10^{18}}$
• "1729 Donukluk" . MathPages.com .
• Weisstein, Eric W. "Carmichael Numarası" . Matematik Dünyası .
• Son Cevaplar Modüler Aritmetik