Öklid teoremi - Euclid's theorem

Öklid teoremi , sonsuz sayıda asal sayı olduğunu iddia eden sayı teorisinde temel bir ifadedir . İlk olarak Öklid tarafından Elements adlı eserinde kanıtlanmıştır . Teoremin birkaç ispatı vardır.

Öklid'in kanıtı

Öklid , burada başka sözcüklerle ifade edilen Elements adlı çalışmasında (Kitap IX, Önerme 20) yayınlanan bir kanıt sundu .

p 1p 2 , ...,  p n asal sayılarının herhangi bir sonlu listesini düşünün . Bu listede olmayan en az bir ek asal sayının var olduğu gösterilecektir. Listedeki tüm asal sayıların çarpımı P olsun : P  =  p 1 p 2 ... p n . q  =  P  + 1 olsun . O halde q ya asaldır ya da değildir:

  • Eğer q asal ise, listede olmayan en az bir asal sayı daha vardır, yani q'nun kendisi.
  • Eğer q asal değilse, o zaman bir p asal çarpanı q'yu böler  . Bu p faktörü listemizde olsaydı, P'yi bölerdi (çünkü P , listedeki her sayının çarpımıdır); ancak p, aynı zamanda , az önce belirtildiği gibi, P  + 1 =  q'yu da böler . Eğer p , P'yi ve ayrıca q'yu bölerse, o zaman p iki sayının farkını da bölmelidir, yani ( P  + 1) −  P veya sadece 1'dir. Hiçbir asal sayı 1'i bölemediğinden, p listede olamaz. Bu, listedekilerin dışında en az bir asal sayının daha var olduğu anlamına gelir.

Bu, her sonlu asal sayı listesi için listede olmayan bir asal sayı olduğunu kanıtlar. Orijinal eserde, Öklid'in keyfi bir asal liste yazmanın bir yolu olmadığı için, sıklıkla uyguladığı bir yöntemi, yani genellenebilir örnek yöntemini kullandı. Yani, sadece üç asal seçiyor ve yukarıda ana hatları verilen genel yöntemi kullanarak, her zaman ek bir asal bulabileceğini kanıtlıyor. Euclid, muhtemelen okuyucularının, başlangıçta kaç tane asal seçilirse seçilsin, benzer bir ispatın işe yarayacağına ikna olduklarını varsayıyor.

Öklid'in, başlangıçta düşünülen sonlu kümenin tüm asal sayıları içerdiği varsayımıyla başlayarak , aslında vakalarla bir ispat , doğrudan bir ispat yöntemi olmasına rağmen, bu sonucu genellikle hatalı bir şekilde kanıtladığı bildirilir . Filozof Torkel Franzén , mantık, devletler üzerinde bir kitapta, "Öklid kanıtı sonsuz sayıda asal var dolaylı kanıt [...] argüman bazen varsayımı ile değiştirerek dolaylı delil olarak formüle edilmiştir 'Varsayalım değil ki q 1 , ... q n'nin hepsi asal sayılardır'. Ancak bu varsayım ispatta bile kullanılmadığı için yeniden formüle etmek anlamsızdır."

Varyasyonlar

Öklid'in ispatında aşağıdakiler de dahil olmak üzere çeşitli varyasyonlar mevcuttur:

Faktöryel n ! pozitif bir tamsayının n , 2'den n'ye kadar olan her tam sayıya bölünebilir , çünkü hepsinin çarpımıdır. Dolayısıyla, n ! + 1 , 2'den n'ye kadar hiçbir tam sayıya bölünemez (her birine bölündüğünde 1 kalanını verir). Bu nedenle n ! + 1 asaldır veya n'den büyük bir asal sayıya bölünebilir  . Her iki durumda da, her pozitif tamsayı için n , daha asal en az bir büyük vardır  n . Sonuç, asal sayısının sonsuz olduğudur.

Euler'in kanıtı

İsviçreli matematikçi Leonhard Euler'in bir başka kanıtı, aritmetiğin temel teoremine dayanır : her tamsayı benzersiz bir asal çarpanlara sahiptir. Euler'in yazdığı (bu modern gösterimle değil ve modern standartların aksine, toplamlar ve ürünlerdeki argümanları herhangi bir sonlu tamsayı kümesiyle sınırlamayan) bizim sahip olduğumuz ifadeye eşdeğerdir.

nerede kümesi belirtir k ilk asal sayılar ve asal faktörler hepsi içindedir pozitif tamsayılar kümesidir

Bunu göstermek için, çarpımdaki her bir faktör geometrik bir seri olarak genişletilir ve çarpım toplamın üzerine dağıtılır (bu, Riemann zeta fonksiyonu için Euler çarpım formülünün özel bir halidir ).

