Bilangan prima: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Dedhert.Jr (bicara | kontrib) →Barisan aritmetika: perbaikan referensi |
→Definisi dan contoh: Menambahkan sejarah Tag: halaman dengan galat kutipan Suntingan perangkat seluler Suntingan peramban seluler Suntingan seluler lanjutan |
||
Baris 20:
Himpunan bilangan prima terkadang dilambangkan <math>\mathbf{P}</math><ref>{{Cite book|last=Nathanson|first=Melvyn B.|date=2008-01-11|url=https://books.google.co.id/books?id=sE7lBwAAQBAJ&pg=PP10&redir_esc=y|title=Elementary Methods in Number Theory|publisher=Springer Science & Business Media|isbn=978-0-387-22738-2|language=en}}</ref> atau <math>\mathbb{P}</math>.<ref>{{Cite book|last=Faticoni|first=Theodore G.|date=2012-04-23|url=https://books.google.co.id/books?id=I433i_ZGxRsC&pg=PA44&redir_esc=y#v=onepage&q&f=false|title=The Mathematics of Infinity: A Guide to Great Ideas|publisher=John Wiley & Sons|isbn=978-1-118-24382-4|pages=44|language=en|url-status=live}}</ref>
==Sejarah==
[[Berkas:Rhind Mathematical Papyrus.jpg|thumb|[[Papirus Matematika Rhind]]|alt=Papirus Matematika Rhind]]
[[Papirus Matematika Rhind]] dari sekitar tahun 1550 SM, memiliki [[pecahan Mesir]] ekspansi bentuk yang berbeda untuk bilangan prima dan 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 pertama kali yang bertahan studi eksplisit bilangan prima berasal dari [[matematika Yunani|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>
Sekitar 1000 M, matematikawan [[Matematika dalam Islam abad pertengahan|Islam]] [[Ibn al-Haytham]] (Alhazen) menemukan [[teorema Wilson]] dengan mencirikan bilangan prima sebagai bilangan <math>n</math> yang membagi rata <math>(n-1)!+1</math>. Ia juga menduga bahwa semua bilangan sempurna genap berasal dari konstruksi Euklides yang menggunakan bilangan prima Mersenne, tetapi tidak dapat membuktikannya.<ref>{{MacTutor Biography|id=Al-Haytham|title=Abu Ali al-Hasan ibn al-Haytham|mode=cs1}}</ref> 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.<ref name="mollin"/>
Pada tahun 1640 [[Pierre de Fermat]] menyatakan (tanpa pembuktian) [[teorema kecil Fermat]], kemudian dibuktikan dengan [[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 [[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> [[Christian Goldbach]] merumuskan [[konjektur Goldbach]], bahwa setiap bilangan genap adalah jumlah dari dua bilangan prima, dalam surat tahun 1742 untuk Euler.<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 [[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 area ini dalam buktinya tentang ketakhinggaan bilangan prima dan [[divergensi jumlah kebalikan dari bilangan prima]] <math>\tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{5}+\tfrac{1}{7}+\tfrac{1}{11}+\cdots</math>.<ref>{{cite book|title=The Development of Prime Number Theory: From Euclid to Hardy and Littlewood|series=Springer Monographs in Mathematics|first=Wladyslaw|last=Narkiewicz|publisher=Springer|year=2000|isbn=978-3-540-66289-1|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 sebagai <math>x</math> cenderung tak-hingga, jumlah bilangan prima hingga <math>x</math> adalah [[Analisis asimtotik|asimptotik]] hingga <math>x/\log x</math>, dimana <math>\log x</math> adalah [[logaritma alami]] dari <math>x</math>. Konsekuensi lemah dari kerapatan bilangan prima tinggi adalah [[postulat Bertrand]], bahwa untuk setiap <math>n > 1</math> terdapat bilangan prima diantara <math>n</math> dan <math>2n</math> yang dibuktikan pada tahun 1852 oleh [[Pafnuty Chebyshev]].<ref>{{cite journal|first=P. |last=Tchebychev |author-link=Pafnuty Chebyshev |title=Mémoire sur les nombres premiers. |journal=Journal de mathématiques pures et appliquées |series=Série 1 |year=1852 |pages=366–390 |url=http://sites.mathdoc.fr/JMPA/PDF/JMPA_1852_1_17_A19_0.pdf |language=fr}}. (Proof of the postulate: 371–382). Lihat pula Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, hal. 15–33, 1854</ref> Gagasan [[Bernhard Riemann]] dalam karyanya [[On the Number of Primes Less Than a Given Magnitude|1859 makalah tentang fungsi-zeta]] membuat sketsa garis besar untuk membuktikan konjektur Legendre dan Gauss. Meskipun [[hipotesis Riemann]] yang terkait erat tetap tidak terbukti, garis besar Riemann diselesaikan pada tahun 1896 oleh [[Jacques Hadamard|Hadamard]] dan [[Charles Jean de la Vallée-Poussin|de la Vallée Poussin]], dan hasilnya sekarang dikenal sebagai [[teorema bilangan prima]].<ref>{{cite book | last = Apostol | first = Tom M. | author-link = Tom M. Apostol | editor1-last = Bambah | editor1-first = R.P. | editor2-last = Dumir | editor2-first = V.C. | editor3-last = Hans-Gill | editor3-first = R.J. | contribution = A centennial history of the prime number theorem | location = Basel | mr = 1764793 | pages = 1–14 | publisher = Birkhäuser | series = Trends in Mathematics | title = Number Theory | contribution-url = https://books.google.com/books?id=aiDyBwAAQBAJ&pg=PA1 | year = 2000}}</ref> Hasil terpenting abad ke-19 lainnya adalah [[Teorema Dirichlet tentang barisan aritmetika]], bahwa [[barisan aritmetika]] tertentu mengandung banyak bilangan prima ketakhinggaan.<ref>{{cite book | last = Apostol | first = Tom M. | author-link = Tom M. Apostol | contribution = 7. Dirichlet's Theorem on Primes in Arithmetical Progressions | contribution-url = https://books.google.com/books?id=3yoBCAAAQBAJ&pg=PA146 | location = New York; Heidelberg | mr = 0434929 | pages = 146–156 | publisher = Springer-Verlag | title = Introduction to Analytic Number Theory | year = 1976 }}</ref>
Beberapa matematikawan telah melakukan [[uji primalitas]] untuk bilangan lebih besar dari bilangan penerapan uji pembagian. Metode batasan untuk bentuk bilangan tertentu termasuk [[uji Pépin]] untuk bilangan Fermat (1877),<ref>{{cite book|title=A History of Algorithms: From the Pebble to the Microchip|first=Jean-Luc|last=Chabert|publisher=Springer|year=2012|isbn=978-3-642-18192-4|page=261|url=https://books.google.com/books?id=XcDqCAAAQBAJ&pg=PA261}}</ref> [[Proth's theorem]] (c. 1878),<ref>{{cite book|title=Elementary Number Theory and Its Applications|first=Kenneth H.|last=Rosen|edition=4th|publisher=Addison-Wesley|year=2000|isbn=978-0-201-87073-2|contribution=Theorem 9.20. Proth's Primality Test|page=342}}</ref> [[uji primalitas Lucas–Lehmer]] (dari tahun 1856), dan generalisasi [[uji primalitas Lucas]].<ref name="mollin"/>
Sejak tahun 1951, semua [[bilangan prima terbesar yang diketahui]] telah ditemukan menggunakan tes 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 [[Pencarian Utama Mersenne Internet Hebat]] dan proyek [[komputasi distribusi]] lainnya.<ref name=ziegler/><ref>{{harvnb|Rosen|2000}}, hal. 245.</ref> Gagasan bahwa bilangan prima memiliki beberapa aplikasi 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 – 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>
Meningkatnya kepentingan praktis dari pengujian dan faktorisasi primalitas terkomputerisasi menyebabkan pengembangan metode menjadi lebih baik yang mampu menangani sejumlah besar bentuk ketakhinggaan.<ref name="pomerance-sciam"/><ref>{{cite book|title=Secret History: The Story of Cryptology|series=Discrete Mathematics and Its Applications|first=Craig P.|last=Bauer|publisher=CRC Press|year=2013|isbn=978-1-4665-6186-1|page=468|url=https://books.google.com/books?id=EBkEGAOlCDsC&pg=PA468}}</ref><ref>{{cite book|title=Old and New Unsolved Problems in Plane Geometry and Number Theory|volume=11|series=Dolciani mathematical expositions|first1=Victor|last1=Klee|author1-link=Victor Klee|first2=Stan|last2=Wagon|author2-link=Stan Wagon|publisher=Cambridge University Press|year=1991|isbn=978-0-88385-315-3|page=224|url=https://books.google.com/books?id=tRdoIhHh3moC&pg=PA224}}</ref> 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.<ref name="neale-18-47">{{harvnb|Neale|2017}}, pp. 18, 47.</ref>
<!--
===Primality of one===
Kebanyakan orang Yunani awal bahkan tidak menganggap 1 sebagai angka,<ref name="crxk-34">{{cite journal | last1 = Caldwell | first1 = Chris K. | last2 = Reddick | first2 = Angela | last3 = Xiong | first3 = Yeng | last4 = Keller | first4 = Wilfrid | issue = 9 | journal = [[Journal of Integer Sequences]] | mr = 3005523 | page = Article 12.9.8 | title = The history of the primality of one: a selection of sources | url = https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.html | volume = 15 | year = 2012 }} For a selection of quotes from and about the ancient Greek positions on this issue, see in particular pp. 3–4. For the Islamic mathematicians, see p. 6.</ref><ref>{{cite book|title=Speusippus of Athens: A Critical Study With a Collection of the Related Texts and Commentary|volume=39|series=Philosophia Antiqua : A Series of Monographs on Ancient Philosophy|first=Leonardo|last=Tarán|publisher=Brill|year=1981|isbn=978-90-04-06505-5|pages=35–38|url=https://books.google.com/books?id=cUPXqSb7V1wC&pg=PA35}}</ref> so they could not consider its primality. A few mathematicians from this time also considered the prime numbers to be a subdivision of the odd numbers, so they also did not consider 2 to be prime. However, Euclid and a majority of the other Greek mathematicians considered 2 as prime. The [[Mathematics in medieval Islam|medieval Islamic mathematicians]] largely followed the Greeks in viewing 1 as not being a number.<ref name="crxk-34"/>
By the Middle Ages and Renaissance, mathematicians began treating 1 as a number, and some of them included it as the first prime number.<ref>{{harvnb|Caldwell|Reddick|Xiong|Keller|2012}}, pp. 7–13. See in particular the entries for Stevin, Brancker, Wallis, and Prestet.</ref> In the mid-18th century [[Christian Goldbach]] listed 1 as prime in his correspondence with [[Leonhard Euler]]; however, Euler himself did not consider 1 to be prime.<ref>{{harvnb|Caldwell|Reddick|Xiong|Keller|2012}}, p. 15.</ref> In the 19th century many mathematicians still considered 1 to be prime,<ref name="cx"/> and lists of primes that included 1 continued to be published as recently as 1956.<ref>{{cite book | last=Riesel | first=Hans | author-link= Hans Riesel | title=Prime Numbers and Computer Methods for Factorization | publisher=Birkhäuser | location=Basel, Switzerland | isbn=978-0-8176-3743-9 | year=1994|page=36|edition=2nd|mr=1292250|url=https://books.google.com/books?id=ITvaBwAAQBAJ&pg=PA36 | doi=10.1007/978-1-4612-0251-6 }}</ref><ref name="cg-bon-129-130">{{cite book | last1=Conway | first1=John Horton | author1-link=John Horton Conway | last2=Guy | first2=Richard K. | author2-link=Richard K. Guy | title=The Book of Numbers | url=https://archive.org/details/bookofnumbers0000conw | url-access=registration | publisher=Copernicus | location=New York | isbn=978-0-387-97993-9 | year=1996 | pages = [https://archive.org/details/bookofnumbers0000conw/page/129 129–130] | mr=1411676 | doi=10.1007/978-1-4612-4072-3 }}</ref>
If the definition of a prime number were changed to call 1 a prime, many statements involving prime numbers would need to be reworded in a more awkward way. For example, the fundamental theorem of arithmetic would need to be rephrased in terms of factorizations into primes greater than 1, because every number would have multiple factorizations with different numbers of copies of 1.<ref name="cx">{{cite journal | last1 = Caldwell | first1 = Chris K. | last2 = Xiong | first2 = Yeng | issue = 9 | journal = [[Journal of Integer Sequences]] | mr = 3005530 | page = Article 12.9.7 | title = What is the smallest prime? | url = https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell1/cald5.pdf | volume = 15 | year = 2012}}</ref> Similarly, the [[sieve of Eratosthenes]] would not work correctly if it handled 1 as a prime, because it would eliminate all multiples of 1 (that is, all other numbers) and output only the single number 1.<ref name="cg-bon-129-130"/> Some other more technical properties of prime numbers also do not hold for the number 1: for instance, the formulas for [[Euler's totient function]] or for the [[Sum-of-divisors function|sum of divisors function]] are different for prime numbers than they are for 1.<ref>For the totient, see {{harvnb|Sierpiński|1988}}, [https://books.google.com/books?id=ktCZ2MvgN3MC&pg=PA245 p. 245]. For the sum of divisors, see {{cite book|title=How Euler Did It|series=MAA Spectrum|first=C. Edward|last=Sandifer|publisher=Mathematical Association of America|year=2007|isbn=978-0-88385-563-8|page=59|url=https://books.google.com/books?id=sohHs7ExOsYC&pg=PA59}}</ref> By the early 20th century, mathematicians began to agree that 1 should not be listed as prime, but rather in its own special category as a "[[Unit (ring theory)|unit]]".<ref name="cx"/>-->
== Sifat-sifat dasar ==
| |||