Bilangan prima
Sejarah

Papirus Matematika Rhind dari sekitar tahun 1550 SM, memiliki perluasan pecahan Mesir dalam bentuk yang berbeda untuk bilangan prima dan bilangan komposit. Namun, catatan sejarah pertama kali yang mempelajari bilangan prima dengan eksplisit berasal dari matematika Yunani kuno.. Elemen dari Euklides (300 SM) membuktikan bilangan prima tak-hingga dan teorema dasar aritmetika, dan menunjukkan cara membuat bilangan sempurna dari prima Mersenne. Penemuan Yunani lainnya yaitu tapis Eratosthenes masih digunakan untuk menyusun daftar bilangan prima.
Sekitar 1000 M, matematikawan Islam Ibn al-Haytham (Alhazen) menemukan teorema Wilson dengan mencirikan bilangan prima sebagai bilangan  n yang membagi rata  (n-1)!+1. Ia juga menduga bahwa semua bilangan sempurna genap berasal dari konstruksi Euklides yang menggunakan bilangan prima Mersenne, tetapi tidak dapat membuktikannya. Matematikawan Islam lainnya, Ibn al-Banna' al-Marrakushi mengamati bahwa pitas Eratosthenes dapat dipercepat dengan menguji hanya pembagi hingga akar kuadrat dari bilangan terbesar yang akan diuji. Fibonacci membawa inovasi dari matematika Islam kembali ke Eropa. Liber Abaci (1202) dalam bukunya yang pertama mendeskripsikan pembagian percobaan untuk menguji primalitas, sekali lagi menggunakan pembagi hanya akar kuadrat hingga.
Pada 1640, Pierre de Fermat menyatakan teorema kecil Fermat tanpa bukti, yang kemudian dibuktikan oleh Leibniz dan Euler. Fermat juga menyelidiki primalitas dari bilangan Fermat  2^{2^{n}}+1, dan Marin Mersenne mempelajari prima Mersenne, bilangan prima dari bentuk  2^{p}-1 dengan  p sendiri adalah bilangan prima. Dalam surat tahun 1742 untuk Euler, Christian Goldbach merumuskan konjektur Goldbach, bahwa setiap bilangan genap adalah jumlah dari dua bilangan prima. Euler membuktikan konjektur Alhazen (yang saat ini disebut teorema Euklides–Euler) bahwa semua bilangan sempurna genap dapat dibangun dari bilangan prima Mersenne. Ia memperkenalkan metode dari analisis matematis ke cabang ini dalam bukti ketakterhinggaan bilangan prima dan kedivergenan jumlah timbal-balik bilangan prima  {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots . Pada awal abad ke-19, Legendre dan Gauss menduga bahwa ketika  x menuju ke takhingga, jumlah bilangan prima hingga  x asimptotik ke  {\tfrac {x}{\log x}}, dimana  \log x melambangkan logaritma natural dari  x. Versi lemah postulat Bertrand yang mengatakan bahwa untuk setiap  n>1, terdapat bilangan prima di antara  n dan  2n, dibuktikan oleh Pafnuty Chebyshev pada tahun 1852. Gagasan Bernhard Riemann dalam makalahnya tahun 1859 tentang fungsi zeta menggambarkan sebuah garis besar dalam membuktikan konjektur Legendre dan Gauss. Walaupun gagasannya yang berkaitan dengan hipotesis Riemann masih belum terpecahkan, namun garis besar Riemann diselesaikan oleh Hadamard dan de la Vallée Poussin pada tahun 1896, dan hasilnya saat ini dikenal sebagai teorema bilangan prima. Hasil penting lainnya pada abad ke-19 adalah teorema Dirichlet tentang barisan aritmetika, barisan aritmetika pasti memuat tak berhingga banyaknya bilangan prima.
Beberapa matematikawan telah melakukan uji primalitas untuk bilangan lebih besar dari bilangan penerapan uji pembagian. Metode yang membatasi bentuk bilangan khusus di antaranya uji Pépin untuk bilangan Fermat (1877), teorema Proth (sekitar 1878), uji primalitas Lucas–Lehmer (berasal dari 1856), dan uji primalitas Lucas rampat.
Sejak tahun 1951, semua bilangan prima terbesar yang diketahui telah ditemukan menggunakan uji ini pada komputer. Pencarian bilangan prima besar telah membangkitkan minat pada luar lingkaran matematika, melalui Great Internet Mersenne Prime Search dan proyek komputasi distribusi lainnya. Gagasan bahwa bilangan prima memiliki beberapa penerapan diluar matematika murni, sekitar tahun 1970-an ketika kriptografi kunci publik dan RSA sistem kripto ditemukan dengan menggunakan bilangan prima sebagai basisnya.
Meningkatnya kepentingan praktis dari pengujian dan faktorisasi primalitas terkomputerisasi menyebabkan pengembangan metode menjadi lebih baik yang mampu menangani sejumlah besar bentuk ketakhinggaan. Teori matematika bilangan prima juga terus berkembang dengan teorema Green-Tao (2004) bahwa barisan aritmetika panjang yang cenderung dari bilangan prima, dan pembuktian pada tahun 2013 Yitang Zhang bahwa memiliki banyak uji celah prima ketakhinggaan.