Campuran

Soal dan Pembahasan Algoritma Euclid dan Persamaan Diophantine (1-2)

Algoritma Euclid adalah salah satu cara yang tepat untuk menentukan persekutuan terbesar (FPB) dua bua angka. Kalian bisa membaca pengertian algoritma euclid terlebih dahulu.

Persamaan Diophantine adalah salah satu cara yang digunakan untuk menentukan himpunan penyelesaian sebuah persamaan linear 2 variabel. Persamaan Diophantine sangat berhubungan dengan Algoritma Euclid. Kalian bisa membaca pengertian persamaan diophantine terlebih dahulu.

Materi Algoritma Euclid dan Persamaan Diophantine memanfaatkan sifat-sifat pembagian atau Modulu.

Perhatikan tiga contoh soal berikut ini:

1. Tentukan nilai x dan y pada persamaan 58x + 23y = 128?

Soal ini ditanyakan oleh @maulanaayub57
maulanaayub57_pict

Penyelesaian:

  • Cari Faktor Persekutuan Terbesar dari koefisien x dan koefisien y dengan menggunakan Algoritma Euclid.

Jika ax + by = c dengan a > b maka Teorema Euclidnya:

a = n.b + r1     -----> (sistem modulo)

n adalah sebuah angka yang jika dikalikan dengan b, mendekati hasil a.

r1 adalah sisa pembagian. Jika r1 = 0. maka operasinya berhenti dan nilai b ditetapkan sebagai FPB. Tetapi jika r1 > o, maka operasi Euclidnya dilanjutkan dengan:

b = n.r1 + r2.

Jika r2 masih lebih besar daripada nol, maka dilanjutkan sampai menemukan r = 0.

r1 = n.r2 + r3.

Kembali pada soal, 58x + 23y = 128.

FPB dari 58 dan 23 adalah

a = n.b + r1

58 = 2.23 + 12  <----->   12 = 58 - 2.23 (tahap I)

23 = 1.12 + 11   <-----> 11 = 23 - 1.12 (tahap II)

12 = 1.11 + 1   <-----> 1 = 12 - 1.11 (tahap III)

11 = 11.1 + 0 (berhenti)

Jadi, FPB nya adalah 1.

  • Gunakan aturan Persamaan Diophantine untuk penentuan nilai x dan y.

58x + 23y = 128

Mulailah dari tahap III pada Algoritma Euclid

1 = 12 - 1.11

Transformasi/ubah angka 11 menjadi seperti tahap II.

1 = 12 - 1(23 - 1.12)

Cari bilangan n yang jika dikali dengan 12 kemudian dikurangi dengan nilai m yang dikali dengan 23, hasilnya sama dengan 1.

1 = n.12 - m.23 , didapat:

1 = 2.12 - 1.23

Transformasi/ubah angka 12 menjadi seperti tahap I

1 = 2(58 - 2.23) - 1.23

Cari bilangan n yang jika 2.58 - n.23 = 1

1 = 2.58 - n.23 , didapat:

1 = 2.58 - 5.23

Masing-masing dikalikan dengan 128 agar sesuai dengan nilai c pada soal ax + by = c  ---> 58x + 23y = 128.

1 = 2.58 - 5.23

1(128) = 2(128).58 - 5(128).23

128 = 256.58 - 640.23

Jadi Himpunan Penyelesaiannya adalah {x,y} = {256 , -640}

Untuk pembahasan sistematis dari soal diatas, perhatikan gambar di bawah ini.

Morsmordre1108

2. Tentukan solusi dari 12378x + 3054y = 6 !

Jawab:

Dengan menggunakan Algoritma Euclid diperoleh persamaan-persamaan:

12378 = 4 . 3054 + 162

3054 = 18 . 162 + 138

162 = 138 + 24

138 = 5 . 24 + 18

24 = 1 . 18 +6

18 = 3 . 6 + 0

Dengan demikian FPB (12378, 3054) adalah 6.

6 habis dibagi oleh 6 sehingga mempunyai penyelesaian bilangan bulat.

Selanjutnya untuk menyatakan 6 sebagai kombinasi linier dari 12378 dan 3054, kita mulai dengan menyatakan dalam persamaan kedua dari terakhir kemudian berturut-turut mengeliminasi sisa pembagian 18, 24, 138 dan 162.

6 = 24 - 1 . 18

= 24 - (138 - 5 . 24)

= 6 . 24 - 138

= 6 . (162 - 138) - 138

= 6 . 162 - 7 . 138

= 6 . 162 - 7 . (3054 - 18 . 162)

= 132 . 162 - 7 . 3054

= 132 . (12378 - 4 . 3054) - 7 . 3054

= 132 . 12378 + (-535) . 3054

Dengan demikian diperoleh:

12378.(132) + 3054.(-535) = 6

Sehingga solusi dari persamaan 12378x + 3054y = 6 adalah (x, y) = (132, -535).

3. Tentukan himpunan penyelesaian dari 20x² + 11y = 2011 ?

Penyelesaian:

Supaya tidak kebingungan dengan variabel x yang kuadrat, alangkah baiknya lakukan permisalan dengan memisalkan x² = a.

Kemudian jika sudah menemukan nilai a nya pada aturan Diophantine, maka tinggal mengakarkan nilai a. -------> a = x.

Keseluruhan pembahasannya, ada pada gambar di bawah ini.

Morsmordre1111Jadi, Himpunan Penyelesaiannya adalah {x,y] = {√10055 , 18099}.

*Semoga Bermanfaat*

2 thoughts on “Soal dan Pembahasan Algoritma Euclid dan Persamaan Diophantine (1-2)

Comments are closed.