matematika: Bilangan Prima

BAB I

       PENDAHULUAN

A.    LATAR BELAKANG

Dalam pembelajaran matematika telah kita ketahui ada macam-macam bentuk bilangan. Seperti bilangan genap, ganjil, bulat asli, real dan salah satunya yakni bilangan prima. Sejak sekolah dasar tentu kita telah mengetahui apa itu bilangan prima. Bilangan prima yakni bilangan yang hanya mempunyai dua fakor yakni satu dan dirinya sendiri. Bagi sebagian orang tentu belum banyak yang tau tentang manfaat dan keuntngan apa saja yang dapat dihasilkan dengan operasi pada bilangan prima, bagaimana sejarah bilangan prima dari awal, sifat sifat bilangan prima, cara menentukan bilangan prima dll. Dengan makalah ini akan dibahas lebih lanjut tentang bilangan prima.

B.     RUMUSAN MASALAH

1.      Bagaimana sejarah bilangan prima dan  apa manfaatnya?

2.      Apa definisi bilangan prima., komposit dan faktorisasai prima?

3.      Bagaimana sifat-sifat bilangan prima?

4.      Bagaimana dengan perumusan bilangan prima yang gagal?

BAB II

PEMBAHASAN

A.    SEJARAH BILANGAN PRIMA

Bilangan prima telah dipelajari selama ribuan tahun. Buku “Elements” karya Euclid diterbitkan sekitar 300 tahun sebelum masehi yang menjadi bukti beberapa hasil terkait bilangan prima. Pada bagian IX dari “Elements”, Euclid menulis kemungkinan terdapat begitu banyak bilangan prima, mendekati tak hingga. Euclid juga memberi bukti teori dasar dari Aritmatika, dimana setiap bilangan bulat dapat ditulis sebagai hasil perkalian bilangan prima secara unik.

Pada buku “Elements”, Euclid menyelesaikan masalah tentang bagaimana menciptakan angka sempurna, dimana bilangan bulat positif setara dengan jumlah dari pembagi positif, menggunakan bilangan prima Marsenne. Bilangan prima Marsenne merupakan bilangan prima yang dapat dihitung lewat persamaan 2ⁿ – 1. Bilangan Marsenne termasuk angka terbesar yang pernah terungkap.

Pada tahun 200 sebelum masehi, Eratosthenes membuat algoritma untuk menghitung bilangan prima, yang dikenal juga sebagai Saringan Eratosthenes. Algoritma merupakan salah satu algoritma yang pertama kali ditulis. Eratosthenes meletakkan angka pada kotak dan mencoret berbagai angka yang tergolong kelipatan dan akar kuadrat sehingga angka tersisa merupakan bilangan prima.

Namun saat Dark Ages, dimana intelektual dan sains mengalami tekanan, tidak ada lagi karya berikutnya yang membahas bilangan prima. Pada abad ke 17, ahli matematika seperti Fermat, Euler, dan Gauss mulai memeriksa pola yang muncul pada bilangan prima. Konjektur dan teori yang dibuat para ahli matematika disaat itu menciptakan revolusi dari matematika, dan beberapa diantaranya masih dibuktikan hingga saat ini.[1]

B.     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.[2]

C.    DEFINISI BILANGAN PRIMA

Bilangan prima adalah bilangan bulat positif (bilangan asli) yang lebih dari satu yang mempunyai hanya dua faktor atau yang mempunyai tepat dua pembagi, yaitu satu dan dirinya sendiri[3]. Berikut suatu tabel yang menunjukan banyaknya pembagi atau faktor dari bilangan.

1 1

2 2 3 5 7 11 13 17 19 23 29 31 37

3 4 9 25

4 6 8 10 14 15 21 22 26 27 33 34 35

5 15

6 12 18 20 28 32

7

8 24 30

Berdasarkan tabel di atas, dapat dilihat bahwa untuk kolom pertama hanya bilangan 1 yang mempunyai 1 faktor. Pada kolom kedua terlihat bahwa semua bilangan yang ada pada kolom tersebut hanya mempunyai 2 faktor. Setiap bilangan yang ada pada kolom ketiga mempunyai 3 faktor.

