Menentukan Pembagi Bersama Terbesar dengan Algoritma Marcelinus Henry M. (13512082) Program Studi Teknik Informatika Sekolah Teknik Elektro dan Informatika Institut Tekonlogi Bandung, Jl. Ganesha 10 Bandung 40132, Indonesia
[email protected]
Abstract - Dalam berbagai persoalan bilangan, pembagi persama terbesar atau yang biasa disebut PBB (greatest common divisor atau gcd) memegang peranan penting dalam beberapa persoalan bilangan dari yang sederhana hingga yang sangat kompleks sekalipun. PBB juga memegang peranan dalam kehidupan sehari-hari tanpa kita sadari. Makalah ini akan menjelaskan berbagai algoritma yang dapat digunakan untuk mengetahui nilai PBB dari dua bilangan bulat atau lebih. Index Terms - bilangan bulat, faktor, algoritma Euclidean, pohon faktor
I. PENDAHULUAN Euclid, matematikawan Yunani yang lahir pada 350 SM, menuliskan sebuah buku yang berjudul Element. Di dalam buku ini, dituliskan langkah-langkah untuk mencari nilai pembagi bersama terbesar (PBB) dari dua buah bilangan bulat m dan n, yaitu bilangan positif terbesar yang habis membagi dua bilangan tersebut. PBB banyak digunakan dalam membahas berbagai teori bilangan yang ada dan juga untuk kehidupan sehari-hari. Maka dari itu, mencari nilai PBB dari beberapa bilangan sangat penting ntuk diketahui dan dipelajari.
II. TEORI 2.1 Definisi Bilangan Bulat Bilangan bulat adalah bilangan yang tidak mempunyai komponen pecahan atau desimal. Bilangan bulat terdiri dari bilangan cacah (0, 1, 2, 3, …) dan negatifnya (-1, -2, -3, …; -0 adalah sama dengan 0 sehingga tidak lagi dimasukkan secara terpisah). Himpunan semua bilangan bulat dalam matematika dilambangkan dengan , berasal dari Zahlen (bahasa Jerman untuk “bilangan”).
2.2 Sifat-sifat operasi bilangan bulat 2.2.1 Closure Jika a dan b adalah bilangan bulat, maka nilai penjumlahan dan perkalian dari a dan b juga merupakan bilangan bulat. Jika a, b maka a b ab 2.2.2 Asosiatif Jika a, b, dan c adalah bilangan bulat, maka penjumlahan dan perkalian dari ketiga bilangan tersebut sama hasilnya tanpa memperhatikan operasi penjumlahan atau perkalian yang didahulukan. Jika a, b, c maka a (b c) (a b) c
a(bc) (ab)c 2.2.3 Komutatif Jika a dan b adalah bilangan bulat, maka penjumlahan dan perkalian dari kedua bilangan tersebut sama hasilnya tanpa memperhatikan urutannya. Jika a, b maka ab ba ab ba 2.2.4 Identitas Jika a maka a0 a a.1 a 2.2.5 Invers Jika a maka a ( a) 0 2.2.6 Distributif Jika a, b, c maka a(b c) ab ac 2.3 Sifat pembagian pada bilangan bulat Misalkan a dan b bilangan bulat, a 0. a habis membagi b jika terdapat bilangan bulat c sedemikian sehingga b ac. Notasi : a | b jika b ac, c dan a 0. 2.4 Pembagi Bersama Terbesar (PBB) Misalkan a dan b bilangan bulat tidak nol. Pembagi bersama terbesar (PBB – greatest
common divisor atau gcd) dari a dan b adalah bilangan bulat terbesar d sedemikian sehingga d | a dan d | b. Dalam hal ini kita nyatakan bahwa PBB(a, b) d .
60 2
2.5 Teorema Euclidean Teorema 1. Misalkan m dan n bilangan bulat, n 0. Jika m dibagi dengan n maka terdapat bilangan bulat unik q (quotient) dan r (remainder), sedemikian sehingga m nq r dengan 0 r n. Teorema 2. Misalkan m dan n bilangan bulat dengan syarat n 0 sedemikian sehingga m nq r , 0 r n
30 2
15 3
5
Pohon faktor dari 60
72
maka PBB(m, n) PBB(n, r )
2
36
III. Menentukan PBB dari dua buah bilangan atau lebih 3.1 Menentukan PBB dari dua buah bilangan Dalam menentukan PBB dari dua buah bilangan , kita bisa memakai beberapa cara diantaranya yang akan dibahas disini yaitu dengan mendaftar semua faktor bilangan, dengan pohon faktor, dan dengan algoritma Euclidean. 3.1.1 Menentukan PBB dengan mendaftar semua faktor yang mungkin. Ambil 2 buah bilangan, misalkan 60 dan 72. 1 2 3 4 5 6
60 30 20 15 12 10 Tabel faktor dari 60
1 2 3 4 6 8
72 36 24 18 12 9 Tabel faktor dari 72
Dari tabel dapat dilihat bahwa faktor dari 60 : 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 72 : 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72 maka PBB(60, 72) = 12. 3.1.2 Menentukan PBB dengan pohon faktor Kita ambil dua buah bilangan pada cara pertama yaitu 60 dan 72.
2
18 2
9 3
3
Pohon faktor dari 72 Dari pohon faktor tersebut didapat hasil sebagai berikut 60 22 3 5 72 23 32 maka PBB(60,72) 22 3 12 3.1.3 Menentukan PBB dengan algoritma Euclidean Representasi algoritma Euclidean dalam notasi algoritmik Iteratif function pbb(a, b : integer) {Kamus Lokal} t : integer {Algoritma} while (not (b = 0)) do t ← b b ← a mod b a ← t → a Rekursif function pbb(a, b : integer) {Kamus Lokal} {Algoritma}
if (b = 0) then → a else → pbb(b, a mod b) Misalkan a dan b adalah bilangan bulat tak negatif dengan a b. Misalkan r0 a dan r1 b. Lakukan algoritma Euclidean sebagai berikut r0 r1q1 r2 , 0 r2 r1
r1 r2 q2 r3 ,
0 r3 r2
rn 2 rn 1qn 1 rn ,
0 rn rn 1
rn 1 rn qn 0 Menurut teorema 2, PBB(a, b) PBB(r0 , r1 ) PBB(r1 , r2 )
PBB(rn 2 , rn 1 ) PBB(rn 1 , rn ) PBB(rn , 0) rn
Bukti Dari bentuk r0 r1q1 r2 dapat diketahui untuk setiap x dan x | r0 serta x | r1 maka berlaku juga x | r2 karena bentuk diatas bisa diubah menjadi r2 r0 r1q1 . Sehingga
PBB(r0 , r1 ) | r2 PBB(r0 , r1 ) | r1. Maka didapat
dan
PBB(r0 , r1 ) PBB(r1 , r2 ). Dari pembalikannya, dan PBB(r1 , r2 ) | r0 Sehingga didapat
didapat pula PBB(r1 , r2 ) | r1.
PBB(r0 , r1 ) PBB(r1 , r2 ). Dari 2 pertidaksamaan tersebut, dapat disimpulkan
PBB(r0 , r1 ) PBB(r1 , r2 ). Hal ini berlaku seterusnya hingga salah satu dari nilai r bernilai 0. 3.2 Menentukan PBB lebih dari 2 buah bilangan Pada pembahasan 3.1, PBB dari 2 buah bilangan dapat ditentukan dengan 3 cara yaitu dengan mendaftar semua factor yang ada, dengan membuat pohon factor dan dengan menggunakan algoritma Euclidean. Pada bagian ini akan dibahas bagaimana menentukan PBB lebih dari 2 bilangan dengan
cara – cara yang sudah dibahas pada subbab sebelumnya. 3.2.1 Menentukan PBB dengan mendaftar semua factor yang mungkin Kita ambil 3 buah bilangan misalkan 126, 240, dan 180 1 2 3 6 7 9
126 63 42 21 18 14 Tabel faktor dari 124
1 2 3 4 5 6 8 10 12 15
240 120 80 60 48 40 30 24 20 16 Tabel faktor dari 240
1 2 3 4 5 6 9 10 12
180 90 60 45 36 30 20 18 15 Tabel faktor dari 180
Dari tabel dapat dilihat bahwa faktor dari 126 : 1, 2, 3, 6, 7, 9, 14, 18, 21, 42, 63, 126 240 : 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, 30, 40, 48, 60, 80, 120, 240 180 : 1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180 Maka PBB(126, 240,180) 6 3.2.2 Menentukan PBB dengan pohon faktor Kita pakai 3 buah bilangan pada cara 3.2.1 yaitu 126, 240, dan 180.
menentukan PBB dari 2 buah bilangan saja. Namun, dengan sedikit modifikasi dan pembuktian, kita dapat menggunakan algoritma Euclidean untuk menentukan PPB dari beberapa buah bilangan. Caranya yaitu dengan menggunakan algoritma Euclidean pada bilangan pertama dan kedua, kemudian menggunakan algoritma Euclidean pada hasil algoritma Euclidean yang sebelumnya dan bilangan ketiga. Teruskan proses hingga bilangan terakhir. Misalkan akan dicari PBB dari bilangan bulat a1 , a2 , , an , maka langkah yang dilakukan yaitu PBB(a1 , a2 ) r1
126 2
63 3
21 3
7
Pohon faktor dari 126
240 2
120 2
PBB(r1 , a3 ) r2
60 2
PBB(r2 , a4 ) r3
30 2
PBB(rn 3 , an 1 ) rn 2 PBB(rn 2 , an ) rn 1 Dengan proses tersebut PBB-nya yaitu rn 1 .
15 3
5
Pohon faktor dari 240
180 2
90 2
45 3
15 3
5
Pohon faktor dari 180 Dari pohon faktor tersebut didapat hasil sebagai berikut 126 2 32 7 240 24 3 5 180 22 32 5 Maka PBB(126, 240,180) 2 3 6 3.2.3 Menentukan PBB dengan algoritma Euclidean Seperti yang kita ketahui, bahwa algoritma Euclidean hanya dapat
didapatkan
Bukti Pembuktiannya hampir serupa dengan pembuktian pada algoritma Euclidean untuk mencari PBB dari 2 bilangan. Jika r , dan r | PBB(a1 , a2 ) serta
r | a3 maka PBB(a1 , a2 , a3 ) PBB( PBB(a1 , a2 ), a3 ) Dengan cara yang sama didapat pula PBB(a1 , a2 , a3 ) PBB( PBB(a1 , a2 ), a3 ) Sehingga algoritma dalam notasi algoritmiknya menjadi function pbb2(a : array [1..n] of integer) {Kamus Lokal} i : integer hasil : integer {Algoritma} hasil ← a[1] i traveral [2..n] hasil ← pbb(hasil, a[i]){pemanggilan algoritma Euclidean} → hasil
IV. KESIMPULAN Dari pembahasan diatas dapat disimpulkan pencarian nilai PBB dari banyak bilangan dapat dilakukan dengan banyak cara, diantaranya dengan table factor, pohon factor, dan algoritma Euclidean baik yang murni maupun modifikasi. V.DAFTAR REFERENSI [1] M. Rinaldi, “Diktat Kuliah IF 2091 Struktur Diskrit”, Program Studi Teknik Informatika, 2008, Bandung, Indonesia. [2] http://www.cut-the-knot.org/blue/Euclid.shtml, tanggal akses 16 Desember 2013 pukul 18.00 [3] http://rumus-matematika.com/pengertian-danoperasi-bilangan-bulat/ tanggal akses 15 Desember 2013 pukul 20.00
PERNYATAAN Dengan ini saya menyatakan bahwa makalah yang saya tulis ini adalah tulisan saya sendiri, bukan saduran, atau terjemahan dari makalah orang lain, dan bukan plagiasi. Bandung, 11 Desember 2011
Marcelinus Henry M 13512082
