Distribusi Bilangan Prima dan Teorema Bilangan Prima

Teorema bilangan prima menjelaskan secara tepat intuisi bahwa bilangan prima menipis secara logaritmik: jumlah bilangan prima hingga batas tertentu adalah asimtotik terhadap batas tersebut dibagi dengan logaritma naturalnya.

Definition

Teorema bilangan prima menyatakan bahwa jumlah bilangan prima yang tidak melebihi x, yang dilambangkan dengan pi dari x, secara asimtotik sama dengan x dibagi dengan logaritma natural dari x, atau ekuivalen dengan integral logaritmik dari x.

Scope

Topik ini mencakup fungsi penghitung bilangan prima dan asimtotiknya, batas elementer Chebyshev serta fungsi penjumlahan psi dan theta, teorema Mertens, pernyataan dan bukti analitik teorema bilangan prima melalui ketidaknolannya fungsi zeta pada garis bagian riil satu, aproksimasi logaritmik-integral, suku galat dan hubungannya dengan Hipotesis Riemann, serta celah bilangan prima dan heuristik bilangan prima kembar.

Core questions

• Bagaimana batas Chebyshev dan estimasi Mertens membatasi kepadatan bilangan prima sebelum teorema lengkap?
• Mengapa teorema bilangan prima ekuivalen dengan fungsi zeta yang tidak memiliki nol pada garis di mana bagian riilnya sama dengan satu?
• Seberapa baik aproksimasi logaritmik-integral, dan bagaimana suku galat bergantung pada Hipotesis Riemann?
• Apa yang diketahui dan diduga tentang celah antara bilangan prima berurutan, termasuk bilangan prima kembar?

Key theories

Teorema bilangan prima

Dibuktikan secara independen oleh Hadamard dan de la Vallee Poussin pada tahun 1896, teorema ini memberikan asimtotik utama untuk penghitungan bilangan prima; pernyataan yang ekuivalen untuk fungsi psi Chebyshev adalah bentuk analitik yang alami.

Daerah bebas nol dan suku galat

Ukuran daerah bebas nol untuk zeta di sebelah kiri garis bagian riil satu mengontrol galat dalam teorema bilangan prima; Hipotesis Riemann akan memberikan galat tipe akar kuadrat yang optimal.

Celah bilangan prima dan heuristik Cramer

Celah rata-rata di dekat x adalah sekitar logaritma x; heuristik probabilistik memprediksi distribusi celah besar dan kecil, dan kemajuan saringan telah membuktikan keberadaan celah terbatas yang tak terbatas.

Clinical relevance

Kepadatan bilangan prima yang diberikan oleh teorema ini memberitahu kriptografer berapa banyak kandidat acak yang harus diuji untuk menemukan bilangan prima dengan ukuran tertentu, secara langsung mengatur efisiensi pembuatan kunci RSA dan Diffie-Hellman.

History

Gauss dan Legendre mengemukakan dugaan tentang jumlah asimtotik bilangan prima sekitar tahun 1800. Chebyshev menetapkan batas atas dan bawah yang ketat pada tahun 1850-an, Riemann menguraikan strategi analitik pada tahun 1859, dan Hadamard serta de la Vallee Poussin menyelesaikan buktinya pada tahun 1896. Selberg dan Erdos kemudian memberikan bukti elementer pada tahun 1949.

Key figures

• Bernhard Riemann
• Pafnuty Chebyshev
• Jacques Hadamard
• Charles-Jean de la Vallee Poussin

Seminal works

• davenport2000

Frequently asked questions

Apakah teorema bilangan prima memungkinkan Anda memprediksi bilangan prima berikutnya?

Tidak. Teorema ini menjelaskan kepadatan rata-rata bilangan prima dalam rentang yang panjang; teorema ini tidak menentukan lokasi bilangan prima individu mana pun, dan bilangan prima tetap tidak beraturan pada skala kecil.

Bagaimana teorema ini berhubungan dengan Hipotesis Riemann?

Teorema itu sendiri tidak bersyarat, tetapi Hipotesis Riemann akan menentukan galat terkecil yang mungkin dalam aproksimasi, mengontrol seberapa jauh jumlah bilangan prima aktual dapat menyimpang dari integral logaritmik.