Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
0 beğenilme 0 beğenilmeme
769 kez görüntülendi

$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?

Orta Öğretim Matematik kategorisinde (25.3k puan) tarafından  | 769 kez görüntülendi

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 :(

1 cevap

0 beğenilme 0 beğenilmeme

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.

(2.9k puan) tarafından 
tarafından düzenlendi

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.

20,200 soru
21,728 cevap
73,275 yorum
1,887,864 kullanıcı