Asal sayılar nedir? Bu sayı asal mı yoksa bileşik mi? Asal Sayıların Özellikleri

Teorem.

Sonsuz sayıda asal sayı vardır.

Kanıt.

Durumun böyle olmadığını varsayalım. Yani, yalnızca n tane asal sayı olduğunu ve bu asal sayıların p 1, p 2, ..., p n olduğunu varsayalım. Her zaman belirtilenlerden farklı bir asal sayı bulabileceğimizi gösterelim.

p sayısının p 1 ·p 2 ·…·p n +1'e eşit olduğunu düşünün. Bu sayının p 1, p 2, ..., p n asal sayılarının her birinden farklı olduğu açıktır. Eğer p sayısı asal ise teorem kanıtlanmış olur. Eğer bu sayı bileşik sayıysa, önceki teorem uyarınca bu sayının bir asal böleni vardır (bunu p n+1 olarak gösteririz). Bu bölenin p 1, p 2, ..., p n sayılarından hiçbiriyle çakışmadığını gösterelim.

Eğer böyle olmasaydı, bölünebilme özelliklerine göre p 1 ·p 2 ·…·p n çarpımı p n+1'e bölünürdü. Ancak p sayısı aynı zamanda p n+1'e de bölünebilir, bu da p 1 ·p 2 ·…·p n +1 toplamına eşittir. Buradan p n+1'in bu toplamın bire eşit olan ikinci terimini bölmesi gerektiği sonucu çıkar, ancak bu imkansızdır.

Böylece önceden belirlenen asal sayılar arasında yer almayan yeni bir asal sayının her zaman bulunabileceği kanıtlanmıştır. Bu nedenle sonsuz sayıda asal sayı vardır.

Dolayısıyla, sonsuz sayıda asal sayı olması nedeniyle, asal sayı tablolarını derlerken kendinizi her zaman yukarıdan bir sayıyla, genellikle 100, 1.000, 10.000 vb. ile sınırlandırırsınız.

Eratostenes Eleği

Şimdi asal sayılar tablosu oluşturmanın yollarını tartışacağız. 100'e kadar asal sayıların bir tablosunu yapmamız gerektiğini varsayalım.

Bu sorunu çözmenin en belirgin yöntemi, 2'den başlayıp 100 ile biten pozitif tam sayıları, 1'den büyük ve test edilen sayıdan küçük bir pozitif bölenin varlığı açısından sırayla kontrol etmektir (bildiğimiz bölünebilirlik özelliklerinden) Bölenin mutlak değeri, sıfır olmayan temettü mutlak değerini aşmamalıdır). Böyle bir bölen bulunamazsa test edilen sayı asaldır ve asal sayılar tablosuna girilir. Böyle bir bölen bulunursa, test edilen sayı bileşik sayıdır; asal sayılar tablosuna girilmez. Bundan sonra, bir bölenin varlığı açısından benzer şekilde kontrol edilen bir sonraki sayıya geçiş gerçekleşir.

İlk birkaç adımı açıklayalım.

2 numarayla başlıyoruz. 2 sayısının 1 ve 2 dışında pozitif böleni yoktur. Bu nedenle basittir, bu nedenle asal sayılar tablosuna giriyoruz. Burada 2'nin en küçük asal sayı olduğunu söylemek gerekir. 3 numaraya geçelim. 1 ve 3 dışındaki olası pozitif böleni 2 sayısıdır. Ancak 3, 2'ye bölünemez, bu nedenle 3 asal bir sayıdır ve asal sayılar tablosuna da dahil edilmesi gerekir. 4 numaraya geçelim. 1 ve 4 dışındaki pozitif bölenleri 2 ve 3 sayıları olabilir, kontrol edelim. 4 sayısı 2'ye bölünebilir, bu nedenle 4 bileşik bir sayıdır ve asal sayılar tablosuna dahil edilmesi gerekmez. Lütfen 4'ün en küçük bileşik sayı olduğunu unutmayın. 5 numaraya geçelim. 2, 3, 4 sayılarından en az birinin böleni olup olmadığını kontrol ediyoruz. 5, 2'ye, 3'e veya 4'e bölünemediği için asaldır ve asal sayılar tablosuna yazılması gerekir. Daha sonra 6, 7 vb. sayılara 100'e kadar geçiş yapılır.

