Mathematics is wonderful: Bilangan Prima ( Bagian 3)

Kalian pasti sudah mengenal bilangan Prima (Prime Number). Bilangan prima adalah bilangan Asli yang hanya mempunyai dua faktor, yaitu 1 dan dirinya sendiri. Contoh 2, 3, 5, dan seterusnya. Bilangan 1 bukan bilangan Prima karena hanya mempunyai satu faktor. Bilangan yang bukan 1 dan bukan bilangan Prima disebut bilangan komposit. Salah satu dalil yang terkenal berbunyi, Setiap bilangan komposit merupakan perkalian bilangan-bilangan Prima. Dalil tersebut dikenal sebagai Teorema Dasar Aritmetika. Nah, berapa banyak bilangan Prima yang kalian tahu?

Eratosthenes mempunyai suatu metode untuk mendapatkan bilangan prima pada rentang tertentu. Metode itu diberi nama saringan Eratosthenes (Eratosthenes Sieve). Misalkan kita akan mencari bilangan Prima yang kurang dari n, dengan n bilangan Asli, maka modal kita adalah bilangan Prima yang kurang dari atau sama dengan $\sqrt{n}$ . Sebagai contoh, kita akan mencari bilangan Prima di antara 1 dan100. Kita tahu bahwa $\sqrt{100}=10$ , dan bilangan Prima yang kurang dari 10 adalah 2, 3, 5, dan 7. Selanjutnya kita daftarkan bilangan 1 sampai 100 dalam tabel 10 x 10. Kemudian lakukan langkah berikut:

Coret angka 1
Coret semua bilangan kelipatan 2, kecuali 2
Coret semua bilangan kelipatan 3, kecuali 3. Pada langkah ini, bilangan yang sudah dicoret tidak perlu dicoret lagi.
Coret semua bilangan kelipatan 5, kecuali 5.
Coret semua bilangan kelipatan 7, kecuali 7. Pada langkah ini bilangan yang dicoret hanya 49, 77, dan 91.

Cukup sampai 7, karena Prima terbesar yang kurang dari $\sqrt{100}$ adalah 7. Bilangan yang tidak tercoret merupakan bilangan Prima. Sampai di sini kita dapatkan bilangan Prima yang terletak di antara 1 dan 100, yaitu: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, dan 97. Ada 25 bilangan prima antara 1 dan 100. Kalian bisa mempercepat proses itu dengan bantuan excel. Lihat caranya pada bagian bawah.

Secara umum, jika kita akan mencari bilangan Prima dari 1 sampai bilangan n, maka kita cari dulu bilangan prima yang kurang dari atau sama dengan $\sqrt{n}$ . Setelah itu lakukan langkah-langkah pencoretan bilangan seperti di atas sampai pada bilangan prima yang kurang dari $\sqrt{n}$ tersebut. Pada contoh di atas $\sqrt{100}=10$ , dan bilangan prima yang kurang dari atau sama 10 adalah 7. Jadi, pencoretan bilangan dari 1 sampai 100 berhenti di kelipatan bilangan 7. Anda bisa mencoba untuk bilangan Prima yang kurang dari 200.

Sejak dulu banyak matematikawan yang berusaha membuat rumus untuk mencari bilangan Prima. Pada kasus tertentu rumus itu benar, tetapi pada kasus yang lain ternyata salah. Oleh karena itu, sampai saat ini belum ada rumus yang dalam waktu singkat dapat menentukan bilangan Prima. Meskipun demikian, kita tentu kagum dengan upaya para matematikawan tersebut karena pencarian itu membawa mereka belajar banyak hal.
Beberapa rumus yang menghasilkan bilangan Prima untuk beberapa kasus adalah sebagai berikut:

$F(n) = n^2-n+41$ untuk n bilangan Asli. Rumus ini menghasilkan bilangan Prima untuk n=1,2,,3,dst, tetapi untuk n=41 rumus tersebut gagal karena menghasilkan 412 yang jelas bukan merupakan bilangan Prima.
$F(n)=2^{2^n}+1$ untuk n bilangan Asli. Rumus ini diciptakan oleh Fermat, seorang Matematikawan dari Perancis. Rumus tersebut memberikan bilangan Prima untuk n=0,1,2,3,dan 4 , tetapi gagal untuk n=5 dan n=6.
$F(p)=2^p-1$ dengan p bilangan Prima yang telah diketahui. Rumus ini diciptakan oleh Marsenne. Untuk beberapa nilai p rumus tersebut menghasilkan bilangan Prima, tetapi untuk p=11 rumus tersebut menghasilkan bilangan komposit (bukan Prima).

Jadi, sampai saat ini cara yang meyakinkan adalah menggunakan saringan Eratosthenes.

Ada berapa banyak bilangan Prima? Euclides dari Yunani membuktikan bahwa ada tak hingga banyak bilangan Prima. Meskipun demikian, para ahli matematika sepanjang masa berusaha mencari terus bilangan Prima yang lebih besar dari yang diketahui saat ini. Pencarian bilangan Prima merupakan salah satu pekerjaan yang menyenangkan bagi beberapa pakar matematika dan komputer. Pencarian ini seperti mendaki Puncak Everest, kata George Woltman, seorang pakar ilmu komputer. Bedanya, Everest memilik puncak sehingga pendakian suatu saat berhenti, sedangkan bilangan Prima tidak akan tidak akan terhenti karena memang tidak ada bilangan Prima terbesar. Artinya, jika sekarang ditemukan bilangan Prima lebih dari bilangan prima yang telah diketahui, maka kelak pasti akan ditemukan lagi bilangan Prima yang lebih besar.

Harian Kompas tanggal 6 Februari 2013 memberitakan penemuan bilangan Prima terbesar yang diketahui manusia saat ini. Bilangan Prima tersebut adalah $2^{57.885.161}-1$ . Ini merupakan bilangan Prima yang masuk kelompok bilangan Prima Marsenne, yaitu bilangan Prima yang berbentuk $2^p-1$ . Bilangan Prima tersebut memiliki 17.425.170 digit (angka). Kita bisa bayangkan betapa panjangnya bilangan tersebut jika ditulis di kertas. Jika menggunakan ukuran huruf seperti pada tulisan di buku ini, maka bilangan Prima tersebut panjangnya sekitar 34,85 km.

Bilangan prima terbesar ini ditemukan oleh matematikawan dari University of Central Missouri, Curtis Cooper. Bilangan prima ini adalah bilangan prima besar ketiga yang berhasil ditemukan oleh Cooper. Penemuan bilangan prima terbesar dilakukan lewat upaya kolektif lewat Great Internet Mersenne Prime Search (GIMPS), misi yang dibantu 360.000 prosesor, mengoperasikan 150 triliun penghitungan per detik. Proses pengecekan lewat komputer dilakukan untuk mengonfirmasi penemuan. Atas penemuannya tersebut Curtis Cooper memperoleh hadiah $ 3000. Bilangan Prima bentuk Marsenne dapat dilihat di http://id.wikipedia.org/wiki/Bilangan_prima_Mersenne
Sebelumnya bilangan Prima terbesar yang diketahui manusia adalah $2^{43.112.609}-1$ yang ditemukan pada tahun 2008. Bilangan ini memiliki 12.978.189 digit. Proses menemukan bilangan Prima tersebut dapat dilakukan dengan cara Saringan Eratosthenes. Namun, butuh waktu bertahun-tahun untuk mendapatkan bilangan Prima berikutnya. Barangkali tidak akan selesai seumur hidup manusia. Oleh karena itu, komputer canggih dengan kecepatan luar biasa diperbantukan untuk mencari bilangan Prima tersebut. Ini pun membutuhkan komputer dalam jumlah yang banyak.

Fakta lain yang menarik dari bilangan Prima adalah bilangan Prima kembar (Twin Prime Numbers), yaitu dua bilangan Prima yang berurutan. Sebagai contoh (2,3), (3,5), (5,7), (11,13), (17,19), (18383549,18383551) dan seterusnya. Pertanyaannya adalah: Apakah pasangan bilangan Prima kembar tersebut ada berhingga buah atau ada tak hingga buah? Sampai saat ini belum ada matematikawan yang berhasil menjawab pertanyaan tersebut.

Nah, jika kalian berminat mencari bilangan Prima yang cukup besar, kita bisa manfaatkan Microsoft Excel dengan modal bilangan Prima yang sudah kita tahu dari saringan Eratosthenes, yaitu 2, 3, … ,97. Cara yang akan kita gunakan pun menggunakan saringan Eratosthenes. Dengan modal bilangan Prima yang kurang dari 100 tersebut, kita bisa mencari semua bilangan Prima yang kurang dari 10.000. Mengapa bisa begitu? Ingat untuk mencari bilangan Prima yang kurang dari atau sama dengan n, maka kita harus mempunyai bilangan Prima yang kurang dari atau sama dengan $\sqrt{n}$ . Jad, jika kita mempunyai semua bilangan Prima yang kurang dari atau sama dengan n, maka kita bisa mendapatkan semua bilangan Prima yang kurang dari atau sama dengan $n^2$ .

