Home » Matematika » Aljabar » Soal dan Pembahasan Algoritma Euclid dan Persamaan Diophantine (1-2)

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

Arsip

Kategori

Twitter Updates

Algoritma Euclid adalah salah satu cara yang tepat untuk menentukan persekutuan terbesar (FPB) dua bua angka. Istana Mengajar sudah pernah membahas materi ini disini

Persamaan Diophantine adalah salah satu cara yang digunakan untuk menentukan himpunan penyelesaian sebuah persamaan linear 2 variabel. Persamaan Diophantine sangat berhubungan dengan Algoritma Euclid. Info lebih lanjut klik disini

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

Perhatikan 2 contoh soal berikut ini:

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

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 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 Comments

  1. nadtjoe says:

    Makasih ilmunya, keren bgt, coba dari smp udah tau ada cara begini gak pake cara yang nyusahin:)

Diskusi yuk

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: