Bilangan prima: Perbedaan antara revisi

[[Berkas:Primes-vs-composites.svg|al=Groups of two to twelve dots, showing that the composite numbers of dots (4, 6, 8, 9, 10, and 12) can be arranged into rectangles but prime numbers cannot|jmpl|Bilangan komposit dapat disusun menjadi [[persegi panjang]], sedangkan bilangan prima tidak dapat.]]

 

Sifat-sifat yang menjadikan bilangan prima disebut '''primalitas'''. Metode sederhana namun lambat yang memeriksa primalitas untuk bilangan <math>n</math>, disebut [[pembagian percobaan]]. Metode ini menguji apakah <math>n</math> kelipatan dari suatu bilangan bulat antara <math>2</math> dan <math>\sqrt{n}</math>. Algoritma lebih cepatnya adalah [[uji primalitas Miller–Rabin]], algoritma cepat namun memiliki kesempatan galat kecil; dan [[uji primalitas Agrawal–Kayal–Saxena]], algoritma yang selalu memberikan solusi yang benar dalam [[waktu polinomial]], namun sangat lambat bila dipraktekkan. Metode cepat khususnya tersedia dalam bilangan bentuk khusus, seperti [[bilangan Mersenne]]. Hingga pada Desember 2018, [[bilangan prima terbesar yang diketahui]] merupakan [[bilangan prima Mersenne]] dengan 24.862.048 [[digit]].<ref>{{Cite web|title=51st Known Mersenne Prime Discovered|url=https://www.mersenne.org/primes/press/M82589933.html|website=www.mersenne.org|access-date=21 Desember 2018}}</ref>

 

 

Beberapa masalah-masalah bersejarah yang melibatkan bilangan prima masih belum terpecahkan. Masalah di antaranya [[konjektur Goldbach]], yang menyatakan bahwa setiap bilangan bulat lebih besar dari 2 dapat dibentuk sebagai jumlah dua bilangan prima, dan [[konjektur bilangan prima kembar]], menyatakan bahwa ada tak berhingga banyaknya pasangan bilangan prima yang memiliki sebuah bilangan genap di antaranya. Masalah-masalah tersebut mendorong pengembangan berbagai cabang dalam teori bilangan, yang fokus pada aspek bilangan [[Teori bilangan analitik|analitik]] atau bilangan [[Teori bilangan aljabar|aljabar]]. Dalam kehidupan sehari-hari, bilangan prima dipakai dalam [[teknologi informasi]], seperti [[kriptografi kunci publik]], yang bergantung pada kesulitan memfaktorkan bilangan yang lebih besar menjadi faktor bilangan prima. Dalam [[aljabar abstrak]], objek yang umumnya berperilaku sebagai bilangan prima di antaranya [[elemen bilangan prima]] dan [[ideal bilangan prima]].

 

== Definisi dan contoh ==

[[Berkas:Prime_number_Cuisenaire_rods_7.png|jmpl|260x260px|Gambaran melalui [[batang Cuisenaire]] bahwa 7 adalah bilangan prima. Karena 2, 3, 4, 5, atau 6 yang tidak dapat membagi 7 secara merata.]]

[[Pembagi]] bilangan asli <math>n</math> adalah bilangan asli yang membagi <math>n</math> sama rata. Pembagi pada setiap bilangan asli tersebut adalah 1 dan dirinya sendiri. Jika <math>n</math> memiliki pembagi lain, maka <math>n</math> bukanlah bilangan prima. Gagasan ini merujuk ke sebuah definisi bilangan prima yang berbeda namun ekuivalen: terdapat bilangan setidaknya dua pembagi bilangan positif, 1 dan dirinya sendiri.<ref>[[Underwood Dudley|Dudley, Underwood]] (1978). "[https://books.google.co.id/books?id=tr7SzBTsk1UC&pg=PA10&redir_esc=y#v=onepage&q&f=false Section 2: Unique factorization]". ''[[iarchive:elementarynumber00dudl 0/page/10/mode/2up|Elementary number theory]]'' (2nd ed.). W.H. Freeman and Co. hlm. [[iarchive:elementarynumber00dudl 0/page/10/mode/2up|10]]. ISBN 978-0-7167-0076-0.</ref> Ada cara lain untuk menjelaskan hal tersebut, yaitu: <math>n</math> adalah bilangan prima jika <math>n</math> lebih besar dari 1 dan tidak ada bilangan <math>2,3,\dots,n-1</math> yang membagi <math>n</math> sama rata.<ref>[[Waclaw Sierpiński|Sierpiński, Wacław]] (1988). ''[https://books.google.co.id/books?id=ktCZ2MvgN3MC&pg=PA113&redir_esc=y#v=onepage&q&f=false Elementary Theory of Numbers]''. North-Holland Mathematical Library. '''31''' (2nd ed.). Elsevier. hlm. 113. ISBN 978-0-08-096019-7.</ref>

[[Papirus Matematika Rhind]] dari sekitar tahun 1550 SM, memiliki perluasan [[pecahan Mesir]] dalam bentuk yang berbeda untuk bilangan prima dan bilangan komposit.<ref>Bruins, Evert Marie, review in ''Mathematical Reviews'' of {{cite journal | last = Gillings | first = R.J. | doi = 10.1007/BF01307175 | journal = Archive for History of Exact Sciences | mr = 0497458 | pages = 291–298 | title = The recto of the Rhind Mathematical Papyrus. How did the ancient Egyptian scribe prepare it? | volume = 12 | issue = 4 | year = 1974| s2cid = 121046003 }}</ref> Namun, catatan sejarah pertama kali yang mempelajari bilangan prima dengan eksplisit berasal dari [[matematika Yunani kuno]].. ''[[Elemen Euklides|Elemen]]'' dari [[Euklides]] (300 SM) membuktikan [[bilangan prima tak-hingga]] dan [[teorema dasar aritmetika]], dan menunjukkan cara membuat [[bilangan sempurna]] dari [[prima Mersenne]].<ref name="stillwell-2010-p40">{{cite book|title=Mathematics and Its History|series=Undergraduate Texts in Mathematics|first=John|last=Stillwell|author-link=John Stillwell|edition=3rd|publisher=Springer|year=2010|isbn=978-1-4419-6052-8|page=40|url=https://books.google.com/books?id=V7mxZqjs5yUC&pg=PA40}}</ref> Penemuan Yunani lainnya yaitu [[tapis Eratosthenes]] masih digunakan untuk menyusun daftar bilangan prima.<ref name="pomerance-sciam">{{cite journal|title=The Search for Prime Numbers|first=Carl|last=Pomerance|author-link=Carl Pomerance|journal=[[Scientific American]]|volume=247|issue=6|date=December 1982|pages=136–147|jstor=24966751|doi=10.1038/scientificamerican1282-136|bibcode=1982SciAm.247f.136P}}</ref><ref name="mollin">{{cite journal | last = Mollin | first = Richard A. | doi = 10.2307/3219180 | issue = 1 | journal = Mathematics Magazine | mr = 2107288 | pages = 18–29 | title = A brief history of factoring and primality testing B. C. (before computers) | volume = 75 | year = 2002| jstor = 3219180 }}</ref>

 

 

Pada 1640, [[Pierre de Fermat]] menyatakan [[teorema kecil Fermat]] tanpa bukti, yang kemudian dibuktikan oleh [[Gottfried Wilhelm Leibniz|Leibniz]] dan [[Leonhard Euler|Euler]].<ref>{{harvnb|Sandifer|2007}}, [https://books.google.com/books?id=sohHs7ExOsYC&pg=PA45 8. Fermat's Little Theorem (November 2003), hal. 45]</ref> Fermat juga menyelidiki primalitas dari [[bilangan Fermat]] <math>2^{2^n}+1</math>,<ref>{{cite book|title=How Euler Did Even More|first=C. Edward|last=Sandifer|publisher=Mathematical Association of America|year=2014|isbn=978-0-88385-584-3|page=42|url=https://books.google.com/books?id=3c6iBQAAQBAJ&pg=PA42}}</ref> dan [[Marin Mersenne]] mempelajari [[prima Mersenne]], bilangan prima dari bentuk <math>2^p-1</math> dengan <math>p</math> sendiri adalah bilangan prima.<ref>{{cite book|title=Elementary Number Theory with Applications|first=Thomas|last=Koshy|publisher=Academic Press|year=2002|isbn=978-0-12-421171-1|page=369|url=https://books.google.com/books?id=-9pg-4Pa19IC&pg=PA369}}</ref> Dalam surat tahun 1742 untuk Euler, [[Christian Goldbach]] merumuskan [[konjektur Goldbach]], bahwa setiap bilangan genap adalah jumlah dari dua bilangan prima.<ref>{{cite book|title=Goldbach Conjecture|edition=2nd|volume=4|series=Series In Pure Mathematics|first=Wang|last=Yuan|publisher=World Scientific|year=2002|isbn=978-981-4487-52-8|page=21|url=https://books.google.com/books?id=g4jVCgAAQBAJ&pg=PA21}}</ref> Euler membuktikan konjektur Alhazen (yang saat ini disebut [[teorema Euklides–Euler]]) bahwa semua bilangan sempurna genap dapat dibangun dari bilangan prima Mersenne.<ref name="stillwell-2010-p40"/> Ia memperkenalkan metode dari [[analisis matematis]] ke cabang ini dalam bukti ketakterhinggaan bilangan prima dan [[kedivergenan jumlah timbal-balik bilangan prima]] <math>\tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{5}+\tfrac{1}{7}+\tfrac{1}{11}+\cdots</math>.<ref>{{cite book|last=Narkiewicz|first=Wladyslaw|year=2000|title=The Development of Prime Number Theory: From Euclid to Hardy and Littlewood|publisher=Springer|isbn=978-3-540-66289-1|series=Springer Monographs in Mathematics|page=11|contribution=1.2 Sum of Reciprocals of Primes|contribution-url=https://books.google.com/books?id=VVr3EuiHU0YC&pg=PA11}}</ref> Pada awal abad ke-19, Legendre dan Gauss menduga bahwa ketika <math>x</math> menuju ke takhingga, jumlah bilangan prima hingga <math>x</math> [[Analisis asimptotik|asimptotik]] ke <math>\tfrac{x}{\log x}</math>, dimana <math>\log x</math> melambangkan [[logaritma natural]] dari <math>x</math>. Versi lemah [[postulat Bertrand]] yang mengatakan bahwa untuk setiap <math>n > 1</math>, terdapat bilangan prima di antara <math>n</math> dan <math>2n</math>, dibuktikan oleh [[Pafnuty Chebyshev]] pada tahun 1852.<ref>{{cite journal|last=Tchebychev|first=P.|author-link=Pafnuty Chebyshev|year=1852|title=Mémoire sur les nombres premiers.|url=http://sites.mathdoc.fr/JMPA/PDF/JMPA_1852_1_17_A19_0.pdf|journal=Journal de mathématiques pures et appliquées|series=Série 1|language=fr|pages=366–390}}. (Proof of the postulate: 371–382). Also see Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, pp. 15–33, 1854</ref> Gagasan [[Bernhard Riemann]] dalam [[On the Number of Primes Less Than a Given Magnitude|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 [[Jacques Hadamard|Hadamard]] dan [[Charles Jean de la Vallée-Poussin|de la Vallée Poussin]] pada tahun 1896, dan hasilnya saat ini dikenal sebagai [[teorema bilangan prima]].<ref>{{cite book|last=Apostol|first=Tom M.|year=2000|title=Number Theory|location=Basel|publisher=Birkhäuser|editor1-last=Bambah|editor1-first=R.P.|series=Trends in Mathematics|pages=1–14|contribution=A centennial history of the prime number theorem|mr=1764793|author-link=Tom M. Apostol|editor2-last=Dumir|editor2-first=V.C.|editor3-last=Hans-Gill|editor3-first=R.J.|contribution-url=https://books.google.com/books?id=aiDyBwAAQBAJ&pg=PA1}}</ref> Hasil penting lainnya pada abad ke-19 adalah [[teorema Dirichlet tentang barisan aritmetika]], [[barisan aritmetika]] pasti memuat tak berhingga banyaknya bilangan prima.<ref>{{cite book|last=Apostol|first=Tom M.|year=1976|title=Introduction to Analytic Number Theory|location=New York; Heidelberg|publisher=Springer-Verlag|pages=146–156|contribution=7. Dirichlet's Theorem on Primes in Arithmetical Progressions|mr=0434929|author-link=Tom M. Apostol|contribution-url=https://books.google.com/books?id=3yoBCAAAQBAJ&pg=PA146}}</ref>

 

 

Sejak tahun 1951, semua [[bilangan prima terbesar yang diketahui]] telah ditemukan menggunakan uji ini pada [[komputer]].{{efn|Sebuah bilangan prima 44-digit yang ditemukan pada tahun 1951 oleh Aimé Ferrier dengan kalkulator mekanik tetap merupakan bilangan prima terbesar yang tidak ditemukan dengan bantuan komputer elektronik.<ref>{{cite book|title=The Once and Future Turing|first1=S. Barry|last1=Cooper|first2=Andrew|last2=Hodges|publisher=Cambridge University Press|year=2016|isbn=978-1-107-01083-3|pages=37–38|url=https://books.google.com/books?id=h12cCwAAQBAJ&pg=PA37}}</ref>}} Pencarian bilangan prima besar telah membangkitkan minat pada luar lingkaran matematika, melalui [[Great Internet Mersenne Prime Search]] dan proyek [[komputasi distribusi]] lainnya.<ref name="ziegler2" /><ref>{{harvnb|Rosen|2000}}, hal. 245.</ref> Gagasan bahwa bilangan prima memiliki beberapa penerapan diluar [[matematika murni]],{{efn|name="pure"|Misalnya, Beiler menulis bahwa ahli teori bilangan [[Ernst Kummer]] menyukai [[bilangan ideal]] miliknya, yang terkait erat dengan bilangan prima, "karena mereka tidak mengotori diri mereka dengan aplikasi praktis apa pun",<ref>{{cite book|title=Recreations in the Theory of Numbers: The Queen of Mathematics Entertains|first=Albert H.|last=Beiler|year=1999|publisher=Dover|orig-year=1966|isbn=978-0-486-21096-4|page=2|url=https://books.google.com/books?id=NbbbL9gMJ88C&pg=PA2|oclc=444171535}}</ref> bahkan Katz menulis bahwa [[Edmund Landau]] yang dikenal karena karyanya tentang distribusi bilangan prima yaitu "''loathed practical applications of mathematics''" dan untuk alasan tersebut untuk menghindari subjek seperti [[geometri]] yang telah terbukti berguna.<ref>{{cite journal | last = Katz | first = Shaul | doi = 10.1017/S0269889704000092 | issue = 1–2 | journal = Science in Context | mr = 2089305 | pages = 199–234 | title = Berlin roots&nbsp;– Zionist incarnation: the ethos of pure mathematics and the beginnings of the Einstein Institute of Mathematics at the Hebrew University of Jerusalem | volume = 17 | year = 2004| s2cid = 145575536 }}</ref>}} sekitar tahun 1970-an ketika [[kriptografi kunci publik]] dan [[RSA (sistem kripto)|RSA]] sistem kripto ditemukan dengan menggunakan bilangan prima sebagai basisnya.<ref name="ent-7">{{cite book|title=Elementary Number Theory|series=Textbooks in mathematics|first1=James S.|last1=Kraft|first2=Lawrence C.|last2=Washington|publisher=CRC Press|year=2014|isbn=978-1-4987-0269-0|page=7|url=https://books.google.com/books?id=4NAqBgAAQBAJ&pg=PA7}}</ref>

=== Rumus untuk bilangan prima ===

{{Main|Rumus untuk bilangan prima}}

 

Contoh rumus yang menghasilkan bilangan prima lainnya berasal dari [[teorema Mills]] dan teorema [[E. M. Wright|Wright]]. Rumus ini mengatakan bahwa terdapat suatu konstanta real <math>A > 1</math> dan <math>\mu</math> sehingga

===Aritmetika modular dan medan berhingga===

{{Main|Aritmetika modular}}

Bilangan asli lainnya dapat dipetakan ke dalam sistem ini dengan menggantinya dengan sisa setelah pembagian dengan <math>n</math>.<ref>{{harvtxt|Kraft|Washington|2014}}, [https://books.google.com/books?id=VG9YBQAAQBAJ&pg=PA96 Proposisi 5.3], hal. 96.</ref> Penjumlahan, pengurangan, dan perkalian modular dihitung dengan melakukan penggantian yang sama dengan sisa hasil penjumlahan, pengurangan, atau perkalian bilangan bulat.<ref>{{cite book|title=Algebra in Action: A Course in Groups, Rings, and Fields|volume=27|series=Pure and Applied Undergraduate Texts|first=Shahriar|last=Shahriari|author-link= Shahriar Shahriari |publisher=American Mathematical Society|year=2017|isbn=978-1-4704-2849-5|pages=20–21|url=https://books.google.com/books?id=GJwxDwAAQBAJ&pg=PA20}}</ref> Kesamaan bilangan bulat sesuai dengan ''kongruensi'' dalam aritmetika modular:

 

Beberapa teorema tentang bilangan prima dirumuskan menggunakan aritmetika modular. Misalnya, [[teorema kecil Fermat]] menyatakan bahwa jika <math>a\not\equiv 0</math> (mod <math>p</math>), maka <math>a^{p-1}\equiv 1</math> (mod <math>p</math>).<ref>{{harvnb|Ribenboim|2004}}, Teorema kecil Fermat dan akar primitif modulo a prima, hal. 17–21.</ref> Menjumlahkan dari semua pilihan <math>a</math> diberikan persamaan

===Bilangan ''p''-adik===

{{main|bilangan P-adik}}

 

Urutan dari sebuah gambar, nilai absolut, dan medan lengkap yang diturunkan dari bilangan <math>p</math>-adik digeneralisasikan ke [[medan bilangan aljabar]] dan [[Penilaian (aljabar)|penilaian-penilaian]] tersebut (pemetaan tertentu dari Medan [[grup perkalian]] ke [[grup terurut total|grup aditif terurut total]] disebut juga sebagai urutan), [[Nilai absolut (aljabar)|nilai absolut]] (pemetaan perkalian tertentu dari medan ke bilangan real disebut juga sebagai norma),<ref name="childress">{{cite book | last = Childress | first = Nancy | doi = 10.1007/978-0-387-72490-4 | isbn = 978-0-387-72489-8 | mr = 2462595 | pages = 8–11 | publisher = Springer, New York | series = Universitext | title = Class Field Theory | url = https://books.google.com/books?id=RYdy4PCJYosC&pg=PA8 | year = 2009 }} Lihat pula hal. 64.</ref> dan tempat (ekstensi ke [[medan lengkap]] dimana medan yang diberikan adalah [[himpunan rapat]] disebut juga sebagai pelengkapan).<ref>{{cite book | last = Weil | first = André | author-link = André Weil | isbn = 978-3-540-58655-5 | mr = 1344916 | page = [https://archive.org/details/basicnumbertheor00weil_866/page/n56 43] | publisher = Springer-Verlag | location = Berlin | series = Classics in Mathematics | title = Basic Number Theory | url = https://archive.org/details/basicnumbertheor00weil_866 | url-access = limited | year = 1995}} Namun perhatikan bahwa beberapa penulis seperti {{harvtxt|Childress|2009}} malah menggunakan "tempat" untuk mengartikan kelas norma yang setara.</ref> Perluasan dari bilangan rasional ke [[bilangan real]], misalnya adalah tempat dimana jarak antara bilangan adalah [[nilai absolut]] biasa dari perbedaannya. Pemetaan yang sesuai ke grup aditif akan menjadi [[logaritma]] dari nilai absolut, meskipun ini tidak memenuhi semua persyaratan penilaian. Menurut [[teorema Ostrowski]], gagasan ekuivalen alami berhingga, bilangan real dan bilangan <math>p</math>-adik dengan urutan dan nilai absolutnya adalah satu-satunya penilaian, nilai absolut, dan tempat pada bilangan rasional.<ref name="childress"/> [[Prinsip lokal-global]] memungkinkan masalah tertentu atas bilangan rasional untuk diselesaikan dengan menyatukan solusi dari masing-masing tempat, sekali lagi menggarisbawahi pentingnya bilangan prima untuk teori bilangan.<ref>{{cite book | last = Koch | first = H. | doi = 10.1007/978-3-642-58095-6 | isbn = 978-3-540-63003-6 | mr = 1474965 | page = 136 | publisher = Springer-Verlag | location = Berlin | title = Algebraic Number Theory | url = https://books.google.com/books?id=wt1sCQAAQBAJ&pg=PA136 | year = 1997| citeseerx = 10.1.1.309.8812 }}</ref>

 

=== Teori grup ===

 

==Catatan==