Untuk keperluan tersebut, kita pelajari dulu operasi MOD. Mod adalah operasi Aritmetika untuk mencari sisa hasil bagi dari dua buah bilangan. Misalnya, 16 Mod 3 = 1 karena 16 dibagi 3 (hasilnya 5) sisanya 1. Jadi, 15 mod 3 = 0 (dengan kata lain 15 habis dibagi 3 atau 3 adalah faktor dari 15), 23 mod 4 = 3 (dengan kata lain 23 tidak habis dibagi 3 atau 3 bukan faktor dari 23).

Konsep yang harus dipahami untuk mencari bilangan Prima yang lebih dari 100 dan kurang dari atau sama dengan 10.000 adalah: Jika bilangan tersebut habis dibagi 2, 3, … ,97, maka bilangan tersebut BUKAN bilangan Prima. Misalnya kita akan memeriksa apakah 101 bilangan Prima atau bukan, maka harus dicek 101 mod 2, 101 mod 3, 101 mod 5, …, 101 mod 11. Jika hasil salah satu operasi di atas sama dengan nol, maka 101 bukan bilangan Prima (komposit). Sebaliknya, jika hasil semua operasi di atas tidak sama dengan nol (≠0), maka 101 adalah bilangan Prima.
Langkah pertama adalah menuliskan bilangan ganjil dari 101 sampai 10.000 pada kolom A (Ingat bilangan Prima yang kurang dari 100 sudah kita tahu). Pada sel B1 ketik:
=IF(OR(MOD(A101;2)=0;MOD(A101;3)=0;MOD(A101;5)=0;MOD(A101;7)=0;MOD(A101;11)=0;MOD(A101;13)=0;MOD(A101;17)=0;MOD(A101;19)=0;MOD(A101;23)=0;MOD(A101;19)=0;MOD(A101;31)=0;MOD(A101;37)=0;MOD(A101;41)=0;MOD(A101;43)=0;MOD(A101;47)=0;MOD(A101;51)=0;MOD(A101;53)=0;MOD(A101;59)=0;MOD(A101;61)=0;MOD(A101;67)=0;MOD(A101;71)=0;MOD(A101;73)=0;MOD(A101;79)=0;MOD(A101;83)=0;MOD(A101;89)=0;MOD(A101;91)=0;MOD(A101;91)=0;);”—“;”Bil. Prima”)
Copy sel B1 pada B2, B3, dan seterusnya. Maka kita mendapatkan semua bilangan Prima yang kurang dari 10.000. Ada 1207 bilangan Prima yang didapat. Jika digabung dengan hasil sebelumnya (bilangan Prima yang kurang dari 100) maka kita memperoleh 1232 bilangan Prima.

Perintah OR dalam Excel adalah memilih salah satu atau semuanya. Sintak perintahnya adalah =OR(pilihan_1;pilihan_2,…,pilihan_k). Perintah MOD dalam Excel adalah untuk mencari sisa pembagian suatu bilangan. Sintak perintahnya adalah =MOD(bilangan yang dibagi;bilangan pembagi). Contoh =MOD(14;5) akan menghasilkan 4.
Dengan hasil tersebut kita juga bisa mendapatkan bilangan Prima kembar. Jika kalian tertarik, maka pencarian berikutnya adalah bilangan Prima yang kurang dari 100.000.000 dengan modal bilangan Prima yang kurang dari 10.000. Tentu membutuhkan waktu yang lama untuk mengetik perintah di Excel. Dengan melakukan peekrjaan tersebut, kalian sudah menyerupai pekerjaan Curtis Cooper.
Dengan cara yang sama, kita bisa memeriksa pada n atau p berapa rumus-rumus $F(n) = n^2-n+41$ , $F(n)=2^{2^n}+1$ , dan $F(p)=2^p-1$ menghasilkan bilangan Prima dan bukan bilangan Prima.
Untuk apa matematikawan mencari bilangan Prima yang sangat besar? Sebenarnya itu merupakan salah satu kesenangan. Namun di balik itu, bilangan Prima yang besar digunakan untuk membuat sandi. Gagasannya sederhana, jika kita mempunyai dua bilangan Prima, maka mudah bagi kita untuk mengalikannya. Tetapi jika kita mempunyai bilangan komposit (hasil perkalian sejumlah bilangan Prima yang besar), maka sangat sulit bagi siapa pun untuk memfaktorkannya. Sandi diperlukan jika kita akan mengirim suatu pesan, tetapi pesan itu tidak ingin diketahui oleh pihak musuh. Untuk memahami hal tersebut, silakan download dihttp://personal.fmipa.itb.ac.id/hgunawan/files/2008/01/matematika-persandian.pdf.

Mathematics is wonderful

Kamis, 10 September 2015

Bilangan Prima ( Bagian 3)

Tidak ada komentar:

Posting Komentar

5 Permasalahan Persamaan Lingkaran Beserta Penyelesaiannya

Laporkan Penyalahgunaan