Bir sayının asal olduğunu anlamak için, o sayının kendisinden ve 1'den başka tam böleni olup olmadığına bakmak gerekir. Eğer böyle bir tam bölen yoksa, o sayı asal sayıdır. Örneğin, 17 sayısı sadece 1 ve 17'ye tam bölünebildiği için asal sayıdır. Ancak, 18 sayısı 2, 3, 6 ve 9'a da tam bölünebildiği için asal sayı değildir.
Bir sayının asal olup olmadığını kontrol etmenin birkaç yöntemi vardır. En basit yöntem, sayıyı kendisinden küçük olan tüm sayılara bölmeyi denemektir. Eğer hiçbir sayıya tam bölünmezse, sayı asaldır. Bu yöntem küçük sayılar için işe yarar, ancak çok büyük sayılar için çok zaman alır. Bu yüzden, daha hızlı ve akıllıca yöntemler geliştirilmiştir. Bunlardan bazıları şunlardır:
- Sayıyı kökünden küçük olan sayılara bölmeyi denemek. Eğer kökünden küçük bir sayıya tam bölünmezse, sayı asaldır. Bu yöntem, ilk yönteme göre daha az sayıya bölme işlemi gerektirir. Örneğin, 101 sayısının asal olup olmadığını kontrol etmek için, 101'in kökü olan 10'dan küçük olan sayılara bölmeyi deneyebiliriz. 2, 3, 5 ve 7 sayılarına tam bölünmediğini görürüz. Bu durumda, 101 asal sayıdır.
- Sayıyı 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 gibi küçük asal sayılara bölmeyi denemek. Eğer bu sayılardan hiçbirine tam bölünmezse, sayı büyük bir olasılıkla asaldır. Bu yöntem, sayının küçük asal sayıların çarpımından daha büyük olması durumunda işe yarar. Örneğin, 97 sayısının asal olup olmadığını kontrol etmek için, 2 ile 37 arasındaki asal sayılara bölmeyi deneyebiliriz. Hiçbirine tam bölünmediğini görürüz. Bu durumda, 97 büyük bir olasılıkla asal sayıdır. Ancak, bu yöntem kesin bir sonuç vermez. Çünkü sayı, daha büyük bir asal sayıya tam bölünebilir. Örneğin, 143 sayısı 2 ile 37 arasındaki asal sayılara tam bölünmez, ancak 11 ve 13 sayılarına tam bölünür. Bu yüzden, 143 asal sayı değildir.
- Sayıyı 2'nin bir kuvveti eksi 1 şeklinde yazabilmek. Eğer bu şekilde yazılabilirse, sayı Mersenne asalı olarak adlandırılır ve asaldır. Bu yöntem, sayının 2'nin bir kuvveti eksi 1 şeklinde yazılabilmesi durumunda işe yarar. Örneğin, 31 sayısının asal olup olmadığını kontrol etmek için, 31'i 2'nin bir kuvveti eksi 1 şeklinde yazmaya çalışabiliriz. 31 = 2^5 - 1 şeklinde yazılabilir. Bu durumda, 31 Mersenne asalıdır ve asaldır. Ancak, bu yöntem her zaman doğru sonuç vermez. Çünkü sayı, 2'nin bir kuvveti eksi 1 şeklinde yazılsa bile, asal olmayabilir. Örneğin, 2047 sayısı 2^11 - 1 şeklinde yazılabilir, ancak 23 ve 89 sayılarına tam bölünür. Bu yüzden, 2047 asal sayı değildir.
Bu yöntemlerin dışında, daha karmaşık ve gelişmiş yöntemler de vardır. Bunlardan bazıları şunlardır:
- Fermat'ın küçük teoremini kullanmak. Bu teorem, eğer p bir asal sayı ise, herhangi bir a sayısı için a^p - a sayısının p'ye tam bölündüğünü söyler. Bu teoremi tersine çevirerek, eğer a^p - a sayısı p'ye tam bölünmüyorsa, p'nin asal olmadığını söyleyebiliriz. Örneğin, 341 sayısının asal olup olmadığını kontrol etmek için, a = 2 alalım. 2^341 - 2 sayısının 341'e tam bölünüp bölünmediğine bakalım. Bu sayıyı hesaplamak zor olduğu için, modüler aritmetik kullanarak daha kolay bir şekilde bulabiliriz. Modüler aritmetik, bir sayının başka bir sayıya bölümünden kalanı bulmaya yarayan bir yöntemdir. Bu yöntemde, bir sayının başka bir sayıya bölümünden kalanı, o sayının modülü olarak adlandırılır. Örneğin, 7'nin 3'e bölümünden kalan 1'dir. Bu durumda, 7 mod 3 = 1 şeklinde yazılır. Modüler aritmetikte, bir sayının modülünü bulmak için, o sayıyı modülü alacağımız sayıya bölerek kalanı buluruz. Örneğin, 15 mod 4 = 3 şeklinde yazılır. Çünkü 15'i 4'e bölersek, kalan 3'tür. Modüler aritmetikte, toplama, çıkarma ve çarpma işlemleri yaparken, sonucun modülünü almak için, işleme giren sayıların modüllerini alıp, işlemi onlarla yapabiliriz. Örneğin, (a + b) mod n = (a mod n + b mod n) mod n şeklinde yazılır. Bu şekilde, çok büyük sayılarla uğraşmadan, modüler aritmetik yapabiliriz. Şimdi, 2^341 - 2 sayısının 341'e bölümünden kalanı bulalım. Bunun için, 2^341 - 2 = (2^10)^34 x 2 - 2 şeklinde yazabiliriz. Bu sayının 341'e bölümünden kalanı, (2^10)^34 x 2 - 2 mod 341 şeklinde yazılabilir. Burada, 2^10 mod 341 = 16 olduğunu biliyoruz. Bu durumda, (2^10)^34 x 2 - 2 mod 341 = (16^34 x 2 - 2) mod 341 şeklinde yazılabilir. Burada, 16^34 mod 341 = 1 olduğunu biliyoruz. Bu durumda, (16^34 x 2 - 2) mod 341 = (1 x 2 - 2) mod 341 = 0 mod 341 şeklinde yazılabilir. Yani, 2^341 - 2 sayısının 341'e bölümünden kalan 0'dır. Bu durumda, Fermat'ın küçük teoremine göre, 341 asal sayı değildir.
- Miller-Rabin testi kullanmak. Bu test, bir sayının asal olup olmadığını büyük bir olasılıkla söyleyen bir testtir. Bu testte, bir sayının asal olup olmadığını, o sayıya rastgele seçilen birkaç sayıyı taban olarak alıp, bazı hesaplamalar yaparak buluruz. Eğer hesaplamaların sonucunda, sayının asal olmadığını gösteren bir kanıt bulursak, sayı asal değildir. Eğer hiçbir kanıt bulamazsak, sayı büyük bir olasılıkla.
Kaynak: Bing ile konuşma, 14.11.2023
(1) Asal Sayı Nedir, Bir Sayının Asal Olup Olmadığı Nasıl Anlaşılır? Asal .... https://www.cnnturk.com/egitim/asal-sayi-nedir-bir-sayinin-asal-olup-olmadigi-nasil-anlasilir-asal-sayilar-nelerdir.
(2) bir sayının asal olup olmadığını anlamak için kullandığınıs yöntemi ve .... https://eodev.com/gorev/114470.
(3) Asal sayılar nasıl bulunur? Asal sayılara örnekler - Mynet Eğitim. https://www.mynet.com/asal-sayilar-nasil-bulunur-asal-sayilara-ornekler-170100273596.
(4) Asal sayılar nelerdir, hangileridir? (TABLO) | Özgün Haberler. https://www.yenisafak.com/asal-sayilar-nelerdir-hangileridir-tablo-h-3890926.
(5) Getty Images. https://www.gettyimages.com/detail/photo/prime-numbers-illustration-royalty-free-image/1215123346.