1. Sifat habis dibagi pada bilangan bulat
Secara umum suatu bilangan yang dapat dibagi dapat dinyatakan kedalam bentuk.
untuk sebarang a dan b, bilangan bulat dengan a ≠ 0, maka terdapat m dan n, bilangan bulat yang tunggal sedemikian sehingga b dapat dinyatakan sebagai
b = (a*m) + n atau b = am + n, dengan 0 ≤ n < │a│
a, kemudian disebut sebagai pembagi, m disebut hasil bagi dan n disebut sebagai sisa hasil bagi. pernyataan b = am + n, biasanya disebut juga sebagai algoritma pembagian. untuk kasus n = 0, maka b dikatakan habis dibagi oleh a. Akibat dari pernyataan tersebut muncul suatu definisi yaitu.
Suatu bilangan bulat b dikatakan habis dibagi oleh suatu bilangan bulat tidak nol, jika ada suatu bilangan bulat m sedemikian sehingga b = am. atau dapat dituliskan sebagai a │ b (dibaca a habis membagi b)
Sifat-Sifat pada hasil bagi.
- jika a│b maka a│bc untuk sembarang c bilangan bulat
- jika a│b dan b│c maka a│c
- jika a│b dan a│c maka a│bx + cy untuk x dan y, sembarang bilangan bulat.
- jika a│b dan b│a maka a = ±b
- jika a│b dan b ≠ 0 maka │a│ ≤ │b│
2. Algoritma Euclide
Defenisi
Diberikan dua bilangan bulat a dan b dengan a > b > 0 maka FPB(a,b) dapat dicari dengan mengulang algoritma pembagian
Contoh :
Tentukan FPB (4840,1512)
Penyelesaian.
4840 = 1512 * 3 + 304
1512 = 304 * 4 + 296
304 = 296 * 1 + 8
296 = 8 * 37 + 0
maka kta peroleh FPB (4840,1512) = 8
Akibat dari teorema Algoritma Euchlide yaitu untuk setiap FPB(a,b) maka terdapat bilangan bulat x dan y sehingga FPB(a,b) = ax + by.
sehingga dari contoh diatas dapat dinyakan sebagai berikut.
8 = 304 - 296
= 304 - [1512 - (304 * 4)]
= (304 * 5) - 1512
= [(4840 - 1512*3)*5 -1512
= 4840 * 5 - 1512 * 16
jadi nilai x = 5 dan y = 16
Akibat Selanjutnya dari teorema algoritma euclide yaitu Persamaan linear diophantine.
3. Persamaan linear Diophantine
Teorema
Suatu Persamaan linear diophantine ax + by = c dengan a, b dan c bilangan bulat mempunyai penyelesaian bilangan bulat, jika dan hanya jika FPB(a,b) membagi habis c.
Contoh
Tentukan penyelesaian umum persamaan diophantine 754x + 221y = 13
Penyelesaian
Dengan menggunakan algoritma euclid diperoleh FPB(754,221) = 13, karena 13│13, akibatnya persamaan diatas mempunyai penyelesaian bilangan bulat.
kita akan mencari nilai dari m dan n sehingga
13 = m * 754 + n * 221 Karena
13 = 5 *754 - 17 * 221 maka m = 5 dan n = -17 jadi penyelesaian umumny adalah.
x = 5 + (221/13) k = 5 + 17 k
y = -17 + (754/13) k = -17 - 58k
dengan k sembarang bilangan bulat.