Sejarah Bilangan Prima

SEJARAH PERKEMBANGAN BILANGAN PRIMA
Drs. Rudy Kurniawan, M.Pd
Dosen Pendidikan Matematika STKIP YASIKA
Abstrak
Prinsip dasar bilangan prima merujuk pada suatu definisi, yaitu suatu bilangan bulat positif yang hanya memiliki dua faktor. Melalui definisi yang istimewa ini maka penemuan – penemuan baru bilangan prima masih memungkinkan hingga dekade ini, terlebih lagi dengan ditemukannya program-program komputer untuk menemukan bilangan prima yang baru. selain itu, melalui keistimewaan bilangan prima tersebut, memungkinkan penggunaannya untuk suatu sistem keamanan yang canggih. Namun dibalik keistimewaannya, masih banyak orang yang belum mengetahui sejarah bilangan prima. Melalui studi literature penulis menyajikan tentang sejarah dan penemuan bilangan prima, yang mudah-mudahan dapat mendorong cakrawala perkembangan bilangan prima dan matematika pada umumnya.


1. Pengertian Bilangan Prima
Dalam sejarah awal perkembangannya, pengertian bilangan prima adalah bagian dari himpunan bilangan bulat positif, sehingga dapat didefinisikan bilangan prima adalah bilangan bulat positif yang hanya dapat terbagi oleh satu dan dirinya sendiri (bilangan prima adalah bilangan yang tepat memiliki dua faktor). Definisi ini dapat saja berkembang jika konteks semesta pembicaraannya diperluas menjadi himpunan bilangan bulat, sehingga pada masa sekarang dikenal adanya bilangan prima negatif (negative prime) dan bilangan prima positif (positive prime).
Dalam beberapa usaha penemuan yang bertujuan mengkaji hubungan antar bilangan prima, dikenal pula adanya pengertian bilangan prima kembar (twin primes) yang merupakan pasangan bilangan prima yang memenuhi kaidah p dan p + 2 dengan p adalah prima. Contoh : 3 dan 5, 11 dan 13, 29 dan 31.