Asal sayılar tablosunu derlemeye yönelik bu yaklaşım ideal olmaktan uzaktır. Öyle ya da böyle var olma hakkı var. Tamsayılardan oluşan bir tablo oluşturmanın bu yöntemiyle, bölenleri bulma sürecini biraz hızlandıracak bölünebilirlik kriterlerini kullanabileceğinizi unutmayın.

Asal sayılar tablosu oluşturmanın daha uygun bir yolu var. Adında bulunan "elek" kelimesi tesadüfi değildir, çünkü bu yöntemin eylemleri, basit sayıları bileşik olanlardan ayırmak için tam sayıları ve büyük birimleri Eratosthenes eleği aracılığıyla "elemeye" yardımcı olur.

50'ye kadar asal sayılar tablosunu derlerken Eratosthenes'in eleğini çalışırken gösterelim.

Öncelikle 2, 3, 4, ..., 50 rakamlarını sırasıyla yazın.

İlk yazılan sayı olan 2 asaldır. Şimdi 2 numaradan itibaren sırayla iki sayı sağa doğru ilerliyoruz ve derlenmekte olan sayılar tablosunun sonuna ulaşana kadar bu sayıların üzerini çiziyoruz. Bu, ikinin katı olan tüm sayıların üzerini çizecektir.

2'den sonra üstü çizili olmayan ilk sayı 3'tür. Bu sayı asaldır. Şimdi, 3 numaradan, sürekli olarak üç rakamla sağa doğru hareket ediyoruz (zaten üzeri çizili rakamları hesaba katarak) ve bunların üzerini çiziyoruz. Bu, üçün katı olan tüm sayıların üzerini çizecektir.

3'ten sonra üstü çizili olmayan ilk sayı 5'tir. Bu sayı asaldır. Şimdi 5 numaradan sürekli olarak 5 numara sağa doğru hareket ediyoruz (daha önce üzeri çizilen sayıları da hesaba katıyoruz) ve üstlerini çiziyoruz. Bu, beşin katı olan tüm sayıların üzerini çizecektir.

Daha sonra 7'nin katı olan sayıların üzerini çiziyoruz, ardından 11'in katı olan sayıların üzerini çiziyoruz ve bu şekilde devam ediyoruz. Üstü çizilecek başka sayı kalmadığında işlem sona erer. Aşağıda Eratosthenes eleği kullanılarak elde edilen 50'ye kadar asal sayıların tamamlanmış tablosu yer almaktadır. Üzeri çizili olmayan tüm sayılar asaldır ve üstü çizili olan tüm sayılar bileşiktir.

Ayrıca Eratosthenes süzgecini kullanarak asal sayılar tablosunu derleme sürecini hızlandıracak bir teoremi formüle edip kanıtlayalım.

Teorem.

Bir bileşik a sayısının birden farklı olan en küçük pozitif böleni, a'dan itibaren olan değeri aşmaz.

Kanıt.

Birden farklı bir bileşik a sayısının en küçük bölenini b harfiyle gösterelim (önceki paragrafın en başında kanıtlanan teoremden anlaşılacağı üzere b sayısı asaldır). O halde a=b·q şeklinde bir q tamsayısı vardır (burada q, tamsayıların çarpma kurallarından çıkan pozitif bir tam sayıdır) ve (b>q için b'nin a'nın en küçük böleni olması koşulu ihlal edilmiştir) çünkü a=q·b) eşitliği nedeniyle q aynı zamanda a sayısının bir böleni olduğundan. Eşitsizliğin her iki tarafını da bir pozitif ve birden büyük bir tamsayı ile çarparak (bunu yapmamıza izin verilir), ve'yi elde ederiz.

Kanıtlanmış teorem Eratostenes eleği hakkında bize ne veriyor?

