Algoritma Euclide dan Persamaan linear Diophantine

  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.