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