Sondan bir önceki toplamda, asalların her ürünü tam olarak bir kez görünür ve bu nedenle son eşitlik aritmetiğin temel teoremi tarafından doğrudur. Bu sonucun ilk doğal sonucu olarak Euler , «mutlak sonsuzluk» a benzer bir sembolle belirtir ve ifadedeki sonsuz toplamın «değer»e eşit olduğunu yazar , bu nedenle sonsuz çarpım da buna eşittir (modern terminolojide bu eşdeğerdir). harmonik serinin kısmi toplamının asimptotik olarak ıraksadığını söylemek için ). Daha sonra ikinci doğal sonucu Euler, ürünün

sonlu değer 2'ye yakınsar ve sonuç olarak karelerden daha fazla asal sayı vardır (« sequitur infinities plures esse numeros primos »). Bu Öklid Teoremini kanıtlar.

Euler tarafından sonsuzluğu belirtmek için kullanılan sembol


Aynı makalede (Teorem 19) Euler aslında kendisinden önce bilinmeyen çok daha güçlü bir teoremi kanıtlamak için yukarıdaki eşitliği kullandı.

olan ıraksak , P tüm asal sayılar kümesini simgeler (Euler sonsuz toplamı yazıyor Modern terminolojide eşdeğerdir söylemek kısmi toplamı kadar asimptotik gibi bu dizi boğulan bir arasında ).

Erdős'in kanıtı

Paul Erdős , aritmetiğin temel teoremine de dayanan bir ispat verdi. Her pozitif tamsayı bir içine benzersiz çarpanlarına sahip kare içermeyen numarası ve bir kare sayı rs 2 . Örneğin, 75.600 = 2 4 3 3 5 2 7 1 = 21 ⋅ 60 2 .

Let , N pozitif bir tamsayı olması ve izin k daha az asal bir sayı olarak ya da eşit , N . Bu asal sayıları p 1 , ... , p k olarak adlandırın . N'den küçük veya eşit olan herhangi bir pozitif tamsayı daha sonra şu şekilde yazılabilir:

burada her bir E i , ya bir 0 ya da 1 . Orada 2 k kare içermeyen parçasını oluşturan yolları bir . Ve s 2 en fazla N olabilir , bu nedenle sN . Böylece bu formda en fazla 2 k N sayı yazılabilir. Diğer bir deyişle,

Veya, yeniden düzenleme, k , N'den küçük veya ona eşit olan asal sayıların sayısı, N'den büyük veya eşittir 1/2günlük 2 N . Bu yana , N keyfi olduğu, k seçerek arzu edilen kadar büyük olabilir N uygun.

Furstenberg'in kanıtı

1950'lerde Hillel Furstenberg , nokta küme topolojisini kullanarak çelişkili bir kanıt sundu .

Tamsayılar üzerinde bir topoloji tanımlama Z adı verilen, eşit aralıklı tamsayı topolojisi , bir alt bildirerek U  ⊆  Z bir olduğu açık grubu , ancak ve ancak bu ya bir boş grubu , ∅ ya da bir olduğu birlik aritmetik dizilerinin S ( ab ) ( a  ≠ 0 için), burada

Sonra bir çelişki temel standartlar bu tamsayılar sonlu kümesi açık olamayacağını mülkiyet ve mülkiyet aşağıdaki S ( ab ) olan hem açık ve kapalı beri,

tümleyeni sonlu olduğu için kapatılamaz, ancak kapalı kümelerin sonlu birleşimi olduğu için kapalıdır.

Bazı son kanıtlar

Dahil etme-dışlama ilkesini kullanan kanıt

Juan Pablo Pinasco aşağıdaki kanıtı yazmıştır.

Let p 1 , ...,  p N en küçük olmak N asal. Daha sonra dahil etme-dışlama ilkesine göre , bu asallardan birine bölünebilen x'ten küçük veya ona eşit pozitif tam sayıların sayısı

Tarafından bölündüğünde x ve icar x  → ∞ verir

Bu şu şekilde yazılabilir

p 1 , ...,  p N'den başka bir asal sayı yoksa, (1)' deki ifade eşittir  ve (2)'deki ifade 1'e eşittir, ancak açıkça (3)'teki ifade eşit değildir. 1. Bu nedenle, p 1 , ...,  p N'den daha fazla asal olmalıdır   .

De Polignac'ın formülünü kullanan kanıt

2010 yılında, Junho Peter Whang çelişkili aşağıdaki kanıtı yayınladı. Let k herhangi bir pozitif tam sayı olması. Sonra de Polignac'ın formülüne göre (aslında Legendre'den dolayı )

nerede

Ama eğer yalnızca sonlu sayıda asal sayı varsa, o zaman