Kolom keempat mempunyai 4 faktor, kolom kelima mempunyai 5 faktor, kolom keenam mempunyai 6 faktor, dan kolom kedelapan mempunyai 8 faktor. Sementara untuk kolom ketujuh tidak ada bilangan yang mempunyai 7 faktor.

Sebarang bilangan bulat positif yang mempunyai tepat dua pembagi positif berbeda disebut bilangan prima. Sebarang bilangan bulat yang lebih besar dari 1 yang mempunyai faktor positif selain 1 dan dirinya sendiri disebut bilangan komposit. Contoh : bilangan 4,6, dan 16 adalah bilangan komposit karena bilangan-bilangan itu mempunyai suatu faktor selain 1 dan dirinya sendiri. Bilangan 1 hanya mempunyai 1 faktor sehingga 1 bukan bilangan prima dan juga bukan bilangan komposit.

Bilangan prima tersebut hanya satu yang merupakan bilanga genap, yaitu 2. Karena bilangan genap selanjutnya merupakan bilangan kelipatan 2, sehingga bilangan genap selain 2 adalah bilangan komposit.

D.    FAKTORISASI PRIMA

Suatu faktorisasi yang memuat hanya bilangan-bilangan prima disebut faktorisasi prima. Untuk menentukan faktorisasi prima dari suatu bilangan komposit yang diberikan, pertama kita tulis kembali bilangan tersebut sebagai suatu hasil kali dua bilangan-bilangan yang lebih kecil, kemudian pemfaktoran bilangan-bilangan yang lebih kecil sampai seluruh faktor-faktor adalah bilangan-bilangan prima.[4]

Contoh :

Perhatikan bilangan 260

260 = 2.2.5.13 = 2²_.5.13

Prosedur untuk mencari faktorisasi prima dari suatu bilangan juga dapat menggunakan pohon faktor.

     260

       

  2          130

             

     2          65

                      

              

              

5                 13

     Lima Sifat Bilangan Prima

1)      Sifat 1 (teorema dasar aritmatika)

Setiap bilangan komposit dapat di tulis juga sebagai hasil kali bilangan prima dalam satu dan hanya satu cara. Sifat ini merupakan dasar untuk menemukan faktorisasi prima dari suatu bilangan. Contoh : bilangan 260. Untuk menemukan faktor prima dari bilangan 260, maka kita mulai membagi bilangan 260 dengan bilangan prima terkecil yaitu 2, lalu kita periksa apakah 2 adalah pembagi bilangan itu. Jika tidak maka kita coba dengan bilangan prima yang lebih besar berikutnyadan kita periksa keterbagiannya oleh bilangan prima ini.

2)      Sifat 2

Jika faktorisasi prima suatu bilangan n adalah n = P₁^q1. P₂^q2 . P₃^q3 . . . P_n^qn, maka banyaknya pembagi n dalam (q₁+1) (q₂+1) . . . (q_{n +} 1).

                     Contoh : tentukan semua pembagi 912

                     Jawaban :

   Faktorisasi prima dari 912 adalah 2⁴ . 3 .19 . Ada 5 . 2 . 2 . Atau 20 pembagi. Pembagi-pembagi 2⁴ adalah 1,2,4,8 dan 16. Pembagi-pembagi 3 adalah 1 dan 3. Pembagi-pembagi 19 adalah 1 dan 19. Dengan demikian pembagi-pembagi 912 adalah 1 , 2, 4, 8, 16, 3, 6, 12, 24, 48, 19, 38, 76, 152, 304, 57, 114, 228, 456, dan  912.

3)      Sifat 3

Misalkn d ≠ 0 dan n ≠ 0. jika d adalah faktor n, maka  ⁿ/d adalah faktor dari n. contoh : Misalkan p adalah faktor prima terkecil dari bilangan n. Dengan menggunakan sifat 3, ⁿ⁄p adalah suatu faktor dari n. karena p adalah faktor terkecil dari n, kita peroleh p ≤   ⁿ⁄p jika p ≤  ⁿ⁄p maka p² ≤ n.

4)      Sifat 4

Jika n adalah suatu bilangan komposit maka n mempunyai suatu faktor prima p sedemikian sehingga p^{2 ≤} n.

Sifat 4 ini dapat digunakan untuk menentukan suatu bilangan yang diberikan termasuk bilangan prima atau bilangan komposit. Contoh : bilangan 109. Jika 109 adalah bilangan komposit, maka 109 harus mempunyai suatu faktor prima p sedemikian sehingga p² ≤ 109. Bilangan-bilangan prima yang dikuadratkan tidak melewati 109 adalah 2, 3, 5, dan 7. Kita tahu bahwa 2, 3, 5 dan 7 masing-masing bukan merupakan faktor dari 109. Dengan demikian 109 adalah bilangan prima.

5)      Sifat 5

    Jika n suatu bilangan bulat lebih besar dari 1 dan tidak dapat dibagi oleh sebarang bilangan prima p maka n adalah bilangan prima. Salah satu cara untuk menemukan seluruh bilangan prima yang lebih kecil dari suatu bilangan bulat yang diberikan adalah dengan menggunakan saringan Eratoshenes : Jika semua bilangan asli lebih besar 1 ditempatkan pada suatu “saringan” maka bilangan yang bukan bilangan prima diberi tanda silang (artinya jatuh melalui lobang saringan). Bilangan-bilangan yang tersisa adalah bilangan-bilangan prima.

    Berikut contoh bagaimana saringan Eratosthenes bekerja. Buat kotak 10 x 10 berisi bilangan 1 – 100. Selanjutnya kita akan mencoret angka kelipatan 2, 3, 4, 5, 6, 7, 8, 9, dan 10 karena 10 merupakan akar kuadrat dari 100. Saat seluruh angka kelipatan dicoret, kita mesti mencoret angka kelipatan yang tersisa dari bilangan berikutnya. Setelah proses pencoretan angka kelipatan mencapai kelipatan 100 (berarti 50), angka yang tersisa akan menjadi bilangan prima. Saringan ini akan membuat kita mampu memperoleh sejumlah angka bilangan prima.[5]

Tabel Saringan Eratosthenes

1 11 21 31 41 51 61 71 81 91

2 12 22 32 42 52 62 72 82 92

3 13 23 33 43 53 63 73 83 93

4 14 24 34 44 54 64 74 84 94

5 15 25 35 45 55 65 75 85 95

6 16 26 36 46 56 66 76 86 96

7 17 27 37 47 57 67 77 87 97

8 18 28 38 48 58 68 78 88 98

9 19 29 39 49 59 69 79 89 99

10 20 30 40 50 60 70 80 90 100

  

  Prosedur berikut mengilustrasi proses penyaringan ini.

1.      Pada tabel 2 dibawah, berilah tanda silang bilangan 1 karena 1 bukan bilangan prima.

2.      Lingkari bilangan 2 karena 2 bilangan prima.

3.      Silanglah bilangan-bilangan kelipatan 2 karena bilangan-bilangan itu bukan bilangan prima.

4.      Lingkari bilangan 3 karena 3 bilangan prima.

5.      Silanglah bilangan-bilangan kelipatan 3 karena bilangan-bilangan itu bukan bilangan prima.

6.      Lingkari bilangan 5 dan 7, silang bilangan kelipatannya.

Berdasarkan data pada tabel tersebut, berhentilah pada langkah ke-6 karena 7 adalah bilangan prima terbesar yang kuadratnya kurang dari 100. Semua bilangan tersisa yang didaftar dan yang tidak disilang adalah bilangan prima.[6]

E.     PERUMUSAN BILANGAN PRIMA YANG GAGAL

Di bawah ini akan diberikan beberapa perumusan yang gagal menghasilkan bilangan prima secara keseluruhan.

