Asal Sayılar

Birden ve kendisinden başka sayıya bölünmeyen sayılara asal sayı denir1. Örneğin 17 asaldır, çünkü 1 ve 17’den başka sayıya (tam olarak) bölünmez. Öte yandan 35 asal değildir, 5’e ve 7’ye bölünür. Teknik nedenlerden 1 asal kabul edilmez.

100’den küçük asalları bulmak pek zor değildir. İşte o asallar: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Demek ki 100’den küçük 25 tane asal varmış. Yani 100’den küçük rastgele seçilmiş bir sayının asal olma olasılığı 1/4’tür.

Matematiksel kanıtlar arasında bir güzellik yarışması yapılsa, Öklid’in (MÖ. 300) “sonsuz tane asal sayı vardır” önermesinin kanıtı hiç kuşkusuz ilk on sırada yer alırdı. Bu teorem Öklid’in ünlü Öğeler adlı yapıtının dokuzuncu cildinde kanıtlanır. Öklid’in teoreminin güzelliğinin göklere çıkarılmadığı ve kanıtlanmadığı popüler matematik kitabı yok gibidir. Birazdan bu güzel teoremi – ve çok daha fazlasını – kanıtlayacağız.

Bir sayının asal olup olmadığını nasıl anlarız? Sayımıza n diyelim. n’yi n’den küçük sayılara bölmeye çalışalım. Eğer n’den küçük, 1’den büyük bir sayı n’yi tam bölüyorsa, n, tanımı gereği, asal olamaz. Öyle bir sayı bulamazsak, n asaldır.

Ne var ki bu yöntemle büyük sayıların asallığına karar vermek çok zaman alır. Bu yöntem ve çeşitlemeleri dışında bir sayının asallığına karar verebilecek genel bir yöntem de bilinmemektedir. Örneğin, şu çeşitleme düşünülebilir: n’yi n’den küçük her sayıya böleceğimize, n’yi √n’den küçük sayılara bölmeye çalışabiliriz. Çünkü n = ab ve a ≥ √n ise, b ≤ √n’dir. Dolayısıyla n asal değilse, √n’den küçük bir sayıya bölünür. Böylece yapmamız gereken bölme sayısı azalır. Bir başka kolaylık da şöyle sağlanabilir: n’nin asal olup olmadığına karar vermek için n’yi √n’den küçük her sayıya bölmeye çalışacağımıza, √n’den küçük asallara bölmeye çalışmamız yeterlidir. Bu birazdan kanıtlayacağımız birinci teoremden çıkar. Böylece, n’nin asallığına karar vermek için yapmamız gereken bölme sayısı daha da azalır. Öte yandan bu yöntemi kullanabilmek için √n’den küçük asalları bilmek gerekir. Bu asalları bildiğimizi varsaysak bile, bölme sayısı gene de büyük sayılar için çok fazladır. Örneğin, n = 100.000.000.001’in asal olup olmadığını anlamaya çalıştığımızı varsayalım bir an. Eğer n asal değilse ve küçük bir asala (örneğin 97’ye) bölünebiliyorsa, n’nin asal olmadığına oldukça çabuk karar veririz. Ama ya n asalsa ya da küçük bir asala bölünmüyorsa? Onbinlerce bölme işlemi yapmamız gerekecek.

Yukarda açıkladığımız yöntem Yunanlı matematikçi Eratosthenes tarafından M.Ö. 3. yüzyılda bulunmuştur. Bu yöntemle 50 rakamlı bir sayının en gelişmiş bilgisayar yardımıyla asal olup olmadığını anlamak trilyonlarca yıl alır. Yaşam gerçekten kısa!

Bazı özel sayıların asallığına karar vermek için özel yöntemler geliştirilebilir. Örneğin son rakamı çift olan bir tek asal sayı vardır, o da 2’dir. Çünkü son rakamı çift olan bir sayı 2’ye bölünür.

Asal olmayan sayılara bir başka örnek vereyim. xa – 1 biçiminde yazılan sayılar x –1’e bölünürler:

xa – 1 = (x – 1)(xa–1 + xa–2 + ... + x + 1).

Dolayısıyla, bir a > 1 sayısı için, xa – 1 biçiminde yazılan bir sayının asal olabilmesi için x’in 2 olması gerekmektedir. Madem öyle, 2a – 1 biçiminde yazılan sayılara bakalım. Bu sayılar asal mıdır?


Sav: Eğer a asal değilse 2a – 1 de asal olamaz.

Kanıt: Bunu kanıtlamak için önce a = bc yazalım. a asal olmadığından bu eşitliği sağlayan b ve c sayıları vardır. Sonra x’i 2b olarak tanımlayıp küçük bir hesap yapalım: 2a – 1 = 2bc – 1 = (2b)c – 1 = xc – 1. Ama xc – 1 sayısının x – 1’e bölündüğünü yukarda görmüştük. Demek ki 2a – 1, x – 1’e bölünür ve asal olamaz. Dolayısıyla, 2a – 1’in asal olması için a’nın asal olması gerekmektedir. Kanıtımız bitmiştir.


Asal bir a için 2a – 1 biçiminde yazılan sayılara Mersenne sayıları denir2. Peki, a asalsa,

Ma = 2a – 1

olarak tanımlanan sayı da asal mıdır? İlk Mersenne sayılarına bakalım:

M2 = 3

M3 = 7

M5 = 31

M7 = 127

Bu sayıların herbiri asal. Ama bundan sonraki ilk Mersenne sayısı, yani M11, asal değil: M11 = 23 × 89.

Hangi asallar için Ma asaldır? Yanıt bilinmiyor.

1972’de M19937’in asal olduğunu Bryant Tuckerman bilgisayar yardımıyla keşfetti.

1975’te, on beş yaşında iki lise öğrencisi, Laura Nickel ve Curt Noll, M19937’in o zamana dek bilinen en büyük asal olduğunu bir gazeteden öğrenince, çalışmaya koyuldular ve üç yıl sonra, 1978’te, bilgisayarlarını 350 saat çalıştırdıktan sonra, M21701’in asal olduğunu buldular. Ve birdenbire ünlendiler.

Şubat 1979’da Noll, M23209’un asal olduğunu buldu.

İki ay sonra, Slowinski M44497’nin asal olduğunu gösterdi.

Mayıs 1983’te Amerikalı David Slowinski, M86243’ün asal olduğunu, bilgisayar yardımıyla tam 1 saat 3 dakika 22 saniyede kanıtladı. Ama 86.243 sihirli sayısını bulmak için aylarca uğraştı. Bilinen klasik yöntemle (yani kendisinden küçük sayılara bölmeye çalışarak) bu sayının asal olduğunu kanıtlamak, evrenin ömrünü aşardı! M86243’ün tam 25.962 rakamı olduğunu da ayrıca belirtelim. Bu kadar bozuk parayı üstüste yığsanız, para kuleniz evrenin sınırlarını aşar! [43]

Yukardaki asalı bulan Slowinski, 19 Eylül 1983’te M132049’un asal olduğunu bilgisayarlarla anladı. Bundan çok daha önce, Manfred Schroeder adlı bir matematikçi, matematiksel yöntemlerle, sezgisinin de yardımıyla, 2130.000 - 1 civarlarında bir asal olduğunu tahmin etmişti zaten.

Mart 1992’de M756839’un asal olduğu anlaşıldı.

12 Ocak 1994’te, Paul Gage ve yine David Slowinsky bilgisayar ağlarında M859433’ün asal olduğunu kanıtladıklarını duyurdular. Hesaplarını gene bilgisayarla yapmışlardı elbet.

Şimdi, So = 4, Sk+1 = Sk2 - 2 olsun. Örneğin, S1 = 42 -2 = 14’tür. Bunun gibi, S2 = S12 -2 = 142 -2 = 194’tür. Bir q asalı için, Mq’nün asal olması için gerekli ve yeterli koşul, Mq’nün Sq’yü bölmesidir. Bu teste Lucas testi denilir. Lucas testi sayesinde çok büyük asallar oldukça kolay sayılacak işlemlerle bulunabilir.

Bu sonuçlara bilgisayarlara güvenebildiğimiz derecede güvenebiliriz elbet. Bilgisayarlar da hata yaparlar!

Büyük sayıların asal olup olmadıklarını anlamak, şifreli mesajlarda (kriptoloji) çok önemlidir ve gelişmiş ülkelerin orduları bu yüzden asal sayılarla çok ilgilenirler. Gizli mesaj yollamak isteyen, mesajıyla birlikte iki büyük asal sayının çarpımını da yollar. Şifreyi çözmek için, şifreyle birlikte yollanan sayıyı bölen o iki asalı bilmek gerekir, ki bu da dışardan birisi için (sayılar büyük olduğundan) hemen hemen olanaksızdır. İki sayıyı çarpmak kolaydır ama bir sayıyı çarpanlarına ayırmak çok daha zordur.

Şifrelemede Mersenne sayıları kullanılmaz. Çünkü az sayıda (30 küsur tane olmalı) asal Mersenne sayısı bilindiğinden, şifreyle birlikte yollanan sayının asal bir Mersenne sayısına bölünüp bölünmediğini anlamak kolaydır.

Asal olmayan bir sayıyı bölenlerine ayırmanın Fermat’nın bulduğu şu yöntem vardır. Eğer n sayısı iki pozitif doğal sayı için x2 - y2 biçiminde yazılıyorsa, o zaman,

n = (x - y)(x + y)

eşitliği doğrudur ve x, y +1 olmadığı sürece, n’yi çarpanlarına ayırmış oluruz. Bunun tersi de aşağı yukarı doğrudur. Eğer n = ab ise ve n çift değilse, o zaman,

x =

ve

y = -

alarak, n = x2 - y2 eşitliğini elde ederiz. Demek ki, çift olmayan bir n doğal sayısını çarpanlarına ayırmak için, n = x2 - y2 eşitliğini sağlayan x ve y bulmalıyız. Bu eşitlik yerine y2 = x2 - n yazalım ve x yerine teker teker sayıları koyup x2 - n sayısını hesaplayalım. Bu sayı tam bir kare (y2) olduğunda n = x2 - y2 eşitliğini bulmuş oluruz. Elbette x’in √n’den büyük olması gerekmektedir, yoksa x2 - n pozitif bile olamaz. Ayrıca, x2 - n sayısının tam bir kare olması için 0, 1, 4, 5, 6 ve 9’la bitmesi gerekmektedir, 2, 3, 7 ve 8’le biten sayılar kare olamazlar.

Bu yöntemi n = 91 için deneyelim. x > √91 olması gerektiğinden, x = 10’dan başlamalıyız. x = 10 ise, x2 - n = 102 - 91 = 9 = 32 dir ve y = 3 olabilir. Demek ki,

91 = n = 102 - 32 = (10 - 3)(10 + 3) = 7 × 13

eşitliği geçerlidir.

Aynı yöntemi n = 143 için deneyecek olursanız, gene yanıtı hemen bulursunuz: x = 12, y = 1.

Mersenne sayılarına çok benzeyen başka sayılara bakalım. 2a + 1 biçiminde yazılan sayılar asal mıdır? Bu sayıların hangi a’lar için asal olduklarını bilmiyoruz ama hangi a’lar için asal olamayacaklarını biliyoruz: Eğer a, 2’nin bir gücü değilse, yani 2n biçiminde yazılamazsa, bu sayılar asal olamazlar. Bunu birazdan kanıtlayacağız (Teorem 9.) Fermat,

Fn =

biçiminde yazılan bütün sayıların asal olduklarını sanıyordu. Bu yüzden bu sayılara Fermat sayıları denir. Gerçekten de ilk beş Fermat sayısı,

Fo = 3

F1 = 5

F2 = 17

F3 = 257

F4 = 65537

