Persamaan Linear Diophantine

Wew. Posting-an kali ini sedikit telaat.. Alasan utama karena semakin lama, materi semakin naik level (meskipun tidak sulit-sulit amett). Tapi, gw berusaha menerangkannya dengan sejelas-jelasnya biar semuanya bisa ngertii..

Nah, sekarang kita akan memasuki babak yang sedikit berbeda dengan pelajaran SMP atau SMA (loh memank di sini ga ada pelajaran sekolah khan yakk). Ini mengenai persamaan diophantine. Lihat di bahasan GCD (algoritma Eulid) karena itu dasar supaya bisa ke sini.

Persamaan diophantine adalah persamaan bersuku banyak ax+by = c, di mana a, b, dan c adalah bilangan-bilangan integer (bulat).

Contoh Persamaan diophantine ax+by=c: 2x+ 4y= 26.

Persamaan linear diophantine ax+by= c mempunyai penyelesaian jika dan hanya jika gcd(a,b) membagi c. Bukti: Bisa dilihat di GCD (algoritma Eulid). Di sana dinyatakan bahwa: . Jadi, c merupakan kelipatan dari gcd(a,b).

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Wew. Jangan stress dulu kawan-kawan. Enjoy aja.. Ini gak susah koq..

Contoh soal 1:
Tentukan semua bilangan bulat x dan y yang memenuhi persamaan berikut:

Jawab:

Mungkin bagi kalian yang penasaran untuk menyelesaikan kasus ini, bisa dengan coba-coba.. Misalnya, jika x = 1, y-nya berapa, dan seterusnya.. Tapi, repott.. ==". Mungkin, 10 tahun lagi baru selese.. Wkwkwkwk
Nah, untuk mendapatkan solusi, kita dari gcdnya dulu: gcd (15,6) = 3.
Namun, ternyata 190 tidak habis dibagi 3. Nah, artinya, persamaan di atas tidak punya solusi untuk semua bilangan bulat x dan y.
Eh, jangan bingung. Jawabannya yah gitu aja.. Wew. Guampang khan..

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Contoh Soal 2:
Tentukan semua bilangan bulat yang memenuhi persamaan berikut:

Jawab:

Wew. Ini soalnya berbeda dengan yang nomor satu.. Cuma beda 190 dengan 189.. Maklum, gw ini males ganti angka.. Jadi, tinggal copy paste aja gitchu.. gak repot... Nah, di sini solusinya jelas berbeda.

Pertama, kita tentukan gcd-nya dulu pake algoritma Euclid.
15 = 6 x 2 +3
6 = 3 x 2 + 0.

Nah, remainder/ sisa terakhir kedua (yang di-bold) adalah gcd-nya. Jadi, gcd(15,6) = 3. Lalu, perhatikan bahwa 189 itu habis dibagi 3 (atau 3 189). Artinya, persamaan itu punya solusi x dan y.
Lalu, ambil persamaan terakhir (Untuk lebih jelasnya, lihat bahasan GCD bagian pengembangan algoritma Euclid / identitas Bezout):

3 = 15 - 6 x 2
3 = 1 x 15 - 2 x 6 (dikali 63)
189 = 63 x 15 - 126 x 6

Nah, dari sini, kita sudah mendapatkan satu solusi, yaitu x = 63 dan y = -126 (lihat bentuk gcd(a,b)=ax+by)... Tapi, yang diinginkan di soal adalah semua solusi. So, bagaimana caranya.?? Sekarang, kita cari gradiennya: m= -¹⁵/₆ = -⁵/2(harus disederhanakan!). Nah, inget lah bahwa jika titiknya ditambah dengan gradien, maka hasilnya adalah bilangan bulat juga. Jadi, kita mendapatkan semua solusi dalam bentuk parameter k sebagai berikut:
y = -126 - 5 k
x = 63 + 2k, untuk k adalah semua bilangan bulat.

Tanda plus minus boleh terbalik. Jadi, hasilnya bisa saja seperti ini:
y = -126 + 5 k
x = 63 - 2k, untuk k adalah semua bilangan bulat.