1. F(n) = n2 – n + 41

Pernah diduga bahwa fungsi F(n) = n2 – n + 41 menghasilkan bilangan prima untuk n bilangan asli. Bisa dicheck untuk n = 1, 2, 3, 4, dst. Tetapi ternyata rumus ini gagal ketika n = 41. Karena F(41) = 412 – 41 + 41. F(41) = 412. Yang bukan merupakan bilangan prima. Sekarang bagaimana dengan rumus ini. F(n) = n2 + n + 41. Coba temukan, untuk n berapakah dia tidak prima.

2. G(n) = 2²ⁿ + 1 (baca : (dua pangkat dua pangkat n) tambah 1)

Ini adalah hasil pekerjaan Fermat. Fermat pernah menduga bahwa rumus tersebut adalah menghasilkan bilangan prima. Untuk n = 0, 1, 2, 3, 4 ini merupakan benar bilangan prima. Tetapi pertumbuhan bilangannya sangat besar. Sehingga membuat orang malas menguji kebenaran bilangan itu untuk n yang selanjutnya. Tetapi pada tahun 1732 Leonhard Euler membuktikan bahwa untuk n = 5, G(5) = 4.294.967.297 bukan merupakan bilangan prima. Karena nilai itu sama dengan 641 x 6.700.417. kemudian pada tahun 1880, F. Landry menunjukkan bahwa untuk n = 6 juga bukan merupakan bilangan prima. Dan pada awal tahun 1970 untuk n = 7 juga bukan merupakan bilangan prima. Dan dengan menggunakan computer ternyata yang merupakan bilangan prima hanya lima angka pertama saja. Meskipun gagal, tetapi usaha fermat sangat hebat.

3. 2p-1 Terkaan arsenne

2p – 1. Dinyatakan oleh Marin Marsenne dari Perancis. Dia menyatakan bahwa untuk p bilangan prima maka bentuk 2p – 1 merupakan bilangan prima. Marsenne tahu bahwa untuk p = 11 akan didapatkan 2047. Yang ternyata angka tersebut bukan merupakan bilangan prima karena 2047 = 23 x 89, akan tetapi Marsenne yakin bahwa untuk p > 11, bilangan yang dihasilkan pasti bilangan prima. Tetapi pada tahun 1903, untuk p = 67 dihasilkan 147.573.952.588.676.412.927 yang bukan merupakan bilangan prima karena bilangan itu sama dengan perkalian dari 193.707.721 x 761.838.257.287.[7]

DAFTAR PUSTAKA

Hamdani, Saepul dkk. 2009. Matematika 2 LAPIS PGMI. Surabaya : Amanah Pustaka

https://asimtot.files.wordpress.com/2010/05/bilangan-prima.pdf. diakses pada hari jumat, 24 Oktober 2014 pukul 16.34

http://www.bglconline.com/2014/07/penerapan-bilangan-prima/ diakses pada 17 Oktober 2014 pukul 13.45

http://endangarief-sejmat.blogspot.com/2009/12/sejarah-bilangan-prima.html diakses pada 17 Oktober 2014 pukul 13.45

---

[1] http://endangarief-sejmat.blogspot.com/2009/12/sejarah-bilangan-prima.html diakses pada 17 Oktober 2014 pukul 13.45

[2]  http://www.bglconline.com/2014/07/penerapan-bilangan-prima/ diakses pada 17 Oktober 2014 pukul 13.45

[3] https://asimtot.files.wordpress.com/2010/05/bilangan-prima.pdf diakses pada 17 Oktober 2014 pukul 14.35

[4] Saepul Hamdani, Matematika 2 LAPIS PGMI, (Surabaya, Amanah Pustaka : 2005 ) hal. 5-8

[5] Ibid, hal. 9-10

[6] Ibid, hal.10

[7] https://asimtot.files.wordpress.com/2010/05/bilangan-prima.pdf. diakses pada hari jumat, 24 Oktober 2014 pukul 16.34