İlk olarak, bir asal sayı b'nin katları olan bileşik sayıların üzerinin çizilmesi, eşit bir sayıyla başlamalıdır (bu eşitsizlikten kaynaklanır). Örneğin, ikinin katı olan sayıların üzerinin çizilmesi 4 sayısıyla, üçün katları 9 sayısıyla, beşin katları 25 sayısıyla vb. başlamalıdır.

İkinci olarak, Eratosthenes süzgeci kullanılarak n sayısına kadar asal sayılar tablosunun derlenmesi, asal sayıların katları olan tüm bileşik sayıların . Örneğimizde n=50 (50'ye kadar asal sayılar tablosu oluşturduğumuz için) ve bu nedenle Eratosthenes süzgecinin, 2, 3, 5 ve 7 asal sayılarının katları olan tüm bileşik sayıları elemesi gerekir. 50'nin aritmetik karekökünü aşamaz. Yani, artık 11, 13, 17, 19, 23 ve benzeri asal sayıların katları olan sayıları 47'ye kadar aramamıza ve üstlerini çizmemize gerek yok, çünkü bu sayıların üzeri zaten daha küçük asal sayılar 2'nin katları olarak çizilmiş olacaktır. , 3, 5 ve 7 .

Bu sayı asal mı yoksa bileşik mi?

Bazı görevler belirli bir sayının asal mı yoksa bileşik mi olduğunu bulmayı gerektirir. Genel durumda, bu görev, özellikle yazımı önemli sayıda karakterden oluşan sayılar için, basit olmaktan uzaktır. Çoğu durumda, sorunu çözmenin belirli bir yolunu aramanız gerekir. Ancak basit durumlar için düşünce zincirine yön vermeye çalışacağız.

Elbette belirli bir sayının bileşik olduğunu kanıtlamak için bölünebilme testlerini kullanmayı deneyebilirsiniz. Örneğin, bir bölünebilirlik testi, belirli bir sayının birden büyük bir pozitif tam sayıya bölünebildiğini gösteriyorsa, o zaman orijinal sayı bileşiktir.

Örnek.

898.989.898.989.898.989'un bileşik bir sayı olduğunu kanıtlayın.

Çözüm.

Bu sayının rakamlarının toplamı 9·8+9·9=9·17'dir. 9.17'ye eşit olan sayı 9'a bölünebildiğine göre, 9'a bölünebilme kriterine göre orijinal sayının da 9'a bölünebildiği söylenebilir. Bu nedenle kompozittir.

Bu yaklaşımın önemli bir dezavantajı, bölünebilirlik kriterlerinin bir sayının asallığını kanıtlamaya izin vermemesidir. Bu nedenle bir sayının asal mı yoksa bileşik mi olduğunu kontrol ederken farklı bir şekilde ilerlemeniz gerekir.

En mantıklı yaklaşım, belirli bir sayının olası tüm bölenlerini denemektir. Olası bölenlerden hiçbiri belirli bir sayının gerçek böleni değilse bu sayı asal olacaktır, aksi takdirde bileşik olacaktır. Önceki paragrafta kanıtlanan teoremlerden, belirli bir a sayısının bölenlerinin, 'yi aşmayan asal sayılar arasında aranması gerektiği sonucu çıkmaktadır. Böylece, belirli bir a sayısı, a sayısının bölenini bulmaya çalışarak asal sayılara (bunlar asal sayılar tablosundan uygun şekilde alınır) sırayla bölünebilir. Bir bölen bulunursa, a sayısı bileşiktir. 'yi geçmeyen asal sayılar arasında a sayısının böleni yoksa a sayısı asaldır.

Örnek.

Sayı 11 723 basit mi bileşik mi?

Çözüm.

11,723 sayısının bölenlerinin hangi asal sayıya kadar olabileceğini bulalım. Bunu yapmak için değerlendirelim.

Oldukça açık ki , 200'den beri 2 =40.000 ve 11.723<40 000 (при необходимости смотрите статью sayıların karşılaştırılması). Dolayısıyla 11.723'ün olası asal çarpanları 200'den küçüktür. Bu zaten işimizi çok kolaylaştırıyor. Eğer bunu bilmeseydik 200'e kadar değil, 11.723'e kadar tüm asal sayıların üzerinden geçmek zorunda kalırdık.

İstenirse daha doğru değerlendirme yapılabilir. 108 2 =11,664 ve 109 2 =11,881 olduğuna göre 108 2<11 723<109 2 , следовательно, . Dolayısıyla, 109'dan küçük asal sayılardan herhangi biri potansiyel olarak verilen 11,723 sayısının asal çarpanıdır.

Şimdi 11,723 sayısını sırasıyla 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 asal sayılarına böleceğiz. , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 . 11.723 sayısı yazılı asal sayılardan birine bölünürse bileşik olur. Eğer yazılı asal sayılardan herhangi birine bölünemiyorsa asıl sayı asaldır.

Bütün bu tekdüze ve tekdüze bölünme sürecini anlatmayacağız. Hemen diyelim ki 11.723

• Çeviri

Asal sayıların özellikleri ilk olarak Antik Yunan matematikçileri tarafından incelenmiştir. Pisagor okulunun (MÖ 500 - 300) matematikçileri öncelikle asal sayıların mistik ve numerolojik özellikleriyle ilgileniyorlardı. Mükemmel ve dost sayılar hakkında ilk fikirleri ortaya atanlar onlardı.

Mükemmel bir sayının kendi bölenlerinin toplamı kendisine eşittir. Örneğin 6 sayısının gerçek bölenleri 1, 2 ve 3'tür. 1 + 2 + 3 = 6. 28 sayısının bölenleri 1, 2, 4, 7 ve 14'tür. Üstelik 1 + 2 + 4 + 7 + 14 = 28.

Bir sayının uygun bölenlerinin toplamı diğerine eşitse ve bunun tersi de geçerliyse sayılara dost denir - örneğin 220 ve 284. Mükemmel bir sayının kendisine dost olduğunu söyleyebiliriz.

Öklid'in Elementleri MÖ 300'de ortaya çıktı. Asal sayılarla ilgili birçok önemli gerçek zaten kanıtlanmıştır. Elementlerin IX. Kitabında Öklid sonsuz sayıda asal sayının olduğunu kanıtladı. Bu arada bu, çelişki yoluyla kanıtın kullanılmasının ilk örneklerinden biridir. Ayrıca Aritmetiğin Temel Teoremini de kanıtlıyor: Her tam sayı, asal sayıların bir çarpımı olarak benzersiz bir şekilde temsil edilebilir.

Ayrıca 2n-1 sayısının asal olması durumunda 2n-1 * (2n-1) sayısının mükemmel olacağını da gösterdi. Başka bir matematikçi olan Euler, 1747'de mükemmel sayıların bile bu biçimde yazılabileceğini göstermeyi başardı. Bugüne kadar tek mükemmel sayıların var olup olmadığı bilinmiyor.

MÖ 200 yılında. Yunan Eratosthenes, asal sayıları bulmak için Eratosthenes Kalburu adı verilen bir algoritma geliştirdi.

Ve sonra asal sayılara ilişkin araştırmaların tarihinde Orta Çağ'la bağlantılı olarak büyük bir kırılma yaşandı.

Aşağıdaki keşifler 17. yüzyılın başında matematikçi Fermat tarafından yapılmıştır. Albert Girard'ın 4n+1 formundaki herhangi bir asal sayının iki karenin toplamı şeklinde benzersiz bir şekilde yazılabileceği varsayımını kanıtladı ve ayrıca herhangi bir sayının dört karenin toplamı olarak yazılabileceği teoremini formüle etti.

Büyük sayıları çarpanlara ayırmak için yeni bir yöntem geliştirdi ve bunu 2027651281 = 44021 × 46061 sayısı üzerinde gösterdi. Ayrıca Fermat'ın Küçük Teoremini de kanıtladı: eğer p bir asal sayı ise, o zaman herhangi bir a tamsayısı için a p = a modulo olduğu doğru olacaktır. P.

Bu ifade, "Çin varsayımı" olarak bilinen şeyin yarısını kanıtlıyor ve 2000 yıl öncesine dayanıyor: Bir n tamsayısı ancak ve ancak 2 n -2'nin n'ye bölünebilmesi durumunda asaldır. Hipotezin ikinci kısmının yanlış olduğu ortaya çıktı - örneğin 2,341 - 2, 341'e bölünebilir, ancak 341 sayısı bileşiktir: 341 = 31 × 11.

Fermat'ın Küçük Teoremi, sayı teorisindeki diğer birçok sonuca ve sayıların asal olup olmadığını test etmeye yönelik yöntemlere temel oluşturdu; bunların çoğu bugün hala kullanılmaktadır.

Fermat çağdaşlarıyla, özellikle de Maren Mersenne adlı bir keşişle çokça yazışıyordu. Mektuplarından birinde, n'nin ikinin kuvveti olması durumunda 2 n +1 formundaki sayıların her zaman asal olacağını varsaydı. Bunu n = 1, 2, 4, 8 ve 16 için test etti ve n'nin ikinin katı olmaması durumunda sayının mutlaka asal olmayacağından emindi. Bu sayılara Fermat sayıları denir ve yalnızca 100 yıl sonra Euler, bir sonraki sayı olan 2 32 + 1 = 4294967297'nin 641'e bölünebileceğini ve bu nedenle asal olmadığını gösterdi.

2 n - 1 formundaki sayılar da araştırmanın konusu olmuştur, çünkü n bileşik ise sayının kendisinin de bileşik olduğunu göstermek kolaydır. Bu sayılara Mersenne sayıları deniyor çünkü kendisi bu sayıları kapsamlı bir şekilde incelemiş.

Ancak n'nin asal olduğu 2 n - 1 formundaki sayıların tümü asal değildir. Örneğin, 2 11 - 1 = 2047 = 23 * 89. Bu ilk kez 1536'da keşfedildi.

Uzun yıllar boyunca bu tür sayılar matematikçilere bilinen en büyük asal sayıları sağladı. M 19'un 1588'de Cataldi tarafından kanıtlandığı ve Euler'in M 31'in de asal olduğunu kanıtlamasına kadar 200 yıl boyunca bilinen en büyük asal sayı olduğu ortaya çıktı. Bu kayıt bir yüz yıl daha devam etti ve ardından Lucas, M 127'nin asal olduğunu gösterdi (ve bu zaten 39 basamaklı bir sayıdır) ve bundan sonra araştırmalar bilgisayarların gelişiyle devam etti.

1952 yılında M 521, M 607, M 1279, M 2203 ve M 2281 sayılarının asallığı kanıtlandı.

2005 yılına gelindiğinde 42 Mersenne asal sayısı bulunmuştu. Bunlardan en büyüğü M 25964951, 7816230 rakamdan oluşuyor.

Euler'in çalışmasının asal sayılar da dahil olmak üzere sayılar teorisi üzerinde büyük etkisi oldu. Fermat'ın Küçük Teoremini genişletti ve φ fonksiyonunu tanıttı. 5. Fermat sayısı 2 32 +1'i çarpanlara ayırdı, 60 çift dost sayı buldu ve ikinci dereceden karşılıklılık yasasını formüle etti (ancak kanıtlayamadı).

Matematiksel analiz yöntemlerini tanıtan ve analitik sayılar teorisini geliştiren ilk kişi oydu. Yalnızca ∑ (1/n) harmonik serisinin değil, aynı zamanda formdaki bir serinin de olduğunu kanıtladı.

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

Asal sayıların tersinin toplamı ile elde edilen sonuç da ıraksaktır. Harmonik serinin n teriminin toplamı yaklaşık olarak log(n) kadar büyür ve ikinci seri log[ log(n)] kadar daha yavaş ıraksar. Bu, örneğin bugüne kadar bulunan tüm asal sayıların karşılıklarının toplamının, seri hala farklı olsa da, yalnızca 4 vereceği anlamına gelir.

İlk bakışta asal sayıların tam sayılar arasında oldukça rastgele dağıldığı görülmektedir. Örneğin, 10000000'den hemen önceki 100 sayıdan 9'u asal sayıdır ve bu değerden hemen sonraki 100 sayıdan yalnızca 2 tanesi vardır. Ancak büyük dilimlerde asal sayılar oldukça eşit bir şekilde dağılmıştır. Legendre ve Gauss bunların dağılımıyla ilgili konuları ele aldılar. Gauss bir keresinde bir arkadaşına herhangi bir boş 15 dakika içinde her zaman sonraki 1000 sayıdaki asal sayıları saydığını söylemişti. Hayatının sonuna gelindiğinde 3 milyona kadar olan tüm asal sayıları saymıştı. Legendre ve Gauss, büyük n için asal yoğunluğun 1/log(n) olduğunu eşit şekilde hesapladı. Legendre, 1'den n'ye kadar olan aralıktaki asal sayıların sayısını şu şekilde tahmin etti:

π(n) = n/(log(n) - 1,08366)

Ve Gauss logaritmik bir integral gibidir

π(n) = ∫ 1/log(t) dt

2'den n'ye kadar bir entegrasyon aralığı ile.

Asal yoğunluk 1/log(n) ile ilgili ifade Asal Dağılım Teoremi olarak bilinir. 19. yüzyıl boyunca bunu kanıtlamaya çalıştılar ve ilerleme Chebyshev ve Riemann tarafından sağlandı. Bunu, Riemann zeta fonksiyonunun sıfırlarının dağılımı hakkında henüz kanıtlanmamış bir hipotez olan Riemann hipoteziyle ilişkilendirdiler. Asal sayıların yoğunluğu 1896'da Hadamard ve Vallée-Poussin tarafından eşzamanlı olarak kanıtlandı.

Asal sayılar teorisinde hala çözülmemiş birçok soru var ve bunların bazıları yüzlerce yıllık:

• İkiz asal hipotezi birbirinden 2 kat farklı olan sonsuz sayıda asal sayı çiftiyle ilgilidir.
• Goldbach varsayımı: 4 ile başlayan herhangi bir çift sayı, iki asal sayının toplamı olarak gösterilebilir
• n 2 + 1 formunda sonsuz sayıda asal sayı var mıdır?
• n 2 ile (n + 1) 2 arasında bir asal sayı bulmak her zaman mümkün müdür? (n ile 2n arasında her zaman bir asal sayının olduğu Chebyshev tarafından kanıtlanmıştır)
• Fermat asallarının sayısı sonsuz mudur? 4'ten sonra Fermat asal sayıları var mı?
• Herhangi bir uzunluk için ardışık asal sayıların aritmetik ilerlemesi var mıdır? örneğin uzunluk 4 için: 251, 257, 263, 269. Bulunan maksimum uzunluk 26'dır.
• Aritmetik bir ilerlemede ardışık üç asal sayının sonsuz sayıda kümesi var mıdır?
• n 2 - n + 41, 0 ≤ n ≤ 40 için bir asal sayıdır. Böyle asal sayılardan sonsuz sayıda var mıdır? Aynı soru n 2 - 79 n + 1601 formülü için de geçerlidir. Bu sayılar 0 ≤ n ≤ 79 için asaldır.
• N# + 1 formunda sonsuz sayıda asal sayı var mıdır? (n#, n'den küçük tüm asal sayıların çarpılmasının sonucudur)
• n# -1 biçiminde sonsuz sayıda asal sayı var mıdır?
• N formunda sonsuz sayıda asal sayı var mıdır? +1?
• N formunda sonsuz sayıda asal sayı var mıdır? – 1?
• eğer p asalsa, 2 p -1'in çarpanları arasında her zaman asal kareler bulunmaz mı?
• Fibonacci dizisi sonsuz sayıda asal sayı içeriyor mu?

En büyük ikiz asal sayılar 2003663613 × 2 195000 ± 1'dir. 58711 rakamdan oluşurlar ve 2007 yılında keşfedilmişlerdir.

En büyük faktöriyel asal sayı (n! ± 1 tipinde) 147855'tir! - 1. 142891 rakamdan oluşur ve 2002 yılında bulunmuştur.

En büyük ilkel asal sayı (n# ± 1 formundaki bir sayı) 1098133# + 1'dir.

Etiketler: Etiket ekleyin

Bölenlerin numaralandırılması. Tanım gereği sayı N yalnızca 2'ye ve 1 ve kendisi dışındaki diğer tam sayılara eşit olarak bölünemediğinde asaldır. Yukarıdaki formül gereksiz adımları ortadan kaldırır ve zaman tasarrufu sağlar: Örneğin, bir sayının 3'e bölünüp bölünemediğini kontrol ettikten sonra, 9'a bölünebilir olup olmadığını kontrol etmeye gerek yoktur.

• Floor(x) işlevi, x'i x'ten küçük veya ona eşit olan en yakın tam sayıya yuvarlar.

Modüler aritmetik hakkında bilgi edinin."X mod y" işlemi (mod, Latince "modulo" yani "modül" kelimesinin kısaltmasıdır) "x'i y'ye böl ve kalanı bul" anlamına gelir. Başka bir deyişle, modüler aritmetikte belirli bir değere ulaşıldığında buna denir. modül, sayılar tekrar sıfıra "döner". Örneğin bir saat, zamanı 12 modülüyle tutar: saat 10, 11 ve 12'yi gösterir ve sonra 1'e döner.

• Çoğu hesap makinesinde mod tuşu bulunur. Bu bölümün sonunda bu fonksiyonun büyük sayılar için manuel olarak nasıl değerlendirileceği gösterilmektedir.

Tanım 1. Asal sayı- Yalnızca kendisine ve 1'e bölünebilen birden büyük bir doğal sayıdır.

Başka bir deyişle, bir sayı yalnızca iki farklı doğal çarpana sahipse asaldır.

Tanım 2. Kendisinden ve birinden başka bölenleri olan her doğal sayıya denir bileşik bir sayı.

Yani asal sayı olmayan doğal sayılara bileşik sayılar denir. Tanım 1'den, bileşik bir sayının ikiden fazla doğal faktöre sahip olduğu sonucu çıkar. 1 sayısı ne asal ne de bileşiktir çünkü yalnızca bir 1 böleni vardır ve ayrıca asal sayılarla ilgili birçok teorem birlik için geçerli değildir.

Tanım 1 ve 2'den, 1'den büyük her pozitif tam sayının ya asal sayı ya da bileşik sayı olduğu sonucu çıkar.

Aşağıda 5000'e kadar asal sayıları görüntüleyen program verilmiştir. Hücreleri doldurun, "Oluştur" butonuna tıklayın ve birkaç saniye bekleyin.

Asal sayılar tablosu

İfade 1. Eğer P- asal sayı ve A herhangi bir tamsayı, o zaman ya A bölünmüş P, veya P Ve A eş asal sayılar.

Gerçekten mi. Eğer P Asal sayı sadece kendisine ve 1'e bölünürse A bölünemez P, o zaman en büyük ortak bölen A Ve P 1'e eşittir. O zaman P Ve A eş asal sayılar.

İfade 2. Birkaç sayının çarpımı ise A 1 , A 2 , A 3, ... bir asal sayıya bölünebilir P, ardından sayılardan en az biri A 1 , A 2 , A 3, ...bölünebilir P.

Gerçekten mi. Eğer sayıların hiçbiri bölünemiyorsa P, ardından sayılar A 1 , A 2 , A 3, ... göre asal sayılar olacaktır P. Ancak Sonuç 3'ten () şu sonuç çıkıyor: ürünleri A 1 , A 2 , A 3, ... aynı zamanda göreli olarak asaldır P bu da beyanın şartına aykırıdır. Bu nedenle sayılardan en az biri bölünebilir P.

Teorem 1. Herhangi bir bileşik sayı her zaman ve benzersiz bir şekilde, sonlu sayıda asal sayının çarpımı olarak temsil edilebilir.

Kanıt. İzin vermek k bileşik sayı ve izin ver A 1, 1'den ve kendisinden farklı bölenlerinden biridir. Eğer A 1 bileşiktir, o zaman 1'e ek olarak vardır ve A 1 ve başka bir bölen A 2. Eğer A 2 bileşik bir sayıdır, o zaman 1'e ek olarak vardır ve A 2 ve başka bir bölen A 3. Bu şekilde akıl yürütmek ve sayıları dikkate almak A 1 , A 2 , A 3 , ... azalınca bu seri sonlu sayıda terim içeriyorsa bazı asal sayılara ulaşacağız P 1. Daha sonra kşeklinde temsil edilebilir

Bir sayının iki ayrışımı olduğunu varsayalım k:

Çünkü k=p 1 P 2 P 3 ...bir asal sayıya bölünebilir Q 1 ise faktörlerden en az biri, örneğin P 1 ile bölünebilir Q 1. Ancak P 1 asal bir sayıdır ve yalnızca 1'e ve kendisine bölünür. Buradan P 1 =Q 1 (çünkü Q 1 ≠1)

O zaman (2)'den hariç tutabiliriz P 1 ve Q 1:

Dolayısıyla, birinci açılımda bir veya daha fazla kez faktör olarak görünen her asal sayının, ikinci açılımda da en az aynı sayıda göründüğüne ve ikinci açılımda faktör olarak görünen herhangi bir asal sayının da tam tersi olduğuna inanıyoruz. bir veya daha fazla kez de ilk genişletmede en az aynı sayıda görünür. Dolayısıyla herhangi bir asal sayı, her iki açılımda da aynı sayıda çarpan olarak yer alır ve dolayısıyla bu iki açılım da aynıdır.■

Bileşik sayının genişletilmesi k aşağıdaki biçimde yazılabilir

Nerede P 1 , P 2, ... çeşitli asal sayılar, α, β, γ ... pozitif tamsayılar.

Genişleme (3) denir kanonik genişleme sayılar.

Asal sayılar doğal sayılar dizisinde eşit olmayan şekilde ortaya çıkar. Sıranın bazı kısımlarında daha fazlası var, diğerlerinde ise daha az. Sayı dizisinde ne kadar ilerlersek asal sayılar o kadar az yaygın olur. Şu soru ortaya çıkıyor: En büyük asal sayı var mı? Antik Yunan matematikçi Öklid sonsuz sayıda asal sayının olduğunu kanıtladı. Bu kanıtı aşağıda sunuyoruz.

Teorem 2. Asal sayıların sayısı sonsuzdur.

Kanıt. Sonlu sayıda asal sayı olduğunu varsayalım ve en büyük asal sayı olsun P. Bütün sayıları büyük sayalım P. İfadeye göre bu sayıların bileşik olması ve asal sayılardan en az birine bölünebilmesi gerekir. Tüm bu asal sayıların artı 1'in çarpımı olan bir sayı seçelim:

Sayı z Daha PÇünkü 2p zaten daha fazlası P. P bu asal sayıların hiçbirine bölünemez çünkü her birine bölündüğünde 1 kalanını verir. Böylece bir çelişkiye varırız. Bu nedenle sonsuz sayıda asal sayı vardır.

Bu teorem daha genel bir teoremin özel bir durumudur:

Teorem 3. Aritmetik bir ilerleme verilsin

Daha sonra herhangi bir asal sayı dahil N, dahil edilmelidir M, bu nedenle N dahil edilmeyen diğer temel faktörler M ve dahası, bu temel faktörler N belirtilenden daha fazla kez dahil edilmez M.

Bunun tersi de doğrudur. Bir sayının her asal çarpanı ise N sayıya en az aynı sayıda dahil edildi M, O M bölünmüş N.

İfade 3. İzin vermek A 1 ,A 2 ,A 3,... çeşitli asal sayılar dahil M Bu yüzden

Nerede Ben=0,1,...α , J=0,1,...,β , k=0,1,..., γ . Dikkat αi kabul eder α +1 değerler, β j kabul ediyor β +1 değerler, γ k kabul ediyor γ +1 değerler, ... .