Faktor Persekutuan Terbesar (FPB) - Matematika Kuliyah

Jika a atau b bilangan-bilangan bulat yang tidak nol, d adalah factor persekutuan terbesar dari a dan b, bila dan hanya bila d factor persekutuan dari a dan b jika factor c persekutuan dari a dan b maka c ≤ d

Kita mengetahui bahwa faktor-faktor 30 adalah 1,2,3,5,6,7,15,dan 30. faktor- faktor 24 adalah 1,2,3,4,6,8,12,dan 24. Maka 1,2,3, dan 6. disebut faktor-faktor peasekutuan.

Suatu algoritma adalah suatu prosedur atau suatu cara untuk meperoleh hasil dengan menerapkan berkali-klali suatu operasi, sedemikian sehingga sebuah unsur yang didapat dari satu kali menerapkan operasi itu dipakai sekurang-kurangnya 1 dalam penerapan berikutnya.

Contoh Algoritma

Jika a = 21 dan b = 75 maka q = 3

dan r = 12

Karena 75 = 3 . 21 + 12

Trlihat bahwa ( 75,21)= 3 dan

21,12 = 3

Jika b=qa + r maka(b,a)=(a,r) Pembagian a dan b akan memberikan (b,a)=(a,r). Karena b=ca+r maka bilangan-bilangan a dan r lebih sederhana daripada b dan a. oleh karena itu untuk menentukan FPB daro a dan b kita menggunakan alogaritma berkali-kali sehingga kita hanya menentukan FPB dari bilangan-bilangan yang masing-masing lebih kecil dari a dan b.

 

Contoh: Misalkan kita akan menghitung (5767,4453)

Dengan menggunakan algoritma pembagian kita peroleh 5767=4453 .1

(5767,4453)=(4453,1314)

Karena bilangan –bilangan ruas kedua dari kesamaan ini masih cukup besar, maka dengan 

menggunakan algoritma lagi kita peroleh

1314=511 . 2 + 292  Dari algoritma pembagian ini maka

  511=292 . 1 + 219  (5767,4453)=(4453,1314)=(219,73)

  292=219 . 1 + 73  (73,0)=73

  219=73 . 1 + 0

Dari pembagian algorima di atas, maka dapat dicari bilangan-bilangan bulat x dan y sehingga ax+by=d

  

contoh:

Jika a=1314 dan b=511, tentukan nilai x dan y sehingga 1314x + 511y =73

Jawab:

•1314=511 . 2 + 292 

•511=292 . 1 + 219 

•292=219 . 1 + 73

•219=73 . 1 + 0

•73  = 292 – 291.1

•511= 292.1 + 219

Maka, nilai x dan y sedemikian hingga

      

   73 = 292. 2 – 511

   73 = (1314 – 511.2).2 -511

   73 = (1314.2 – 511.4) – 511

   73 = 1314.2 – 511.5

Jadi, x=2 dan y= -5 agar 1314x + 511y = 73

Tweet