asaldır. Fermat, bütün Fermat sayılarının asal olduklarını kanıtlamaya uğraştı ama başaramadı. Başarısızlığının nedeni vardı: Sanısı doğru değildi. F5 asal değildir. F5 on basamaklı bir sayı olduğundan asallığını kanıtlamak kolay değildi. Euler (1707-1783), F5’in 641’e bölündüğünü gösterdi:

F5 = 641 × 6700417.

Demek ki a = 2n biçiminde yazılabilse bile, 2a + 1 asal olmayabiliyor.

Lucas F6’nın asal olmadığını kanıtladı. Daha sonra, 1880’de, Landry,

F6 = 274177 × 67280421310721

eşitliğini buldu. F7 ve F8 de asal değiller. Bu sayıların asal olmadıkları, çok geç bir tarihte, 1970 ve 1981’de anlaşıldı. W. Keller, 1980’de F9448’in asal olmadığını gösterdi. Bu sayı 19 × 29450 + 1’e bölünür. 1984’de gene W. Keller, F23471’in asal olmadığını kanıtladı. Bu sayının 107000’den fazla basamağı vardır ve 5 × 223473 + 1’e bölünür.

n ≥ 5 için, asal bir Fn’nin olup olmadığı şimdilik bilinmiyor. Asallığı bilinmeyen en küçük Fermat sayıları şunlar: F22, F24, F28.

Son yıllarda bir sayının asallığına yüzde olarak oldukça çabuk karar verebilen yöntemler geliştirildi. Örneğin, “Şu sayı yüzde 99,978 olasılıkla asaldır,” gibi önermeler bilgisayarların yardımıyla oldukça kısa sayılabilecek zamanda kanıtlandı. Bu konuda bilgim kısıtlı olduğundan daha fazla söz söyleyemeyeceğim.

11, 111, 1111, 11111 gibi her rakamı 1 olan sayılar asal mıdır? İçinde n tane 1 olan sayıya Bn diyelim. Eğer çift sayıda 1 varsa, yani n çiftse, Bn, 11’e bölünür ve B2 dışında bunlardan hiçbiri asal olamaz. Eğer n üçe bölünüyorsa Bn de üçe bölünür ve asal olamaz.

Hangi n’ler için Bn asaldır? Bu asallardan kaç tane vardır? B2, B19, B23, B317, B1031 asal sayılar, bu biliniyor. Bunlardan başka? Ben bilmiyorum. Bu sayılardan daha büyük bir asal varsa, n > 10.000 olması gerektiğini Harvey Dubner adlı biri kanıtlamış, daha doğrusu hesaplamış. [43]


Asallar matematikte çok önemlidir elbet. Bu yazıda bu önemli konuda bir iki teorem kanıtlayacağız. İlk teoremimizi okurların çoğu biliyordur.


Teorem 1. 1’den büyük her sayı3 bir asala bölünür.


Kanıt: Bunun kanıtı oldukça kolaydır: a > 1 bir sayı olsun. a’nın bir asala bölündüğünü kanıtlamak istiyoruz.

Eğer a asalsa bir sorun yok: a, a’yı böler ve teoremimiz kanıtlanmış olur (a bir asala (kendisine!) bölünür.)

Eğer a asal değilse, a’yı bölen ve 1 < b < a eşitsizliklerini sağlayan bir b vardır. Eğer b asalsa bir sorun yok: b, a’yı böler ve teoremimiz kanıtlanmış olur.

Eğer b asal değilse, b’yi (ve dolayısıyla a’yı da) bölen ve 1 < c < b eşitsizliklerini sağlayan bir c vardır. Eğer c asalsa bir sorun yok: c, a’yı böler ve teoremimiz kanıtlanmış olur.

Eğer c asal değilse, c’yi (ve dolayısıyla a’yı da) bölen ve 1 < d < c eşitsizliklerini sağlayan bir d vardır. Eğer d asalsa bir sorun yok: d, a’yı böler ve teoremimiz kanıtlanmış olur.

Eğer d asal değilse.......

Nereye dek gidebiliriz? Bulacağımız her sayı bir öncekinden küçük ve 1’den büyük olduğundan sonsuza dek bunu böyle sürdüremeyiz. Bir zaman sonra durmalıyız, yani bir zaman sonra a’yı bölen bir asal buluruz. Teoremimiz kanıtlanmıştır. ?