2. Sejarah Bilangan Prima
2.1.Bilangan Prima pada Rumusan Pythagorean Triples
Dalam sejarah Yunani kuno tercatat nama besar Pythagoras (570 – 500 SM), ia sangat terkenal lewat `Theorem of Pythagoras` dan memunculkan bilangan ganda 3 atau dikenal dengan istilah Pythagorean Triples yang sebenarnya telah ada sejak 1000 tahun sebelum masa Pythagoras. Menurut catatan sejarah bangsa Babilonia telah mengenal ganda 3 tersebut, yang terkenal dengan nama Babylonian Triples. Di dalam Babylonian tablet Plimton 322, yang diperkirakan berasal dari tahun 1700 S M, tercatat Babylonian Triples tersebut ketenarannya terkalahkan oleh ketenaran nama Pythagorean Triples. Sebenarnya, diantara keduanya terdapat perbedaan. Pada Babylonian Triples disyaratkan bahwa u dan v sebagai generator 2uv, u2 – v2 dan u2 + v2 yang merupakan ukuran sisi-sisi segitiga siku-siku, harus relatif prima dan tidak mempunyai faktor prima selain 2, 3 atau 5. Sebagai contoh, tiga angka seperti (56,90,106) adalah Babylonian Triples hal ini dimungkinkan karena jika u = 9 dan v = 5 dan disubstitusikan pada generatornya akan menghasilkan bilangan 56, 90, 106, tetapi untuk ketiga bilangan (28,45,53) adalah bilangan Pythagorian Triples tetapi bukan Babylonian Triple, karena untuk u = 7, u memiliki faktor prima 7 bukan 2 atau 3 atau 5.
2.2. Bilangan Prima di Rumusan Bilangan Sempurna
Bilangan Prima dalam Rumusan Bilangan Sempurna, sesuai karya Euclid dalam buku IX Elements (300 SM) diberikan bukti dari sebuah proposisi, yaitu :
Jika 2n – 1 adalah prima maka 2n – 1.(2n – 1) adalah bilangan sempurna (perfect number).
Bukti preposisi tersebut adalah sebagai berikut :
Karena 2m – 1 adalah prima maka 2m – 1 = p dengan p prima sehingga
Untuk n = 2m-1.(2m – 1) dan n = 2m-1. p, dengan pembagi-pembagi : 1, 2, 22, …, 2m-1, p, 2p, …,
2m-1.p
Jumlah pembagi-pembaginya :
1 + 2 + 22 +… + p + 2p +
… + 2m-1.p
S(n) = (1+2+22+…+2m-1).(1+p) = ( 2m-1).(1+p) = p . (1+p),
dengan p = 2 m-1 dan p+1 = 2m- 1+1=2m = p . 2m, sementara
n = 2m-1. p maka 2n = 2.2m-1 . p = 2m . p = p . 2m
Pada masa itu bangsa Yunani telah menemukan 4 bilangan sempurna yaitu 6, 28, 496 dan 8128 (Kart : 458). Berkenaan dengan bilangan sempurna ini, sekitar 2000 tahun kemudian seorang matematikawan Euler pada tahun 1947 telah mampu menunjukkan bahwa semua bilangan sempurna yang didapat dari rumusan di atas adalah genap. Tidak diketahui sampai hari ini apakah ada bilangan sempurna yang ganjil.
Teorema ke-20 dari buku IX The Elements Euclide menyatakan bahwa “ Tidak ada bilangan prima yang terakhir (There is no last Prime)”. Pernyataan ini menunjukan ketakberhinggaan bilangan prima (Infinitude of Prime) yang dibuktikan Euclid dengan menggunakan cara pembuktian kontradiksi.
Untuk hal tersebut perhatikanlah definisi bahwa suatu bilangan p prima jika p ¹1 dan pembagi-pembaginya hanya 1 dan p dengan demikian hanya p½p dan 1½p. Misalkan p1, p2, p3, …, pn adalah n prima berbeda maka bilangan prima dapat dinyatakan dengan:
a = p1 . p2 . p3 . ….pn + 1, maka p1 ½a , karena p1 ½ p1 . p2 . p3 . ….pn dan andaikan p1½a maka p1 ½(a - p1 . p2 . p3 . ….pn ) atau p1 ½1, tentu hal ini tidak mungkin terjadi karena hanya 1½1 , sementara p1 prima ( p1¹ 1 ), terjadi kontradiksi, sehingga yang benar: p1½a dan p2½a, p3½a,…, pn½a
Dengan demikian ada suatu bilangan a yang tidak terbagi oleh bilangan prima manapun dengan pengambilan suatu n. Dalam hal ini a adalah bilangan prima yang besarnya ditentukan oleh n. Nilai n dapat membesar sampai tak hingga.
2.3. Pencarian Bilangan Prima
Sebenarnya Euclid dalam beberapa definisi dan proposisi buku Elements-nya menaruh perhatian yang sangat besar akan keberadaan bilangan prima ini. Dalam buku IX Elements, beliau memberikan bukti tentang ketakberhinggaan banyaknya bilangan-bilangan prima dengan menggunakan metode kontradiksi, yang dilakukan pertama kali dalam sejarah matematikan. Selain itu, Euclid juga memberikan sebuah bukti Teorema Fundamental Aritmetika : “Setiap bilangan bulat dapat ditulis sebagai hasil kali bilangan-bilangan prima dalam sebuah bentuk dasar yang unik”. Kemudian dikenal dengan nama Eratosthenes (± 230 SM) dengan `Eratosthenes sieve` atau saringan Eratosthenes,. Pertama-tama ia memperkenalkan metode untuk mendapatkan seluruh bilangan prima yang terbatas hingga suatu bilangan bulat positif n. Dari saringan itu akan didapat bilangan-bilangan prima yang kurang dari n, bahkan dengan saringan tersebut diturunkan suatu konjektur dalam bentuk formula yang dapat dipergunakan untuk memprediksi banyaknya bilangan prima kurang dari suatu bilangan n, yang dinyatakan dengan √n. Sebagai contoh diberikan cara mencari bilangan prima kurang dari 50, dengan langkah-langkah sebagai berikut:
1. Susun bilangan asli secara berurutan kurang dari 50
2. Hilangkan bilangan 1 karena 1 bukan prima
3. Hilangkan bilangan kelipatan 2, kecuali 2
4. Hilangkan bilangan kelipatan 3, kecuali 3
5. Hilangkan bilangan kelipatan 5, kecuali 5
6. Hilangkan bilangan kelipatan 7, kecuali 7
Realisasi langkah tersebut seperti berikut ini:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50.
Sehingga didapat bilangan prima yang kurang dari 50 adalah 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Keberadaan formula untuk memprediksi banyaknya bilangan prima kurang dari n, yaitu Ön, diperkuat oleh Ernst Meissel yang sukses menunjukkan banyaknya bilangan prima kurang dari 108 sebanyak 5.761.455 pada tahun 1870. Bertelsen, melanjutkan perhitungan Ernst dan tahun 1893, ia mengumumkan bahwa banyak bilangan prima yang kurang dari 109 adalah 50.847.478, dan hasil ini kemudian dikoreksi oleh D. H. Lehmer pada tahun 1959 yang menyatakan bahwa Bertelsen keliru, seharusnya 50.847.534, ia juga menunjukkan bahwa banyak bilangan prima kurang dari 1010 adalah sebanyak 455.052.511. Meskipun telah sebegitu jauh para matematikawan berusaha, tapi sampai saat ini belum dikenal suatu prosedur praktis yang dapat dipergunakan untuk menentukan suatu bilangan prima.
Matematikawan masa lalu beranggapan bahwa bentuk 2n – 1 akan menghasilkan semua bilangan prima untuk n bilangan prima, jika n bukan prima maka bilangan yang didapat adalah komposit.. Rumus berbentuk 2n – 1 ini tampaknya diadopsi dari rumus bilangan sempurna 2n-1.( 2n – 1) yang mempersyaratkan 2n –1 adalah prima. Sementara 2n –1 tidak prima jika n bukan prima, tetapi pada tahun 1536 Hudalricus Regius menunjukkan bahwa 211 – 1 = 2047 bukan prima karena 2047 = 23 x 89. Selain itu Pietro Cataldi dari Italia pada tahun 1603 melakukan verifikasi terhadap 217 – 1 dan 219 – 1 , ternyata keduanya adalah prima dan menurut Cataldi pula 2n – 1 adalah prima juga untuk n = 23, 29, 31 dan 37. Pada tahun 1640, Pierre de Fermat berhasil menunjukkan bahwa Cataldi keliru untuk n = 29 dan beberapa waktu kemudian Euler menunjukkan bahwa Cataldi kali ini benar untuk n = 31.
2.3.1. Pierre de Fermat ( 1601 – 1665 )
Pada awal abad ke-17 Fermat membuktikan sebuah spekulasi dari Albert Girard bahwa setiap bilangan prima berbentuk 4n + 1 dapat ditulis dalam sebuah bentuk unik sebagai jumlah dari dua kuadrat, seperti 5 = 4.1 + 1 = 22 + 12 dan 13 = 4.3 + 1 = 32 + 22, dan ia juga mampu menunjukkan bagaimana suatu bilangan dapat ditulis sebagai jumlah dari 4 kuadrat. Fermat menemukan metode baru dalam memfaktorkan bilangan-bilangan besar yang didemontrasikannya pada pemfaktor-an bilangan 2027651281 = 44021 46061, yang sangat bermanfaat besar pada pengujian keprimaan suatu bilangan. Dalam korespondensi dengan seorang biarawan matematikawan Marin Mensenne (1588 – 1648), yang tercatat dalam suratnya pada Juni 1640 berisi 3 proposisi, yaitu :
1. Jika n bukan prima maka 2n – 1 tidak dapat menjadi prima
Dengan bukti :
n bukan prima maka n = r.s
2n – 1 = 2r.s – 1 = (2r)s – 1s = (2r – 1).(2r.(s-1) + 2r.(s-2) + … +2r + 1)
2. Jika p bilangan prima ganjil maka 2p membagi 2p – 2 atau p membagi 2p-1 – 1
3. Pembagi-pembagi yang mungkin untuk 2p – 1 adalah berbentuk 2pk + 1.
Untuk kedua proposisi terakhir Fermat tidak memberikan bukti dalam suratnya tersebut. Untuk proposisi yang ketiga ia hanya memberikan konfirmasi bahwa 237 – 1 adalah komposit (bukan prima) dengan pengujian 2pk + 1 = 2.37.k + 1 = 74k + 1 = 74.3 + 1 = 223 adalah pembagi dari 237 – 1. Dalam suratnya yang lain kepada Bernard Frenicle de Bessy (1612 – 1675), Fermat membuat pernyataan teoremanya lebih umum dari teoremanya di atas yang sekarang kita kenal dengan nama Fermat’s Little Theorem: Jika p adalah suatu bilangan prima maka untuk suatu bilangan bulat positif a didapat p membagi ap – a. Atau dapat pula ditulis: Jika p adalah suatu bilangan prima maka untuk suatu bilangan bulat positif a didapat aP ≡ a (modulo p). Atau dengan penambahan kondisi: Jika p adalah bilangan prima dan a suatu bilangan yang tidak habis dibagi p ( a dan p relatif prima) maka a p-1 º 1 (modulo p). Sebagian dari contoh-contoh yang berkenaan dengan kebenaran teori ini telah ada jauh sebelum itu, yaitu seperti yang ditulis sekitar 2000 tahun sebelumnya dalam suatu hipotesis yang dinamakan Chinese Hypothesis bahwa sebuah bilangan bulat positif n adalah prima jika dan hanya jika bilangan 2n – 2 habis dibagi n. Namun sayangnya pada sebagian contoh yang lainnya terdapat kekeliruan semenjak ditemukan bahwa 2341 – 2 habis dibagi 341 tetapi 341 = 31 x 11, mengindikasikan 341 bukan prima. Jadi dalam hal ini teorema Fermat ini merupakan suatu koreksi dari sebuah hipotesis.
Pada tahun 1659, Fermat mengajukan suatu konjektur bahwa bilangan-bilangan yang didapat dari rumusan berbentuk adalah selalu prima untuk n = 0, 1, 2, 3, … . Bilangan-bilangan yang didapat dari rumusan ini dinamakan dengan Fermat Numbers. Namun tidak sampai 100 tahun kemudian tepatnya tahun 1732, Leonhard Euler mendapatkan bahwa untuk 232 + 1 = 4294967297 adalah habis dibagi oleh 641 dan berarti bukan prima.
2.3.2. Marin Mersenne (1588-1648)
Sementara itu Marin Mersenne tampil dengan membuat suatu pernyataan pada kata pengantar dalam karyanya Cogitata Phisyca-Mathematica (1644) bahwa bilangan-bilangan yang didapat dari 2n – 1 adalah prima untuk n = 2, 3, 5, 7, 17, 19, 31, 67, 127 dan 257 dan komposit untuk semua bilangan bulat positif lainnya n < mn =" 2n" m19 =" 219" n =" 257" n =" 2," u1 =" 4," 1 =" un2"> 2 maka 2m –1 adalah bilangan prima.
Sebagai contoh :
u1 = 4, u2 = u12 – 2 = 42 – 2 = 14, u3 = u22 – 2 = 142 - 2 = 194, dan
u4 = u32 - 2 = 1942 – 2 = 37.634, dst.
Untuk m = 5 maka 25 – 1 = 31 merupakan factor dari u4 = 37.634, karena itu 25 – 1 = 31 adalah prima (Anglin,25: 1994)
Rumus lain bilangan prima dalam bentuk fungsi kuadarat dengan domain n bulat positif juga pernah tampil diantaranya f(n) = n2 – n + 41, yang ternyata hanya berlaku untuk n < an =" banyaknya" n =" 1/" 1 =" 131071" 1 =" 524287" 1 =" 2147483647" 179951="3203431780337)." 1 =" 170141183460469231731687303715884105727" href="http://www.utm.edu/research/primes/notes/proofs/MerDiv.html">trial division++(/a)
(259-1)/179951
13
1867
Landry
SDA
2127-1
39
1876
Lucas
Lucas sequences
(2148+1)/17
44
1951
Ferrier
Proth's theorem

