10n+1 dizisindeki sayıların asallık durumları

11 sayısı asal. 101 de öyle. İnsan bu örneklere bakarak $10 \cdots 01$ şablonundaki sayılar arasında asal olanların bulunmasını bekliyor. İtiraf etmek gerekirse ben uzun zaman 1001'in de asal olduğunu sanmıştım. Halbuki çok basit bir şekilde 1001'in 11'e bölündüğünü ispatlayabilirsiniz. Hatta küçük bir hesap makinası kullanarak $1001 = 7 \times 11 \times 13$ şeklinde asal çarpanlarına ayırabiliriz bu sayıyı. 11, 101, 1001 vb sayılar $A_{n}:= 10^{n}+1$ dizisiyle tarif edilebilirler. Burada $n>0$ olacak şekilde bir doğal sayıdır. Bu paragrafta $A_{1}=11$ ve $A_{2}=101$ sayılarının asal, $A_{3}=1001$ sayısının ise kompozit olduğunu anlattık. Bugünkü sorumuz şu:

Problem: $A_{n} := 10^{n}+1$ dizisinde 11 ve 101 haricinde başka asal sayı var mı?

1001'in çarpanlarına ayrılmasında başka bir kuraldan da faydalanabilirdik. $a^{3}+b^{3}=(a+b)(a^{2}-ab+b^{2})$ cebirsel özdeşliğini bilmeyenimiz yoktur. O zaman $1001 = 10^{3}+1=(10+1)(10^{2}-10+1)=11 \times 91$ eşitliği kolayca ortaya çıkar. Bizi 1001'de tutan hiç bir şey yok. $A_{3n}=10^{3n}+1=(10^{n}+1)(10^{2n}-10^{n}+1)$ özdeşliğini de rahatlıkla yazabiliriz. Diğer bir ifadeyle

$$\begin{equation} A_{3n} = A_{n}(A_{2n}-A_{n}+1). \end{equation}$$ Bu bize $A_{3n}$ sayısının asla asal olmadığını söylüyor. Farkında mısınız, bir kalbur yaptık!

$n \equiv 0 ({\rm mod}\ 3)$ ise, o zaman $A_{n}$ asal değildir.

Fakat bu eleğin gözenekleri yeterince ince değil. Elemanlarının asallığını incelediğimiz dizinin sadece üçte biri için kesin sonuç veriyor. Daha iyisine ihtiyacımız var. 11'e bölünebilme kuralına bir bakalım. $10^{1} \equiv -1 ({\rm mod}\ 11)$ olduğundan $10^{2n+1} \equiv -1 ({\rm mod}\ 11)$ diyebiliriz. Diğer bir ifadeyle $A_{2n+1} \equiv 0 ({\rm mod}\ 11)$ olduğundan şöyle diyebiliriz:

$n \equiv 1 ({\rm mod}\ 2)$ ise, o zaman $A_{n}$ asal değildir.

Bu da bir kalbur! Hem de $A_{n}$ dizisindeki sayıların %50'si için asallık testinde kesin sonuç veriyor.

Son iki bulgumuzu birleştirerek kolayca daha iyi bir kalbur yapabiliriz. Şu önermenin ispatını okura bir alıştırma olarak bırakıyorum. $A_{n}$ dizisindeki $A_{6n}$, $A_{6n+1}$, $A_{6n+3}$ ve $A_{6n+5}$ sayıları asal değildir. Böylece dizideki elemanların %66,67'si için asallık testinde kesin sonuç alabiliyoruz.

Daha da iyi asallık testi için dizinin elemanlarının 101 ile bölünebilme durumlarına bakacağız. (Dizinin ilk terimi 11 idi ve 11'e bölünebilme kuralı asal sayı adaylarının yarısını hemen elememizi temin etti. Umudumuz 101 ile bölünebilme kuralından da benzer bir eleme algoritması türetmektir.) Şimdi $10^{2} \equiv -1 ({\rm mod} \ 101)$ olduğundan $A_{2}$, $A_{6}$, $A_{10}$ ve genelde $A_{4n+2}$ 101 ile tam bölünür. Ama daha önce 11'e bölünebilme kuralından $A_{4n+1}$ ve $A_{4n+3}$ sayılarının da asal olmadığını biliyoruz. İşte daha iyi bir kalbur çıktı!

$n \not\equiv 0 ({\rm mod}\ 4)$ ise, o zaman $A_{n}$ asal değildir.

Bu kalbur dizideki sayıların %75'i için kesin sonuç veriyor.

Şöyle bir gözlem yapalım. 11 ile bölünebilme asal sayıları sadece $A_{2n}$ formundaki dizi elemanları arasında aramamızı söyledi. 101 ile bölünebilme ise asal olma ihtimalini $A_{4n}$ formuna daralttı. Dizinin $A_{4n}$ formundaki ilk elemanı 10.001. Bu sayı da asal değil. Çünkü $10.001 = 73 \times 137$. Burada bir genelleme yapacağız. $10^{k}\equiv -1 ({\rm mod}\ A_{k})$ oldğunundan, bütün dizideki $A_{k(2n+1)}$ sayıları $A_{k}$ ile bölünürler. O zaman asal olma şüphesi sadece $A_{k(2n)}$ formundaki sayılara aittir. Şimdi $A_{4n}$ dizisini iki alt diziye bölebiliriz: $A_{4(2n+1)}$ ve $A_{4(2n)}$. Bu alt dizilerden ilkinin asal sayı üretmeyeceğini biliyoruz. O zaman geriye ikinci alt dizi kalıyor: $A_{8n}$. Bu fikri genelleştirdiğimizde aşağıdaki önermeye ulaşıyoruz.

$A_{n}$ dizisinde $n \ne 2^{k}$ ise, o zaman $A_{n}$ asal değildir.

Diğer bir deyişle sadece $A_{2^{n}}$ formundaki sayıların asallıklarını sınamamız yeterli. İstatistiksel olarak bakıldığında en iyi ihtimalle dizinin ilk $n$ elemanından kabaca $\log _{2} n$ tanesi asal olabileceğinden, dizide asal sayı bulunma oranına getirilen üst limit $\frac{\log _{2} n}{n} \to 0$ değerine yakınsar. Uzun lafın kısası şu: verimli bir şekilde asal sayı üretmek istiyorsanız, $A_{n}$ dizisinden size ekmek yok! Ayrıca belirtelim ki şimdiye kadar elde ettiğimiz en iyi kalbur bu. Çünkü -pratik olarak- dizideki her eleman için asallık testinde kesin sonuç veriyor.

Postadaki soruya kesin cevap veremedik. Bunun için $10^{2^{n}}+1$ sayılarını çarpanlarına ayırmamız ya da asal olduklarını göstermemiz gerekiyor. Ben bu işi kolayca yapabilecek temel bir yöntem bilmiyorum. Sayısal olarak bu problem üzerinde yapılmış bazı deneyler var nette. Onlara da sonra bakalım.