BILANGAN PRIMA

Makalah

“Bilangan Prima”

 

Kelompok 5

 

 

PRODI PENDIDIKAN MATEMATIKA

PERIODE 2018

 

Kata Pengantar

Segala puji kami hanturkan kepada Allah SWT, karena atas pertolongan-Nya sehingga kami dapat menyelesaikan makalah ini sebagai bahan dalam pemenuhan tugas kelompok mata kuliah Teori Bilangan yang dibimbing oleh Pak Dedy Setyawan S.Pd., M.Pd. Kami juga tak lupa mengucapkan banyak terima kasih kepada berbagai pihak yang telah membantu dalam penyelesaian makalah ini. Makalah ini membahas tentang “Bilangan Prima”.

Kami menyadari makalah ini masih  jauh dari kesempurnaan, maka dari itu kami banyak mengharap kritik dan saran dari pembaca demi kesempurnaan kami dalam menyusun makalah dikemudian hari. Semoga makalah ini dapat bermanfaat baik bagi pembaca maupun bagi kami sebagai penyusun.

 

 

 

Maros, 26 juni 2018

 

Penyusun

 

 

 

 

 

 

Daftar Isi

Halaman Sampul

Kata Pengantar......................................................................................................... ii

Daftar Isi...................................................................................................................iii

BAB I PENDAHULUAN

A.    Latar Belakang............................................................................................ 4

B.     Rumusan Masalah....................................................................................... 4

C.     Tujuan......................................................................................................... 4

BAB II PEMBAHASAN

A.    Pengertian bilangan prima........................................................................... 5

B.     Rumus bilangan prima................................................................................. 5

C.     Teorema bilangan prima.............................................................................. 8

BAB III PENUTUP

A.    Kesimpulan................................................................................................ 13

B.     Saran.......................................................................................................... 13

Daftar pustaka

 

 

 

BAB I

PENDAHULUAN

 

A.  Latar belakang

Bilangan prima memiliki kekhususan dan peran penting yang tidak dimiliki bilangan lain. Selain itu, berbagai kontroversi rumus dan banyaknya bilangan prima juga belum dapat dijelaskan secara tuntas. Dengan adanya pernyataan di atas maka dari itu kami sebagai mahasiswa matematika menyusun makalah yang berjudul Bilangan Prima.

 

B.  Rumusan Masalah

Adapun rumusan masalah dalam makalah ini adalah :

1.      Apa yang dimaksud dengan bilangan prima?

2.      Rumus apa yang dapat digunakan untuk menentukan suatu bilangan prima?

3.      Apa-apa sajakah teorema dari bilangan prima?

 

C.  Tujuan

Tujuan dari makalah ini adalah :

1.      Untuk mengetahui defenisi bilangan prima

2.      Untuk mengetahui cara menentukan bilangan prima dengan menggunakan rumus.

3.      Untuk mengetahui dan dapat membuktikan teorema dari bilangan prima

 

 

 

 

 

 

BAB II

PEMBAHASAN

 

A.  Pengertian bilangan prima

Bilangan prima adalah bilangan asli yang lebih besar dari 1 dan hanya mempunyai 2 faktor, yaitu 1 dan bilangan itu sendiri. Dengan kata lain, bilangan yang hanya bisa dibagi bilangan itu sendiri dan satu. Sedangkan bilangan bulat yang lebih besar dari 1 dan bukan bilangan prima disebut bilangan komposit.

Contoh:

2,3,5,7,11,13,17,19 adalah bilangan-bilangan prima.

4,6,8,9,10,12 adalah bilangan-bilangan komposit.

 

B.  Rumus 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. Peragaan 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.

 

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

(catatan: beberapa bilangan mendapat pencoretan lebih dari sekali)

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 Є N

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²-n+41 gagal menjadi rumus bilangan prima.

2.    f(n)= n²-79n+1601

Formula ini gagal menjadi rumus bilangan prima sebab f(81)= 81²-79(81)+1601=1763, di mana faktor dari 1763 adalah 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)= 2²ⁿ+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 x 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^p=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 a^p-1(mod p) 1. Teorema ini memberikan uji yang baik untuk ketidakmiripan. Dengan bilangan bulat n>1, pilihlah a>1 dan hitung a^n-1(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 2^341-1 (mod 341)=(2¹⁰)³⁴ (mod 341)=( 2¹⁰ mod 341)³⁴= 1³⁴ mod 341=1. Tetapi, 341 bukan bilangan prima karena 341= 11×31, 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 2^32.582.657-1. Bilangan ini mempunyai 9.808.358 digit dan merupakan bilangan prima Mersenne yang ke-44. M_32582657 (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 prima relatif, jika (a,b)=1”

Apabila (a₁, a₂, a₃…a_n) = 1 maka a₁, a₂, a₃…a_n juga dikatakan saling prima. Bilangan bulat positif a₁, a₂, a₃…a_n dikatakan saling prima dua-dua atau saling prima sepasang demi sepasang, apabila (a_i, a_j) = 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 15 saling prima dan sekaligus saling prima dua-dua; sebab (7,8) = (7,15) = (8,15) = 1. Contoh lain (4,6,9,10) = 1. Contoh lain (4, 6, 9, 10) = 1 menunjukkan bahwa 4, 6, 9, dan 10 saling prima, tapi tidak saling prima dua-dua, sebab (4, 6) = 2, (4, 10) = 2, (6, 9) = 3, (6, 10) = 2 meskipun (4, 9) = (9, 10) = 1.

Teorema 6.1

Jika sisa pembagian b oleh a adalah prima relatif dengan a, maka b juga prima reltif dengan a.

Bukti:

Misalkan a dan b adalah bilangan-bilangan bulat dan a  0, maka menurut algoritma pembagian diperoleh bahwa: b= aq+r dengan 0  r < .

Misalnya, (a,r) = 1. Apakah (b,a) = 1 ?

Misalkan (b,a) = d, maka d ǀ b

Karena b= aq+r dengan d│a dan d│b, maka d│r. selanjutnya d│a 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. Jadi (b, a) = 1.

Contoh 6.1 :

misalkan 81 dan 266, dengan 266 = (81) (3) + 23. Perhatikan bahwa (81, 23) = 1, maka menurut teorema 6.1, (266,81) = 1. Hal ini dapat dilihat pada Algoritma Euclides.

 

Teorema 6.2

Setiap bilangan bulat n>1 dapat dibagi oleh suatu bilangan prima. Dengan perkataan lain, jika n  dan n adalah bilangan komposit, maka ada bilangan prima p sehingga p|n.

Bukti:

Jika n adalah bilangan prima maka n│n, jelas. Jika n adalah bilangan komposit, maka n mempunyai faktor selain 1 dan n misalkan d₁. d₁│n, maka ada n₁ sehingga n=d₁n₁. Karena d≠1 dan d1 ≠n, maka 1>n1>n. jika n₁ bilangan prima, maka jelas n₁│n.

Jika n₁ bilangan komposit, maka n₁ mempunyai faktor selain 1 dan n₁ misalkan d₂. d₂│n₁, maka ada n₂ sehingga n₁=d₂n₂. Karena d₂≠1 dan d₂≠n1, maka 1< n₂<n1. Jika n₂ bilangan prima, maka jelas n₂│n₁

Karena n₂│n₁ dan n₁│n, maka n₂│n₁ (jelas)

Jika n₂ bilangan komposit, maka n₂ mempunyai faktor selain 1 dan n₂ misalkan d₃. d₃│n₂, maka ada n₃ sehingga n₂=d₃n₃. Karena d₃≠1 dan d₃≠n₂, maka 1<n₃<n₂. Demikian seterusnya sehingga ada barisan n, n₁, n₂, n₃,…dengan n>n₁>n₂>n₃>… dan setiap n_i>1.

Misalkan nk adalah bilangan prima, maka n_k│n karena n_k│n_k-1, n_k-2, …n₁│n. (teorema terbukti).

 

Teorema 6.3

Setiap bilangan bulat n >1 dapat dinyatakan sebagai hasil kali bilangan-bilangan prima.

 

Bukti:

a.       Ambil sebarang bilangan bulat positif n>1. Menurut teorema 2, ada suatu bilangan prima p₁ sedemikian hingga p₁ ǀ n. Karena itu, ada bilangan bulat positif n₁ sehingga n= p₁ n₁ dengan 1< n₁<n .

b.      n =1  n= p₁  n {bilangan prima}. Tetapi, jika n₁>1, menurut teorema 6.2, ada bilangan  p₂ , sedemikian sehingga p₂ ǀ n₁ . Karena itu, ada n₂ sedemikian sehingga  dengan 1<n2 <n1 .

c.       n₂=1  n₁=p₂  n= p₁p₂ . Hal ini berarti n dapat dinyatakan sebagai perkalian bilangan-bilangan prima (teorema terbukti). Tetapi, jika n₂ >1, maka menurut teorema 2,   p  {bilangan prima}  p₃ ǀ n₂ . Karena itu,  n₃  Z⁺  n₂= p₃n₃  dengan 1 n₃ <n₂ .

d.      n₃=1  n₂=p₃  n= p₁p₂p₃ . Hal ini berarti n dapat dinyatakan sebagai perkalian bilangan –bilangan prima (teorema terbukti). Tetapi, jika n₃>1, maka proses dapat dilanjutkan sehingga pada akhirnya diperoleh n_k=1

Penguraian atas faktor-faktor prima tersebut pasti berakhir karena n>n₁>n₂>n₃>… dan setiap n_i  1  . Misalnya untuk k, n_k= 1 maka diperoleh n=p₁p₂p₃…p_k  yaitu n dapat dinyatakan sebagai perkalian bilangan-bilangan prima.

Contoh:

Ambil nilai a =112 dan b =212.

Penguraiannya menjadi faktor-faktor prima:

a = 112 = (2⁴ ) (7) = (2⁴) (7¹) (53⁰)

b = 212 = (2²) (53) = (2²) (7⁰) (53¹)

Dengan demikian FBP dan KPK diberikan oleh:

(a,b) = 2 ^{min (2,4)} × 7 ^{min (0, 1)} × 53 ^{min (1,0)} = 22 × 70  530  = 4

[a,b] = 2 ^{min (2,4)} 7 ^{min (0, 1)} 53 ^{min (1,0)} = 2⁴ × 7¹ × 53¹ = 5936.

Karena a dan b keduanya positif, sifat [a,b] (a,b) = ab dapat digunakan.

Bukti, [112,212] (112,212) = 112 × 212 = 23744 = 5936 × 4 . Cara ini berlaku hanya pada dua bilangan bulat positif.

Contoh 6.3

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 adalah bilangan komposit.

 

Teorema 6.4

Jika n suatu bilangan komposit, maka n memiliki faktor k dengan 1< k    n.

Bukti:

1.      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.

2.      Apabila k dan m kedua-duanya lebih besar dari  n, yaitu k >  n  dan m >  n , maka n = km >  n ×  n = n (n > n).

3.      Hal ini tidak mungkin sehingga salah satu dari k atau m harus lebih kecil atau sama dengan n, misalnya k, yaitu 1 < k   n. Jadi, n memiliki faktor k dengan 1 < k    n.

Kontraposisi teorema 6.4

Apabila bilangan bulat positif n tidak mempunyai faktor k dengan 1< k    n. , maka n adalah suatu bilangan prima.

Contoh 6.4

Apakah 4567 merupakan bilangan prima atau bukan?

Penyelesaian:

Untuk mengetahui apakah 4567 merupakan bilangan prima atau bukan, kita mencoba mencari bilangan prima yang kurang dari  dan membagi habis 4567. Bilangan-bilangan prima tersebut adalah 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 51, 53, 57, 59, 61, dan 67 < . Karena tidak ada bilangan prima yang kurang dari  yang membagi habis 4567, maka 4567 adalah bilangan prima.

Teorema 6.5

Jika n  N (bilangan asli), maka n mempunyai faktor prima terbesar p sehingga p n.

Bukti:

Misalkan tidak benar bahwa n mempunyai faktor prima terbesar p n , berarti n paling sedikit mempunyai dua faktor p >  n dan q >  n . Dengan demikian, n = pq >  n ×  n  atau n = pq > n. Hal ini menunjukkan suatu kontradiksi (n > n) yang berarti n mempunyai faktor prima terbesar p n .

Contoh 6.5

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  n;

b.      Mencoret semua bilangan bilangan prima yang kurang dari atau sama dengan  n  (kecuali bilangan-bilangan prima itu sendiri);

c.       Semua bilangan yang tersisa adalah bilangan prima.

 

 

 

 

 

BAB III

PENUTUP

 

A.  Kesimpulan

 

Bilangan prima adalah bilangan asli yang lebih besar dari 1 dan hanya mempunyai 2 faktor, yaitu 1 dan bilangan itu sendiri. Dengan kata lain, bilangan yang hanya bisa dibagi bilangan itu sendiri dan satu. Sedangkan bilangan bulat yang lebih besar dari 1 dan bukan bilangan prima disebut bilangan komposit.

Teorema 6.1: Jika sisa pembagian b oleh a adalah prima relatif dengan a, maka b juga prima reltif dengan a.

Teorema 6.2 : Setiap bilangan bulat n>1 dapat dibagi oleh suatu bilangan prima. Dengan perkataan lain, jika n  dan n adalah bilangan komposit, maka ada bilangan prima p sehingga p|n.

Teorema 6.3 :Setiap bilangan bulat n >1 dapat dinyatakan sebagai hasil kali bilangan-bilangan prima.

Teorema 6.4: Jika n suatu bilangan komposit, maka n memiliki faktor k dengan 1< k    n.

Teorema 6.5: Jika n  N (bilangan asli), maka n mempunyai faktor prima terbesar p sehingga p n.

 

B.  Saran

 

Makalah ini disusun dengan tujuan untuk menambah wawasan dan membantu memudahkan kita dalam mengikuti mata kuliah Teori Bilangan terkhusus pada materi bilangan prima. Kami menyadari bahwa dalam penyusunan makalah ini terdapat banyak kekurangan, maka dari itu kami bersedia menerima setiap kritikan dan saran dari pembaca yang bersifat membangun. Semoga dengan makalah ini wawasan semakin bertambah. Untuk itu kami mengucapkan terima kasih yang sebesar-besarnya kepada pembaca dan semua pihak yang telah terlibat dalam penyusunan makalah ini.

Daftar pustaka

 

Tiro.MA.dkk.2008: Pengenalan Teori Bilangan (213-254).Makassar: CV. Andira Karya Mandiri.