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 2n
– 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][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 = 22.5.13
Prosedur untuk mencari faktorisasi prima dari suatu
bilangan juga dapat menggunakan pohon faktor.
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 = P1q1. P2q2 .
P3q3 . . . Pnqn, maka banyaknya
pembagi n dalam (q1+1) (q2+1) . . . (qn + 1).
Contoh : tentukan semua pembagi 912
Jawaban :
Faktorisasi prima dari 912 adalah 24 . 3
.19 . Ada 5 . 2 . 2 . Atau 20 pembagi. Pembagi-pembagi 24 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 ≤ n⁄p jika p ≤ n⁄p maka p2 ≤ n.
4. Sifat 4
Jika n adalah suatu
bilangan komposit maka n mempunyai suatu faktor prima p sedemikian sehingga p2
≤ 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 p2
≤ 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) = 22n + 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][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][1] http://endangarief-sejmat.blogspot.com/2009/12/sejarah-bilangan-prima.html diakses pada 17 Oktober 2014 pukul 13.45
[2][2]
http://www.bglconline.com/2014/07/penerapan-bilangan-prima/ diakses pada 17 Oktober 2014 pukul 13.45
[3][3] https://asimtot.files.wordpress.com/2010/05/bilangan-prima.pdf diakses pada 17 Oktober 2014 pukul 14.35
[7][7] https://asimtot.files.wordpress.com/2010/05/bilangan-prima.pdf. diakses pada hari jumat, 24 Oktober 2014 pukul 16.34
Tidak ada komentar:
Posting Komentar