Dalam tahun 1951 Meller dan Wheeler memulai era perhitungan elektronik -EDSA machine di Cambridge Inggris dan menemukan beberapa bilangan prima, yaitu: k.M127 + 1 untuk k = 114, 124, 388, 408, 498, 696, 738, 744, 780, 934 dan 978, kemudian didapat rekor 79 digit bilangan prima baru untuk 180.(M127)2 + 1 (disini M127= 2127-1). Pada tahun berikutnya Raphael Robinson dengan menggunakan program SWAC (Standards Westeren Automatic Computer) menemukan lima bilangan prima (Mersenne prime) besar baru. Pada waktu program tersebut pertama kali digunakan pada tanggal 30 Januari, ditemukan dua bilangan prima (M521, M607), tiga prima berikutnya ditemukan pada tanggal 25 Juni (M1279), 7 Oktober (M2203), dan 9 Oktober (M2281).
Dengan kemajuan tehnologi komputer diperoleh bilangan prima Riesel yang menemukan M3217 menggunakan mesin Swedia BESK, Hurwitz menemukan M4253 dan M4423 dengan IBM 7090; Gilleis dengan ILLIAC-2 menemukan M9689, M9941 dan M11213. Tuckerman menemukan M19937 dengan IBM360.
Bilangan prima terbesar untuk saat ini, didapat oleh Michael dalam The team of Michael Cameron, George Woltman, Scott Kurowski pada tanggal 14 Nopember 2001, berhasil mendapatkan bilangan prima menggunakan program yang ditulis oleh George sebagai mata rantai dari GIMPS (Great Internet Mensenne Prime Search) Internet database melalui Scott’s PrimeNet. Bilangan prima tersebut merupakan Mersenne Prime ke-39 yaitu M13466917 terdiri atas 4.053.946 digit desimal.
Bilangan prima kembar terbesar, diumumkan oleh Indlekofer dan Ja’rai pada Nopember1995 adalah 242206083 x 23880 + 1 dan 242206083 x 23880 – 1, keduanya terdiri atas 11.713 digit desimal.
Bilangan prima faktorial terbesar, diumumkan oleh Caldwell pada tahun 1993 adalah 3610! –1, yang terdiri atas 11.277 digit desimal.
Bilangan prima primorial terbesar (bilangan prima didapat dari rumus n # ± 1 dengan n # adalah hasil kali semua prima £ n) diumumkan oleh Caldwell pada tahun 1993 adalah 24029 # + 1 yang terdiri atas 10.387 digit desimal.( O’Connor and Robertson: 2001).
Berikut ini adalah tabel 2, mengenai rekor pencarian bilangan prima dengan menggunakan komputer.


Tabel 2
Rekor Penemuan Bilangan Prima dengan Program Komputer
Bilangan
Digit
Tahun
Program
Pembukti
180(M127)2+1
79
1951
EDSAC1
Miller & Wheeler
M521
157
1952
SWAC
Robinson (Jan 30)
M607
183
1952
SWAC
Robinson (Jan 30)
M1279
386
1952
SWAC
Robinson (June 25)
M2203
664
1952
SWAC
Robinson (Oct 7)
M2281
687
1952
SWAC
Robinson (Oct 9)
M3217
969
1957
BESK
Riesel
M4423
1,332
1961
IBM7090
Hurwitz
M9689
2,917
1963
ILLIAC 2
Gillies
M9941
2,993
1963
ILLIAC 2
Gillies
M11213
3,376
1963
ILLIAC 2
Gillies
M19937
6,002
1971
IBM360/91
Tuckerman
M21701
6,533
1978
CDC Cyber 174
Noll & Nickel
M23209
6,987
1979
CDC Cyber 174
Noll
M44497
13,395
1979
Cray 1
Nelson & Slowinski
M86243
25,962
1982
Cray 1
Slowinski
M132049
39,751
1983
Cray X-MP
Slowinski
M216091
65,050
1985
Cray X-MP/24
Slowinski
391581*2216193 -1
65,087
1989
Amdahl 1200
Z.html
M756839
227,832
1992
Cray-2
Slowinski & Gage
M859433
258,716
1994
Cray C90
Slowinski & Gage
M1257787
378,632
1996
Cray T94
Slowinski & Gage
M1398269
420,921
1996
Pentium (90 Mhz)
Armenga,Woltman, Mersenne org.
M2976221
895,932
1997
Pentium (100 Mhz)
Spence, Woltman, Mersenne.org
M3021377
909,526
1998
Pentium (200 Mhz)
Clarkson, Woltman, Kurowski, Mersenne.org
M6972593
2,098,960
1999
Pentium (350 Mhz)
Hajratwala, Woltman, Kurowski,Mersenne
M13466917
4,053,946
2001
AMD T-Bird (800 Mhz)
Cameron, Woltman, Kurowski,Mersenne

4. Manfaat Bilangan Prima
Saat ini bilangan prima dapat dimanfaatkan pada RSA dan El-Gamel yaitu suatu usaha penggunaan sandi rahasia untuk kepentingan pengamanan (Semantical Security). Dalam El-Gamel, dibutuhkan sebuah grup Zp *, yaitu grup dengan Z adalah himpunan bilangan prima dan operasi *. Kemudian El-gamel tidak hanya membutuhkan grup tetapi juga subgrup dari Zp* dengan generatornya diambil dari Grup Zp*. Hal tersebut diperlukan karena pengamanan dengan hanya menggunakan Plain Group, membuat kode keamanan El-Gamel menjadi kurang terjamin. Implikasi kebermanfaatan bilangan prima sekarang ini, digunakan untuk kode-kode rahasia kartu ATM suatu bank.





















Daftar Pustaka

Anglin, W.S. (1994).Mathematics: A Concise History and Philosophy, Springer-Verlag, New York.

Chris, C. K.(2003). The Largest Known Prime by Year A Brief History. http://www.utm.edu/research/primes/largest.html. Akses, 25 September 2003.

Canjorin, F. (1924). A History of Elementary Mathematics with Hints on Methods of Teaching. London: The Macmillan Company.

Evans, P.J. (1970). Mathematics Creation and Study of Form California:Addison Wesley.

Eves, H.(1964).An Introduction to the History of Mathematics. New York: Holt, Rinehart and winston.

Naga, S.D.(1980). Berhitung Sejarah dan Perkembangannya. Jakarta: PT Gramedia

O’Connor, J.J. and Robertson, E.F.(2001).Prime Number. http://www-history.mcs.st-andrew.ac.uk/ history/Hist Topis/prime_numbers.html. Akses, 25 September 2003.

Sitorus, J.(1990). Pengantar Sejarah Matematika dan


Pembaharuan Pengajaran Matematika di Sekolah. Bandung: Tarsito

Suhendra (2003). Sejarah Bilangan Prima. Makalah PPS : Tidak dipublikasikan.

Victor, K. J. (1998).A History of Mathematics an Introduction.California: Addison Wesley.