Birazdan yukarda güzelliğinden sözettiğimiz Öklid Teoremini kanıtlayacağız: Sonsuz tane asal sayı vardır. Aynı yöntemle başka sonuçlar da çıkaracağız. İlk önce biraz ilkokul aritmetiği yapalım.

Eğer a ve b sayıları n’ye bölünüyorsa, bu iki sayının toplamı da n’ye bölünür. Örneğin hem 78, hem 66 üçe bölündüğünden, 78 + 66 da, yani 144 de, üçe bölünür.

Öte yandan eğer a ve b sayılarından yalnızca biri n’ye bölünüyor, öbürü bölünmüyorsa, bu iki sayının toplamı n’ye bölünmez. Örneğin 78 üçe bölünür, 67 bölünmez. Dolayısıyla 78 + 67 üçe bölünmez.

Bir üst paragraftaki b’yi 1 olarak alırsak, a’yı bölen 1’den büyük bir sayının a + 1’i bölemeyeceği çıkar. Demek ki a ve a+1 sayılarının 1’den başka ortak böleni yoktur.

Hem ikiye, hem de üçe bölünen bir sayıya 1 eklersek, elde ettiğimiz sayı ne ikiye ne de üçe bölünür. Bunun gibi, 2 × 3 × 4 × 5 × 6 × 7, yani 5040, 2’ye, 3’e, 4’e, 5’e, 6’ya, 7’ye bölünür, ama bu sayıya 1 ekleyerek elde ettiğimiz 5041, bunlardan hiçbirine bölünmez.

Aynı şey a ve a – 1 sayıları için de geçerlidir. Örneğin, 5040’ı bölen 1’den büyük hiçbir sayı 5039’u bölemez.

5039 ve 5041 sayılarının 7 ve 7’den küçük hiçbir asala bölünmediklerini gördük. Öte yandan, Teorem 1’e göre, bu sayılardan herbiri bir asala bölünmeli. Demek ki 7’den büyük bir asal vardır. Bunun gibi 2’yle 11 arasındaki sayıların çarpımına 1 eklersek, elde edilen sayı bir asala bölünür ve bu asal 11’den büyük olmak zorundadır. Bu akıl yürütmeyi genelleştireceğiz:


Teorem 2. Sonsuz tane asal sayı vardır.


Kanıt: n > 1 herhangi bir sayı olsun. 2’den n’ye kadar bütün sayıları birbiriyle çarpalım: 2 × 3 × ... × (n–2) × (n–1) × n. Kocaman bir sayı elde ettik. Bu sayı n! olarak simgelenir. n! sayısı n + 1’den küçük bütün sayılara bölünür elbet, çünkü n! bu sayıların çarpımı. Demek ki n! + 1 sayısı 1’le n arasındaki hiçbir sayıya bölünemez. Öte yandan, Teorem 1’e göre n! + 1 sayısı bir asala bölünmeli. Demek ki n’den büyük bir asal vardır.

Ne bulduk? Her sayıdan büyük bir asal bulduk. Dolayısıyla sonsuz tane asal vardır, çünkü her asaldan büyük bir başka asal vardır. İkinci teorem kanıtlanmıştır. ?


Ne denli yalın bir kanıt değil mi? Ve şaşırtıcı. Şu nedenden şaşırtıcı: Kanıt, n’den sonra gelen ilk asalı bulmuyor; yalnızca n’den büyük bir asalın varlığı kanıtlanıyor. Örneğin 1 milyondan büyük bir asal vardır. Hangi asal? Yanıt yok! Kanıt, hangi asalın 1 milyondan büyük olduğunu göstermiyor. “Öyle bir asal var” demekle yetiniyor.

Aslında kanıtımız n’den büyük asallar üzerine hiç de bilgi vermiyor değil. En azından, her n için, n < p ≤ n! + 1 eşitsizliklerini sağlayan bir p asalının olduğunu kanıtlıyor.