Jika, dirasa angka 126 dan 63 terlalu besar, maka dapat dikecilkan dengan memasukkan sembarang angka k, misalnya k= 30.

Maka: y = -126 + 5.30 = 24 dan x = 63 - 2.30 = 3. Jadi, persamaannya menjadi seperti ini:
y = 24 + 5k
x = 3 - 2k, untuk k semua bilangan bulat.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Aku kasih contoh lagi yg semodel dengan contoh 2 yaa, biar tambah jagoo..
Contoh soal 3:
Tentukan semua bilangan bulat yang memenuhi persamaan berikut:

Jawab:
Huehue.. Biar sesuai dengan tahunnya donkx.. 2008...
LAgi-lagi, gunakan algoritma Euclid:
155 = 1 x 128 + 27
128 = 4 x 27 + 20
27 = 1 x 20 + 7
20 = 2 x 7 + 6
7 = 1 x 6 + 1
6 = 6 x 1 + 0
gcd(155,128) adalah 1. Karena 1 2008, maka persamaan tersebut punya solusi.

Lalu, ubah bentuk algoritma di atas menjadi identitas diophantine. (ambil persamaan kedua terbawah)

1 = 7 - 1 x 6
1 = 7 - (20 - 2 x 7)
1 = 3 x 7 - 20
1 = 3 x (27 - 20) - 20
1 = 3 x 27 - 4 x 20
1 = 3 x 27 - 4 (128 - 4 x 27)
1 = 19 x 27 - 4 x 128
1 = 19 (155 - 128) - 4 x 128
1 = 19 x 155 -23 x 128
Lalu, kalikan dengan 2008, hasilnya:
2008 = (38152) x 155 + (-46184) x 128

Note: jujur angkanya jelek.. wew..
Jadi, kita mendapatkan x dan y-nya: x = -46184 dan y = 38152
Cari gradiennya: m = - (¹²⁸/₁₅₅) ==> sudah tidak bisa lebih sederhana...
Maka hasilnya:
y = 38152 -128 k
x = -46184 +155k, untuk k semua bilangan bulat.

Jika ingin angkanya lebih tidak rumit, maka masukkan saja misalnya k =298, maka:
y = 38152 - 128. 298 = 8 dan x = -46184 + 155.298 = 6, maka hasilnya:
y = 8 - 128 k
x = 6 + 155 k, untuk semua k bilangan bulat.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Contoh Soal 4:
Tentukan semua bilangan bulat POSITIF yang memenuhi persamaan berikut:

Jawab:
37 = 2 x 13 + 11
13 = 1 x 11 + 2
11 = 5 x 2+ 1
2 = 2 x 1 + 0.
gcd (13,37) = 1. Satu membagi 200. Artinya punya solusi.
1 = 11 - 5 x 2
1 = 11 - 5 x (13 -11)
1 = 6 x 11 - 5 x 13
1 = 6 x (37 - 2 x 13) - 5 x 13
1 = 6 x 37 - 17 x 13
Kalikan semua dengan 200
200 = 1200 x 37 - 3400 x 13
Maka, x = -3400 dan y = 1200.
gradien = m = - (¹³/₃₇)

Maka, nilai x dan y-nya adalah:
y = 1200 -13 k
x = -3400 + 37k
Namun, ini belum selesai. Coba lihat kembali apa yang diminta soal: bilangan bulat POSITIF. Artinya nilai x dan y harus > 0.

y > 0 1200 - 13 k > 0 13k 1200 k 92 4/13 ... (i)

x > 0 -3400 + 37k>0 37 k > 3400 k > (3400/37) k > 91 33/37... (ii)

91 ³³/₃₇ k 92 ⁴/13

k = 92

Maka, hanya ada satu solusi x dan y, yaitu jika nilai k =92.
y = 1200 -13.92 = 4
x = -3400 + 37.92 = 4.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Hueee. Akhirnyaa.. , postingan mengenai diophantine selesai juga... Ini buatnya berjam-jam... >.<

Misalnya kalo ada yang bingung, silakan laporrr.. Aku akan bersedia menjawab..
So, ada yg bingung ga nieh.??

Sumber: Olimpiade Matematika SMA (Suwah Semibiring): Yrama Widya