Dalam matematika , bilangan prima adalah bilangan asli yang lebih besar dari 1, yang
faktor pembaginya adalah 1 dan bilangan itu sendiri. 2 dan 3 adalah bilangan
prima. 4 bukan bilangan prima karena 4 bisa dibagi 2. Sepuluh bilangan prima
yang pertama adalah 2, 3, 5, 7, 11, 13, 17, 19, 23 dan 29.
Jika suatu bilangan yang lebih besar dari
satu bukan bilangan prima, maka bilangan itu disebut bilangan komposit . Cara
paling sederhana untuk menentukan bilangan prima yang lebih kecil dari bilangan
tertentu adalah dengan menggunakan saringan
Eratosthenes Secara
matematis, tidak ada "bilangan prima yang terbesar", karena jumlah
bilangan prima adalah tak terhingga.
Bilangan prima terbesar yang diketahui per 2013 adalah
257,885,161 − 1. Bilangan
ini mempunyai 17,425,170 digit dan merupakan bilangan
prima Mersenne yang
ke-48. M57885161 (demikian notasi penulisan bilangan prima Mersenne ke-48) ditemukan
oleh Curtis Cooper pada 25 Januari 2013 yang merupakan profesor-profesor dari
University of Central Missouri bekerja sama dengan puluhan ribu anggota lainnya
dari proyek GIMPS .
Jadi bilangan prima adalah
bilangan-bilangan sail/asli yang hanya bisa dibagi dirinya sendiri dan
satu, atau bilangan yang memiliki 2 faktor, dan angka satu bukan bilangan
prima.
Contoh: 2,3,5,7,11,13,17,….
B. Rumus
Bilangan Prima
Selama berabad-abad, banyak matematikawan
telah mencoba untuk mencari rumusan yang dapat digunakan dalam menentukan
bilangan prima. Semua bilangan prima yang lebih besar dari 2 jelas merupakan
bilangan gasal (ganjil) sehingga orang percaya bahwa untuk suatu bilangan prima
p, -1 juga merupakan bilangan prima. Persamaan ini sama halnya dengan
persamaan yang diungkapkan oleh Mersenne, yakni rumus: = -1, n>1.
Namun, hal tersebut kemudian terbukti tidak benar. Pada tahun 1536, Regius membuktikan bahwa bilangan
-1=2047=23 89, bukan bilangan prima.
Cara yang paling sederhana untuk mencari
bilangan prima adalah dengan menggunakan metode saringan Eratosthenes (Sieve of Eratosthenes),
sebuah karya dari Eratosthenes (240 SM), seorang ilmuwan Yunani Kuno. Cara ini
yang paling sederhana dan paling cepat untuk menemukan bilangan prima,
sebelum saringan Atkin ditemukan pada tahun 2004. Saringan
Atkin merupakan cara yang lebih cepat namun lebih rumit dibandingkan dengan
saringan Eratosthenes.
Misalkan, kita hendak menemukan semua bilangan prima di
antara 1 sampai bilangan bulat 50.
Peragaaun saringan Eratosthenes untuk membuat daftar bilangan kurang dari atau
sama dengan 50
dilakukan sebagai berikut:
1.
Membuat daftar bilangan mulai dari 1 sampai
dengan 50,
2.
Mencoret bilangan 1 dari daftar bilangan
tersebut,
3.
Membiarkan bilangan 2 dan mencoret semua
bilangan kelipatan 2
4.
Membiarkan bilangan 3 dan mencoret semua
bilangan kelipatan 3
5.
Membiarkan bilangan 5 dan mencoret semua bilangan kelipatan 5,
6.
Membiarkan bilangan 7 dan mencoret semua
bilangan kelipatan 7,
7.
Membiarkan semua bilangan yang belum dicoret,
8.
Melihat hasil bilangan yang dibiarkan dan
tidak dicoret.
9.
Mendaftar semua bilangan prima yang kurang
dari 50,
yaitu 2, 3, 5,
7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 dan 47.
(catatan: beberapa bilangan mendapat
pencoretan lebih dari sekali)
|
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
|
Penggunaan saringan
Eratosthenes tidak dapat secara memuaskan untuk menguji langsung suatu bilangan
adalah bilangan prima atau bukan bilangan prima, sehingga banyak “formula” lain
yang dibuat untuk menghasilkan bilangan prima. Rumus atau formula itu antara
lain:
1)
f(n)= -n+41
Untuk
n=1 sampai dengan n=40, diperoleh daftar angka yang merupakan bilangan prima.
Tetapi, untuk n=41 maka f(41)= bukan bilangan prima karena 1681
habis dibagi 1, 41 dan 1681. Dengan demikian, f(n)= -n+41 gagal menjadi
rumus bilangan prima.
2)
f(n)= -79n+1601
Formula
ini gagal menjadi rumus bilangan prima sebab f(81)= -79(81)+1601=1763, di
mana faktor dari 1763 adalaah 1, 41,43 dan 1763, sehingga 1763 bukan bilangan
prima.
3)
f(n)= +1
Rumus
ini dibuat oleh Fermat. Jika secara berturut-turut n diganti dengan 1, 2, 3 dan
4 maka diperoleh semuanya adalah bilangan prima. Tetapi, jika n diganti
dengan 5 maka
f(5)= +1=4.294.967.297.
Hasil ini bukan bilangan prima karena habis dibagi oleh 641. Jadi, rumus Fermat
gagal menghasilkan bilangan prima untuk n=5.
4)
Bilangan prima Sophie Germain. Sebuah
bilangan prima p disebut bilangan prima Sophie Germain bila 2p+1 juga bilangan
prima. Misalnya, 23 adalah bilangan prima Sophie Germain karena 2 23+1=47
juga bilangan prima. Bilangan ini diberi nama sesuai nama matematikawan
Perancis Marie Sophie Germain.
5)
Bilangan prima dengan rumus 3+4k, untuk
k>0. Tentu, rumus ini gagal menghasilkan bilangan prima untuk k=3, karena
3+4(3)=15 bukan
bilangan prima.
6)
Teorema kecil Fermat menyatakan jika
p adalah bilangan prima, maka untuk semua bilangan bulat a, =a(mod p). Ini
berarti, jika kita mengambil sembarang bilangan a, kemudian mengalikan dengan
dirinya sendiri sebanyak p kali dan mengurangi a, hasilnya akanhabis dibagi
dengan p.
Secara
khusus, jika a bukan faktor p, maka (mod p) 1. Teorema ini memberikan
uji yang baik untuk ketidakmiripan. Dengan bilangan bulat n>1, pilihlah
a>1 dan hitung (mod n). jika hasilnya 1, maka n bukan bilangan prima.
Sebaliknya, jika hasilnya=1, maka n mungkin bilangan prima sehingga n mungkin
disebut bilangan prima semu basis a (prima semu, bilangan yang
“mendekati” bilangan prima).
Sebagai
contoh, untuk a=2 dan n=341, maka (mod 341)= (mod 341)= = mod
341=1. Tetapi, 341 bukan bilangan prima karena 341= , sehingga 341 adalah
bilangan prima semu basis 2. (umumnya digunakan oleh praktisi kriptografi,
kriptografi adalah teknik untuk menyamarkan suatu pesan dengan kata lain
“sandi”).
Meski
bilangan prima Mersenne terbukti tidak secara pasti benar bahwa rumus tersebut
adalah rumus untuk bilangan prima, namun para peneliti tetap menggunakan rumus
Mersenne dalam mencari bilangan prima. Bilangan prima terbesar yang diketahui
pada September 2006 adalah -1. Bilangan ini mempunyai 9.808.358 digit dan merupakan bilangan prima Mersenne
yang ke-44. (demikian notasi penulisan bilangan prima Mersenne ke-44) ditemukan
oleh Curtis Cooper dan Steven Boone pada 4 september 2006 yang keduanya adalah
profesor university of Sentral Missoouri bekerja sama dengan
puluhan ribu anggota lainnya dari proyek Great Internet Mersenne Prime Search
(GIMPS).
Di
antara semua bilangan prima Mersenne yang sudah ditemukan, sepuluh bilangan
terbesarnya ditemukan dengan GIMPS. Bilangan prima Mersenne terbesar saat ini
memiliki 9.808.358
digit angka.
C.
Teorema Bilangan Prima
Sebelum membahas teorema tentang bilangan
prima, terlebih dahulu dijelaskan istilah saling prima. Dua buah
bilangan dikatakan saling prima jika faktor persekutuan terbesar (FPB) dari dua
bilangan tersebut adalah 1. Istilah lain dari saling prima adalah komprima atau prima
relatif. Jadi defenisi saling prima dapat dituliskan sebagai berikut.
“Dua bilangan bulat a dan b dikatakan komprima, jika (a,b)=1”
Apabila (ab )=1 maka juga dikatakan
saling prima. Bilangan bulat positif dikatakan saling prisma dua-dua
atau saling prima sepasang, apabila ( )=1, untuk i=1, 2, 3,…., n dan j=1,
2, 3,…., n dengan i j. contoh (7, 8, 15)=1,sehingga dikatakan bahwa 7, 8 dan 15saling prima dan sekaligus saling prima
dua-dua, sebab (7,8)=(7,15)=(8,15)=1. Contoh lain (4, 6, 9, 10) =1 menunjukkan
bahwa 4, 6, 9 dan 10 saling prima, tetapi tidak saling prima dua-dua, sebab
(4,6)=2, (4,10)=2, (6,9)=3, (6,10)=2 meskipun (4,9)=(9,10)=1.
a.
Teorema 6.1
“Jika
sisa pembagian b oleh a adalah prima relatif dengan a, maka b juga prima relatif
dengan a.”
Bukti:
Misalkan
a dan b adalah bilangan-bilangan bulat
dan a=0, maka menurut algoritma pembagian diperoleh: b=aq+r dengan
Misalnya,
(a,r)=1. Apakah (b,a)=1?
Misalkan
(b,a)=d, maka dan d|b
Karena
b=aq+r dengan d dan d|b maka d|r
Selanjutnya
dan d|r, sehingga d merupakan faktor persekutuan dari a dan r.
Tetapi,
karena (a,r)=1, maka d 1.
Mengingat
(b,a)=d, yaitu d 1, maka d=1.
Maka,
(b,a)=1
Contoh:
Misalkan
81 dan 266, dengan 266=(81)(3)+23. Perhatikan bahwa (81,23)=1, maka menurut teorema
1 (266,81)=1. Hal ini dapat dilihat pada Algorotma Euclides.
b.
Teorema 6.2
“Setiap
bilangan bulat n>1 dapat dibagi oleh suatu bilangan prima. Dengan perkataan
lain, jika n adalah
bilangan komposit, maka ada bilangan prima p sehingga p|n.
Bukti:
Cara
I
1.
Ambil sembaraang bilangan positif n>1.
Jika n bilangan prima maka berarti teorema terbukti.
2. Apabila
n adalah bilangan komposit, maka n mempunyai faktor selain 1 dan n sendiri.
Misalnya , yaitu maka ada sehingga n= dengan 1< <n.
3. Ambil
bilangan prima sehingga , dengan demikian teorema terbukti. Tetapi,
jika suatu bilangan komposit, maka mempunyai faktor selain 1
dan , misalnya , yaitu | sehingga ada sehingga ,
1< < .
4. Ambil
bilangan prima sehingga . Karena dan |n maka . Jadi, n terbagi
oleh suatu bilangan prima , sehingga teorema terbukti. Tetapi, jika suatu
bilangan komposit, maka mempunyai faktor selain 1 dan ,
misalnya , yaitu . Ini berarti ada sedemikian sehingga = dengan
1< < .
5. Ambil
bilangan prima dan dengan dan yang berimplikasi sehingga
teorema terbukti. Tetapi, jika suatu bilangan komposit,
proses seperti di atas dapat dilanjutkan sedemikian sehingga didapatkan suatu
barisan n, , ,….,dengan n> >>……>1.
Penguraian atas
faktor-faktor komposit tersebut tentu berakhir pada suatu faktor prima, karena
faktor-faktor tersebut selalu kurang dari bilangan yang diuraikan dan selalu
lebih dari 1.
Cara II
1. Misalkan
tidak ada bilangan prima p yang memenuhi dan S adalah himpunan semua
bilangan komposit yang tidak mempunyai faktor prima dengan S.
2. Karena
S dan S N maka menurut prinsip terurut rapi , S mempunyai unsur
terkecil m.
3. Misalkan
m S maka m= . dengan 1< <m dan
1< <m, S, sebab m adalah unsur terkecil S,
berarti adalh bilangan prima atau bilangan yang mempunyai faktor
prima.
4. Ternyata
terjadi kontradiksi karena m S mempunyai faktor prima. Jadi, S ,
yaitu ada bilangan prima p yang memenuhi .
Contoh:
1. Misalkan
n=17 dan n {bilangan prima}, menurut teorema 2, terdapat bilangan prima p
sehingga . Pilih bilangan prima p=17, sehingga .
2. Misal
n=357, dengan n {bilangan
komposit}. Menurut teorema 2, n memiliki faktor selain 1 dan 357 sendirii. Misalkan faktor lain
adalah =3 yaitu , maka ada sedemikian sehingga 357=3 dengan =119 dan 1<199< 357. Karena 119 merupakan bilangan
komposit , maka mempunyai faktor selain 1dan
119 sendiri. Misalkan faktor lain tersebut adalah =7 yaitu , maka
ada sedemikian sehingga 119=7 dengan =17 dan
1<17<119. Karena =17 merupakan bilangan prima, menurut teorema 2, ada
bilangan prima p sedemikian sehingga . Pilih bilangan prima p=17.
c.
Teorema 6.3
“Setiap
bilangan bulat n>1 dapat dinyatakan sebagai hasil kali bilangan-bilangan
prima.”
Bukti:
Cara
I
1.
Ambil sebarang bilangan bulat positif n>1.
Menurut teorema 2, ada suatu bilangan prima sedemikian sehingga .
Karena itu, ada bilangan bulat positif sehingga n= dengan
1< .
2. =1 n= n
{bilangan prima}. Tetapi, jika >1, menurut teorema 2, ada bilangan ,
sedemikian sehingga . Karena itu, ada sedemikian
sehingga dengan 1< < .
3. =1 = n= .
Hal ini berarti n dapat dinyatakan sebagai perkalian bilangan-bilangan prima
(teorema terbukti). Tetapi, jika >1, maka menurut teorema 2, p
{bilangan prima} . Karena itu = dengan 1 < .
4. =1 = n= .
Hal ini berarti n dapat dinyatakan sebagai perkalian bilangan –bilangan prima
(teorema terbukti). Tetapi, jika , maka proses dapat dilanjutkan sehingga pada
akhirnya diperoleh .
5. Penguraian
atas faktor-faktor prima tersebut pasti berakhir karena dan setiap .
Misalnya untuk k, maka diperoleh n= yaitu n dapat dinyatakan
sebagai perkalian bilangan-bilangan prima.
Cara II
1. Bilangan
bulat n>1 memiliki kemungkinan n bilangan prima atau komposit. Jika n
bilangan prima maka n adalah faktor primanya sendiri. jika n bilangan komposit,
maka n dapat difaktorkan katakanlah n= dengan dan .
2. Jika bilangan
prima maka ia adalah faktor prima n. jika bukan bilangan prima,
maka dengan dan dengan
cara yang sama dapat pula berlaku untuk , yaitu mungkin prima atau komposit.
Penguraian faktor komposit pasti berakhir karena faktor-faktornya harus lebih
kecil dari yang diuraikan yaitu bilangan komposit itu sendiri, tetapi harus
lebih besar dari 1. Jadi, kita dapat menyatakan n sebagai hasil kali
bilangan-bilangan prima.
3. Suatu
bilangan positif yang lebih besar dari 1 dapat dinyatakan sebagai perkalian
bilangan-bilangan prima. Jika diantara faktor-faktor prima tersebut ada yang
sama, maka faktor-faktor yang sama dapat ditulis dalam
bentuk dengan adalah faktor-faktor prima
dan merupakan pangkat-pangkat positif.
4. Selanjutnya disebut representasi n
sebagai perkalian bilangan-bilangan prima atau sering pula disebut bentuk
kanonikdari n. teorema 3 sangat membantu untuk menentukan FPB dan KPK dari
2 bilangan atau lebih dengan menyatakan bilangan-bilangan tersebut dalam bentuk
kanoniknya.
5. Misalkan
2 bilangan a dan b, masing-masing dinyatakan
dengan dan dimana dan , (i=1, 2, 3,…..,r). Dengan
demikian FBP dari a dan badalah dan KPK a dan b adalah[a,b]
Contoh :
Ambil nilai a=112 dan
b=212.
Penguraiannya menjadi
faktor-faktor prima:
a=112=(16)(7)=(4)(4 )(7 )
b=212= (4)(53)= (4)( 53)
Dengan demikian FBP dan KPK
diberikan oleh: (a,b)=4 Karena
a dan b keduanya positif, sifat [a,b](a,b)=ab dapat digunakan.
Bukti,
[112,212](112,212)=112 X 212=23744 : 4=5936 .
Cara ini berlaku hanya pada dua bilangan bulat positif.
d.
Teorema 6.4
“Jika
n suatu bilangan komposit, maka n memiliki faktor k dengan 1<k .”
Bukti:
Karena
n suatu bilangan komposit, ada bilangan-bilangan bulat positif k dan m
sedemikian sehingga km=n dengan 1<k<n dan 1<m<n.
Apabila
k dan m kedua-duanya lebih besar dari , yaitu k> dan m> ,
maka n=km> =n(n>n).
Hal
ini tidak mungkin sehingga salah satu dari k atau m harus lebih kecil atau sama
dengan , misalnya k, yaitu 1<k . Jadi, n memiliki faktor k dengan
1<k .
Kontraposisi
teorema 4.
Apabila
bilangan bulat positif n tidak mempunyai faktor k dengan 1<k , maka
n adalah suatu bilangan prima.
Contoh:
Apakah
1003 merupakan bilangan prima atau bukan?
Penyelesaian:
Bilangan
1003 diperiksa keterbagiannya oleh bilangan-bilangan prima yang kurang
dari yaitu 2, 3, 5,
7, 11, 13, 17, 19, 23, 29 dan 31. Karena terdapat bilangan yang dapat membagi
habis 1003 yaitu 17 maka 1003 adalaah bilangan komposit.
e.
Teorema 6.5
“Jika
n (bilangan asli), maka n mempunyai faktor prima terbesar p.”
Bukti:
Misalkan
tidak benar bahwa n mempunyai faktor prima terbesar p ,
berarti n paling sedikit mempunyai dua faktor p dan q> .
Dengan demikian, n=pq> atau n=pq>n. Hal ini menunjukkan suatu
kontradiksi (n>n) yang berarti n mempunyai faktor prima terbesar p .
Contoh:
Contoh
ini merupakan prinsip kerja dari saringan Eratosthenes. Jika n=300 maka
pencoretan dihentikan pada bilangan prima terbesar p yaitu p=17.
Proses yang dilakukan adalah:
a.
Mencari bilangan prima terbesar kurang dari
atau sama dengan
b. Mencoret
semua bilangan kelipatan bilangan prima yang kurang dari atau sama dengan (kecuali
bilangan-bilangan prima itu sendiri)
c. Semua
bilangan yang tersisa adalah bilangan prima
0 Comments:
Posting Komentar