(kesirin payı tek başına üssel olarak büyürken, Stirling'in yaklaşımıyla payda tek başına üstel olmaktan daha hızlı büyür), her k için payın paydaya eşit veya ondan büyük olduğu gerçeğiyle çelişir .

İnşaat kanıtı

Filip Saidak aşağıdaki verdi inşaat tarafından kanıt kullanmaz, reductio saçmaya veya Öklid Lemma (yani bir başbakan eğer p böler ab sonra bölmek gerekir bir veya  b ).

Her bir doğal sayı (> 1) sahip olduğu için en az bir asıl faktörü ve birbirini takip eden iki sayı , n ve ( n  + 1) ortak olan bir faktör, ürün bilgisi , n ( n  + 1) sayısından daha fazla farklı ana faktörler vardır n kendisi . Pronik sayılar zinciri :
1×2 = 2 {2}, 2×3 = 6 {2, 3}, 6×7 = 42 {2, 3, 7}, 42×43 = 1806 {2, 3, 7, 43}, 1806×1807 = 3263442 {2, 3, 7, 43, 13, 139}, · · ·
sınırsız büyüyen asal kümeler dizisi sağlar.

π irrasyonelliğini kullanarak ispat

π için Leibniz formülünü bir Euler çarpımı olarak temsil etmek ,

Bu çarpımın payları tek asal sayılardır ve her payda, paya en yakın dördün katıdır.

Sonlu sayıda asal sayı olsaydı, bu formül π'nin irrasyonel olduğu gerçeğiyle çelişerek π'nin rasyonel bir sayı olduğunu gösterirdi .

Bilgi teorisini kullanarak kanıt

Alexander Shen, sıkıştırılamazlığı kullanan bir kanıt sundu :

Sadece k tane asal sayı olduğunu varsayalım ( p 1 ...  p k ). Tarafından aritmetik temel teoremi , herhangi bir pozitif tam sayı , n , sonra olarak temsil edilebilir:

burada negatif olmayan tamsayı üsleri e i sonlu boyutlu asal listeyle birlikte sayıyı yeniden oluşturmak için yeterlidir. İtibaren tüm i , tüm aşağıdaki (burada baz-2 logaritması anlamına gelir).

Bu , aşağıdaki boyutta n için bir kodlama sağlar ( büyük O notasyonu kullanılarak ):

bit.

Bu, n'yi doğrudan bit alan ikili dosyada temsil etmekten çok daha verimli bir kodlamadır . Kayıpsız veri sıkıştırmada yerleşik bir sonuç, genellikle N bitlik bilginin N bitten daha azına sıkıştırılamayacağını belirtir . Yukarıdaki temsil, n'den beri yeterince büyük olduğunda , bunu açık ara ihlal ediyor .

Bu nedenle, asal sayısı sonlu olmamalıdır.

Daha güçlü sonuçlar

Bu bölümdeki teoremler aynı anda Öklid teoremini ve diğer sonuçları ima eder.

Aritmetik ilerlemeler üzerinde Dirichlet teoremi

Dirichlet teoremi, herhangi iki pozitif asal tamsayı a ve  d için , a  +  nd biçiminde sonsuz sayıda asal sayı olduğunu belirtir , burada n aynı zamanda pozitif bir tam sayıdır. Başka bir deyişle, olan sonsuz sayıda asal vardır uyumlu için bir modülo d .

asal sayı teoremi

Let π ( X ) olmak ana sayma fonksiyonu daha az asal sayısını verir ya da eşit , x , herhangi bir gerçek sayı için,  x . Asal sayı teoremi sonra bildiren x / günlük x için iyi bir yaklaşımdır π ( x ) bu anlamda, sınır arasında bölüm iki fonksiyonları arasında π ( x ) ve X / günlük X olarak X , bağlı olmayan artışlar 1 :

Kullanımı notasyonu ASİMPTOTİK bu sonucu olarak yeniden ifade edilebilir

Bu, Öklid teoremini verir, çünkü

Bertrand-Chebyshev teoremi

Gelen sayılar teorisi , Bertrand'ın postülası bir olan teoremi herhangi belirten tamsayı , her zaman en az bir vardır asal sayı olacak şekilde

Bertrand-Chebyshev teoremi ile bir ilişki olarak ifade edilebilir , bir asal sayma fonksiyonu (asal sayısı daha az veya eşit ):

hepsi için


Bu ifade ilk olarak 1845'te Joseph Bertrand (1822–1900) tarafından tahmin edildi . Bertrand, ifadesini [2, 3 × 10 6 ] aralığındaki tüm sayılar için doğruladı . Onun varsayımı 1852'de Chebyshev (1821-1894) tarafından tamamen kanıtlandı ve bu nedenle postüla Bertrand-Chebyshev teoremi veya Chebyshev teoremi olarak da adlandırılır .

Notlar ve referanslar

Dış bağlantılar