Bir sayının asal olup olmadığını anlamak için ne yöntem kullanırız?

[SoruCevap]

Bir sayının asal olup olmadığını anlamak için ne yöntem kullanırız? ödevim çok acele edin ya ne olur hemen sorunun cevabını verin bana acele edin ne olur!!!!

Bir sayının asal olup olmadığını nasıl anlarız? Sayımıza n diyelim. nyi nden küçük sayılara bölmeye çalışalım. Eğer nden küçük, 1den büyük bir sayı nyi 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 olmayanP) bir arkadaşım tarafından gösterilmişti. O günü düşününce kendimden utanıyorum

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= (x1)(xa1 + xa2 + ... + 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 xin 2 olması gerekmektedir. Çünkü x = 2 iken x-1=1 olur, bu durumda (xa1 + xa2 + ... + x + 1) sayısı da xa1 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 xi 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 1e 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 1in asal olması için anı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 alar için asal olduklarını bilmiyoruz ama hangi alar için asal olamayacaklarını biliyoruz: Eğer a, 2nin 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 + 1e bölünür. Şöyle ki:

xa + 1 = (x+1)(xa1 xa2 + xa3 xa4 + ... x + 1.)

Şimdi anın bir tek sayıya bölündüğünü varsayalım. 2a + 1in asal olamayacağını kanıtlamak istiyoruz. ayı 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 + 1i böler. Yani x + 1, 2a + 1i böler. Demek ki a bir tek sayıya bölünüyorsa, 2a + 1 asal olamaz. Dolayısıyla a, 2nin 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, Mqnün asal olması için gerekli ve yeterli koşul, Mqnün Sq-1i tam bölmesidir.

Örneğin M5 = 31i kontrol edelim;

s(1) = 4
s(2) = 14
s(3) = 194
s(4) = 37634

37634 / 31 = 1214 olduğundan M5 = 31 asaldır.

M7 = 127i 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.