bir sayının asal olup olmadığını anlamak için kullandığınıs yöntemi ve asak sayıların diğer sayılardan farkını açıklayınıs [ne olur cok acil
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. Tabi çok yüksek basamaklı sayılar için bunu yapmak çok zordur(bilgisayarlar için bile). Şöyle bir yöntem daha kolay olabilir. N sayısını kök n den küçük sayılara bölmeyi düşünebiliriz. Çünkü eğer n=a.b şeklinde asal çarpanlarına ayrılabiliyorsa a<kök n<b eşitliğini sağlamak zorundadır(tabi n tam kare değilse bu durumda a=b=kök n olur ki o zamanda n asal olmaz). Biz de bu durumda daha az sayıya bölme işlemi uygulayabiliriz. Yine de çok yüksek sayılar için, mesela 1000001 sayısının asal olup olmadığını kontrol etmek için 1001den küçük asal sayılara bölme işlemi uygulamamız gerekiyor. 1001dem küçük 186 tane asal olduğunu düşünecek olursak baya bir işlem yapmamız lazım. Sayının daha da yukarılara çıktığını düşünürsek işlem sayısı ve vakitte artacak tabi(merak edenler için 1000001 asal değil 101x9901 e eşit).
Bu yöntem M.Ö. 3. yüzyılda bulunmuş. Bana da lisedeyken ismi lazım olmayan(:P) bir arkadaşım tarafından gösterilmişti. O günü düşününce kendimden utanıyorum :P
Bazı özel durumlar içinde sayıların asal olup olmadığına karar verilebilir. En önemlisi ve asal sayılarla ilgili az çok bilgisi olan herkesin bildiği, çift sayıların(tabiî ki 2 hariç) asal olmadığı… Çünkü çift sayılar 2nin katlarıdır ve 2 ile bölünürler doğal olarakta asal olamazlar.
xa-1 şeklinde yazılan sayılara bakmak lazım. xa-1 şeklindeki sayılar (x-1)e bölünürler.
xa -1= (x–1)(xa–1 + xa–2 + ... + x + 1)
Bu durum da 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. Çünkü x = 2 iken x-1=1 olur, bu durumda (xa–1 + xa–2 + ... + x + 1) sayısı da xa–1 e eşit olur. Bu durumda bizimde 2a – 1biçiminde yazılabilen sayılara bakmamız gerekir.
Teorem: Eğer a asal değilse 2a – 1 de asal olamaz.
İspat: Öncelikle 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 söylemiştik. Bu durumda (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.
Asal bir a için 2a – 1 biçiminde yazılan sayılara Mersenne sayıları denir.
Ma = 2a – 1 şeklinde tanımlanan Mersenne sayıları asal mıdır? Hemen bakalım;
M2 = 3
M3 = 7
M5 = 31
M7 = 127
Her şey güzel gözüküyor. Ancak bir sonraki Mersenne sayısı yani M11=2047 asal değil. Kendisi 23 ile 89 çarpımı…
Hangi asallar için Ma asaldır? Şimdilik bir cevap yok.
Mersenne sayılarına çok benzeyen, 2a + 1 şeklinde yazılan sayılara bakalım. Bunlar asal mıdırlar? 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 kuvveti değilse, yani 2n biçiminde yazılamazsa, bu sayılar asal olamazlar.
İspat: Öncelikle şunu belirtelim; x herhangi bir sayı ve a > 1 bir tek sayıysa, xa + 1 sayısı asal olamaz, çünkü x + 1’e bölünür. Şöyle ki:
xa + 1 = (x+1)(xa–1 – xa–2 + xa–3 – xa–4 + ... – x + 1.)
Şimdi a’nın bir tek sayıya bölündüğünü varsayalım. 2a + 1’in asal olamayacağını kanıtlamak istiyoruz. a’yı bölen tek sayıya m diyelim. Demek ki a = nm ve m bir tek sayı. x = 2n olsun. Bu durumda:
2a + 1 = 2nm + 1 = (2n)m + 1 = xm + 1.
m tek olduğundan, x + 1, xm + 1’i böler. Yani x + 1, 2a + 1’i böler. Demek ki a bir tek sayıya bölünüyorsa, 2a + 1 asal olamaz. Dolayısıyla a, 2’nin bir katı olmalı.
İspatladığımıza göre geri dönelim. 22n +1 şeklinde yazılan sayılar asal mıdırlar? Fermat bu
sayıların asal olduklarını sanıyordu. Bu yüzden bu sayılara Fermat sayıları denir. Gerçektente ilk beş Fermat sayısı asaldır;
Fo = 3
F1 = 5
F2 = 17
F3 = 257
F4 = 65537
Fermat, bütün Fermat sayılarının asal olduklarını kanıtlamaya uğraştı ama başaramadı. Çünkü Fermat sayılarının hepsi asal değildi. Euler, F5 = 4294967297nin 641e bölündüğünü gösterdi. Daha sonra zaman içinde diğer Fermat sayılarının da asal olmadığı gösterildi. Şu anda ilk beş Fermat sayısı dışında bilinen başka asal Fermat sayısı yok. Asallığı bilinmeyen en küçük Fermat sayıları ise F22, F24, F28
Son olarakta Lucas Testinden bahsedicem. Özellikle Mersenne sayılarının asal olup olmadıklarını inceleme de büyük kolaylıklar sağlıyor. Peki Lucas Testi nedir? S1 = 4, Sk+1 = Sk2 - 2 olsun. q asalı için, Mq’nün asal olması için gerekli ve yeterli koşul, Mq’nün Sq-1’i tam bölmesidir.
Örneğin M5 = 31’i kontrol edelim;
s(1) = 4
s(2) = 14
s(3) = 194
s(4) = 37634
37634 / 31 = 1214 olduğundan M5 = 31 asaldır.
M7 = 127’i kontrol edelim;
s(1) = 4
s(2) = 14
s(3) = 194
s(4) = 37634
s(5) = 1416317954
s(6) = 2005956546822746114
2005956546822746114 / 127 = 15794933439549182 olduğundan M7 = 127 asaldır.