(Guncel) En buyuk asal sayi nasil bulundu?

Question

$22$ milyon basamaktan fazla olan bir asal sayi bulundu. Peki $22$ milyondan buyuk bir asal sayi bulabilir misiniz? Bu bile aslinda zor bir soru ki, bulunan bu sayi bilgisayar yardimi olmadan zor bulunur.

Bilgisayar yardimi disinda dikkat cekici olan bu sayinin $2^{74,207,281}-1$ olmasi.

Soru 1: Bu $74,207,281$ sayisi asal mi peki? Bence asal olmali. Peki neden?

Ilk olarak sunlari gosterelim:
1) $a,n>0$ tam sayilari icin $a^n-1$ sayisi $a-1$ sayisina tam bolunur. 
2) $a>2$ ve $n>1$ ise $a^n-1$ asal olamaz.
3) Eger $n>1$ ve $a^n-1$ asal sayi ise $a=2$ olmali, yani asal sayimiz $2^n-1$ olmali.

Peki $n$ asal olmak zorunda mi?

1) $n$ asal degilse $n$ sayisinin $1$'den buyuk, $n$'den kucuk bir tam boleni olmali. (ki asal olmasin degil mi?)
2) Bu bolene $d$ diyelim. Bu durumda $a^n-1$ sayisi $a^d-1$ sayisina tam bolunur.
3) Demek ki $a^n-1$ sayisi asal ise $n>1$ asal ve $a=2$ olmali.

Artik sunu gosterdik $n$ asal bir sayi olmazsa $2^n-1$ sayisi asal olamaz. Eger $2^{74,207,281}-1$ sayisi gercekten asal ise $74,207,281$ sayisi asal olmali.

Soru 2: Eger her asal $n$ sayisi icin $2^n-1$ sayisi asal olsaydi o zaman $p=2^{2^{74,207,281}-1}-1$ daha buyuk bir asal sayi ve $2^p-1$ daha da buyuk bir asal sayi olurdu. Adamlar da kalkip bulabildigimiz en buyugu bu demezdi. Demek ki en az bir adet $n$ asal sayisi var ki $2^n-1$ asal olmaz. Buna bir ornek bulunuz.

Soru 3: Bu sayinin $22$ milyondan fazla basamagi oldugunu nasil soyleyebiliyorlar?

Comments

Bu algoritmalar hakkında sorular sorulabilir sitede. Hem site daha güzzelleşir, hem fikrimiz daha güzele kayar.

Yukarıda polinomsal süre demişsin. Öyle bir algoritma var mı? Benim bildiğim yok.

---

Makale kuantum bilgisayar diyor. Normal bilgisayardı kastım. Eger bu bilgisayarlarla ilgili bilgin varsa şu soruya da bakabilirsin.

---

Soru 2 için dipnot: $2^{2^{74207281}-1}-1$ sayısı asal olmayan $2^p-1$ sayısının varlığından dolayı değil de mevcut bilgisayarların yetersizliğinden kaynaklanıyor da olabilir :)

---

$p$ ve $q$ asal sayılar olmak üzere $2p+1=q$ sağlanıyorsa $q$ asalı $2^p-1$ sayısını tam böler. Örneğin $\{(11,23),(23,47)\}$ ikilileri. Fakat ispatını bilmiyorum biraz uğraşmalıyım.

---

Ki $\{(2,5),(5,11)\}$ ikilileri için sağlamıyor. İspatı da yok :(

Answer 1

Soru 1 için $2^p-1$ sayısının asal olmaması için bir $q$ asalına tam bölünmesi gerekir yani $2^p \equiv 1\ (mod\ q)$ şartı sağlanmalıdır. Fermat teoreminden $2^{q-1} \equiv1\ (mod\ q)$ olduğuna göre $q-1$ sayısının $p$ asalını tam bölebilmesi gerekir. $q-1$ çift, $p$ tek sayı olduğuna göre $q-1$ sayısı $p$'yi tam bölemez. O halde çelişki elde ederiz. Yani $2^p-1$ ifadesi asaldır.

Soru 3 için $log2^{74207281}=74207281.log2=74207281.0,301=22336391,581$ olduğuna göre tamsayı kısmına $1$ eklersek $2^{74207281}$ sayısının $22336392$ basamaklı olduğunu görürüz. Virgüllü kısmı çok küçük olmadığından $2^{74207281}-1$ ifadesinin de $22336392$ basamaklı olduğunu söylemek mümkün.

Comments

Bu cevapta hatalar var. En sondaki çıkarımın yanlış olacagı da soru içerisinde ve yorumlarda verilmiş.

---

Hocam hata nerde onu merak ettim. Açıklayabilir misiniz

---

$q-1$ mertebesi olmak zorunda değil, yani en küçüğü, böleni de olabilir. Eğer $p$ asalı böleni ise mertebesi olmaya aday. Yukarıda pisayısı'nın verdiği tabloya pakabilirsin, p=11 için.