Mencari FPB tanpa pemfaktoran

Ketika SD, kita diajarakan mencari FPB (Faktor Persekutuan terBesar) dengan cara pemfaktoran. Nah… kali ini saya kan tunjukan cara lain mencari FPB tanpa pemfaktoran yang dinamakan Algoritma Euclid. Algoritma ini sudah ada 300 sm diambil dari nama matematikawan Yunani kuno, Euclid yang membuat Algoritma tersebut. Mungkin Algoritma Euclid adalah algoritma yang pertama kali dibuat Manusia.

Algoritma

Kita akan mencari FPB dari A dan B dangan A > B. Pertama-tama kita bagi A dengan B. Bilangan yang lebih kecil membagi bilangan yang lebih besar

A ÷ B = C sisa D

Artinya A dibagi B hasilnya adalah C dengan sisa D, kemudian sisa D ini membagi B

B ÷ D = E sisa F

lalu F membagi D

D ÷ F = G sisa H

Begitu seterusnya sampai kita mendapatkan sisa nol. Nah.. pembagi terakhir merupakan FPB dari A dan B

Contoh 1: Hitunglah FPB dari 77 dan 119

119 ÷ 77 = 1 sisa 42

77  ÷ 42 = 1 sisa 35

42  ÷ 35 = 1 sisa 7

35 ÷ 7 = 5 sisa 0

So… diperoleh FPB (77, 119) = 7

Contoh 2: Hitunglah FPB dari 168 dan 232

232 ÷ 168 = 1 sisa 64

168 ÷ 64 = 2 sisa 40

64 ÷ 40 = 1 sisa 24

40 ÷ 24 = 1 sisa 16

24 ÷ 16 = 1 sisa 8

16 ÷ 8 = 2 sisa 0

Diperoleh FPB(168, 132) = 8

Algorima Euclid bisa digunakan untuk menemukan FPB dari beberapa bilagan sekaligus. Misal kita mencari FPB dari bilangan-bilangan berikut

X1, X2, X3 , … , Xn.

yang sudah diurutkan dengan X1 terbesar dan Xn terkecil.
Pertama-tama kita mecari FPB(Xn-1, Xn) = A1 kemudian FPB(Xn-2,A1) =A2 lalu FPB(Xn-3,A2) =A3, begitu seterusnya. sampai mendapat FPB(X1, An-2) =An-1. Nah.. An-1 adalah FPB dari X1, X2, X3 , … , Xn.

Contoh 3: Carilah FPB dari 126, 144 dan 171. Pertama-tama kita akan mencari FPB dari 126 dan 144.
144 ÷ 126 = 1 sisa 18
126 ÷ 18 = 7 sisa 0

Diperoleh FPB(126, 144) = 18. Selanjutnya dicari FPB dari 171 dan 18
171 ÷ 18 = 9 sisa 9
18 ÷9 = 2 sisa 0
Itu berarti FPB dari 126, 144 dan 171 adalah 9

Advertisements

About Aria Turns

Seorang Alumnus Matematika UGM, dengan ilmu yang didapat ketika kuliah (Padahal sering bolos kuliah :p ), saya menyebarkan virus matematika
This entry was posted in Teori Bilangan and tagged , , , , . Bookmark the permalink.

Silahkan, tinggalkan komentar

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s