Saturday, September 6, 2008

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: ax+by = \text{gcd (a,b)} . 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:
15x+ 6y=190
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:
15x+ 6y=189
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= -15/6 = -5/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:
128x+155y=2008
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 = - (128/155) ==> 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:
13x+37y =200
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 = - (13/37)

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 33/37< k < 92 4/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

29 comments:

  1. woww...bagus banget tutorialnya....
    tambahin terus ya plajaran2 yang lain. aku tunggu lho..

    ReplyDelete
  2. good... it's fantastic..

    gradiennya untuk apa ya? kok selama ini aku belum pernah pake gradien untuk diophantine ya?

    ReplyDelete
  3. Di buku-buku oficial memang ngak disinggung gradien... Tapi, inti pengerjaannya sama seperti yang kutulis di blog ini.. Hwohwohwo.. ^^

    Gradien itu untuk mendapatkan selisih y dan selisih x yang relatif prima, sehingga dapat digunakan untuk mengubah parameter x dan y secara lebih akurat. (Penjelasan yang lebih baik bisa ditemukan di contoh soal di atas). ^^

    ReplyDelete
  4. alhamdulillah akhirnya dapt jg tntang persamaan diophantine..
    maf kl tidak keberatan tlong ksih tw referensinya tntang persamaan diophantine donk ;)

    kl ada jurnal jg g p2. tlg tar dikirim ke arofieta@yahoo.com
    makasih bnyk sebelumnya..

    ReplyDelete
  5. Saya br bljar diophantine tuch...

    jadi masih agak mumet gitcuuu :)

    mhn dijelaskan lagi ya?! gmn untuk ngubah
    parameter ke k???

    trus knp pada contoh 2 variabel y yang dijumlahkan dengan -5 at +5????

    knp bkn -2 at +2???

    Mhn penjelasannya y..

    sangat ditunggu blsnnya..
    Makacih ;)

    ReplyDelete
  6. Saya br bljar diophantine tuch...

    jadi masih agak mumet gitcuuu :)

    mhn dijelaskan lagi ya?! gmn untuk ngubah
    parameter ke k???

    trus knp pada contoh 2 variabel y yang dijumlahkan dengan -5 at +5????

    knp bkn -2 at +2???

    Mhn penjelasannya y..

    sangat ditunggu blsnnya..
    Makacih ;)

    ReplyDelete
  7. Gradien merepresentasikan selisih y/ selisih x..

    Dengan demikian, bagian pembilang itu miliknya y, kalo bagiannya penyebut itu milik x..

    Apakah sudah terjawab? ^^

    ReplyDelete
  8. Assalamu'alaikum.... oia pak, sy punya

    permaslahan.. sy mencb mencari selesaian positif

    dari persamaan 4181x-6765y=1000000.., mhn bantuannya y, cz sy cr hasilnya masih ttp ada yang slh.. dimanakah letak kesalahannya???????
    makasih banyak

    ReplyDelete
  9. Ya elah. Aku yang imut-imut gini and masih muda en cakep gini dipanggil bapak... ~_~

    Huehue.. Ternyata koefisien x dan y nya itu sejalan sesuai penjumlahan fibonacci.. Agak ribet kalo dijabarkan.. Jadi, aku langsung buat identitas Bezoutnya yaa..


    Identitas Bezout:
    4181 * (-2584) -6765 * (-1597) = 1
    kalikan kedua ruas dengan sejuta..
    4181 * (-2584*1000000) - 6765 * (-1597*1000000) = 1000000.

    Artinya solusi awalnya:
    x = -2584000000
    y = -1597000000
    Gradiennya = m = 4181/ 6765.

    Jadi:
    x = -2584000000 + 6765 k
    y = -1597000000 + 4181 k.
    Ambil k= 381967 (dengan coba-coba), maka:
    x = 6755 + 6765 k
    y = 4027 + 4181 k
    Agar menjadi postif, maka k = 0,1,2,3,....
    Artinya, solusinya tak berhingga.
    Selesai.

    ReplyDelete
  10. ya maaf q khan g tw...:) jadi tak pangil bapk aj he he...]

    soal diatas emang perluasan dari barisan fibonacci kak

    identitas bezoutnya dah bisa, tp q binggung gunkan k berapa yang nanti hasilnya positif... semuanya dah tak coba hsilnya negatif.. please ya mhn bantuannya..

    ni terkait dg TA q he..he..
    Tinggal ini thok please ?!!! kakakq yang muda en imut2..

    semoga dibalas dengan kebaikan amin..

    gmn bntu aq y? k nya berapa biar positif, kmrn q gnkan k = 31896

    makasih seblemnya...

    sangat di tunggu jawabny..

    oia, blh mnt almat emailnya?

    blh donk hi hi...:)

    ReplyDelete
  11. eh iya bknkah identitas bezoutnya itu 4181*(-2584)-6765*1597??.. tlg di cek ulang ya?

    tar q jg cek ulang lagi...

    makacie:))))))))))))

    ReplyDelete
  12. iy kak, mf q yang salah dalam memasukkan nilainya

    makasih ya..

    tp q tetep mnta emailnya kl boleh..

    q hrap boleh, :)

    ReplyDelete
  13. btw x koq bisa lgsung jd x=6755+6765k?
    begtu pula dg y nya?
    gmn tuch?

    ReplyDelete
  14. kak ternyta q salah soal, jgn bingung lht pertanyaanq yow??

    sorry, amburadul

    soalny itu x1*4181+6765x2=1000000

    mksih, dtunggu jwbnya y dengn segera

    ReplyDelete
  15. email kuw hendry_dext@yahoo.com... Ada di bagian kanan "About Me" koq.. Hueheee...

    Ak tulis ulang lagisoalnya:
    4181 x + 6765 y = 1000000

    Kalo kamu udah bikin identitas Bezuotnya, maka semuanya jadi gampang bgt...

    Identitas Bezoutnya:
    4181 * (-2584) +6765 * (1597) = 1
    dikali sejuta jadi:
    4181 * (-2584000000)+6765 * (1597000000) = 1000000
    Artinya solusi awalnya:
    x = -2584000000
    y = 1597000000

    gradiennya = m = (-4181)/ (6765)
    Jadi, solusinya:
    x = -2584000000 + 6765 k
    y = 1597000000 -4181k

    So, karena penyelesaiannya positif maka:
    x>0
    -2584000000 + 6765 k > 0
    6765 k > 2584000000
    k > 381966,0015
    k>= 381967 .. (i)

    y> 0
    1597000000 -4181k > 0
    4181 k <1597000000
    k < 381966.0368
    k <= 381966 ... (ii)

    Dari (i) dan (ii), tidak ada nilai k yang memenuhi. Jadi, penyelesaiannya tidak ada. ^^

    ReplyDelete
  16. tukan hasilnya sama jg kyak aq ,,, trus gmn? padahal itu yang aq bthkan..

    kira2 apa yang mempengaruhi y? sehingga tidak ada penyelesaian positif? mhn bntuannya y

    makasih:)

    ReplyDelete
  17. Assalamu'alaikum..

    Kak, maff jgn bosan2 dengan pertanyaanq y???

    cz q bth bnatuan bgt...

    kira2 apa y yang mempengaruhi sehingga selesaiannya negatif??...

    kakak ada literatur?

    kl ada blh tidk q download???

    mksh banyak :)

    ReplyDelete
  18. Kalo literatur, aku belum coba cari di internet.. Au ambil literatur dari buku SuwahSembiring, dan itu pun cuma sekilas.. ungkin, minta bantuan om google deh..

    "kira2 apa y yang mempengaruhi sehingga selesaiannya negatif??..."... Boleh kutanya lagi ngak, maksud pertanyaannya itu apa..? @_@

    Contoh soal di atas dipengaruhi oleh parameter k-nya.. Jadi, penyelesaianya ada atau ngak itu gara-gara tergantung dari apakah ada nilai k yang memenuhi atau tidak..

    ReplyDelete
  19. Assalamualaikum..
    afwan mau tanya, bagaimana cara menyelesaikan persamaan diopantine linear dengan n peubah? kalau yang antum jelaskan diatas kan hanya yang dua peubah. mohon penjelasannya. syukron..

    ReplyDelete
  20. Misalnya:

    Soal:
    Tentukan semua pasangan bilangan bulat positif x, y, dan z yang memenuhi persamaan 3x+2y+z = 8.

    Jawab:
    (1,2,1),(1,1,3)

    Mungkin, untuk soal di atas, kita dapat dengan mudah menjawabnya dengan coba-coba. Karena cara coba-coba merupakan cara yang cukup ampuh dan jitu dan cepat.. ^^

    Ada juga cara lain, yaitu dengan memisalkan 2 buah variabel menjadi 1 variabel lain, misalnya: 2y+z = a, maka persamaan 3 variabel di atas menjadi:
    3x+a = 8.

    ReplyDelete
  21. permisi numpang tanya :
    kalo persamaannya 4 variabel bsa pke persamaan diophantn nga??

    gn :
    170a + 130b + 104c + 78d = 3600

    berapa nilai a???

    ini gmn iia??

    ReplyDelete
  22. @atas: Soalnya aneh ya.. Ha3.. Kalo ada 4 variabel, artinya solusinya ada banyak sekali.

    Jika a bernilai nol, artinya akan menghsilkan persamaan:
    130b + 104c + 78 d = 3600
    Ruas kiri dapat dibagi 13, namun ruas kanan tidak habis dibagi 13.
    Jadi, a tidak boleh nol.

    a juga tidak boleh kelipatan 13.

    Kemudian, perhatikan bahwa jika b=0, c=0, d=0, maka akan menghasilkan persamaan:
    170 a = 3600
    Nilai a tidak bulat.

    Maka, b atau c atau d tidak boleh nol.

    Perhatikan bahwa jika dibagi 13, hasilnya adalah
    170a + 0 (mod 13) = 3600
    170a + 0 mod 13 = 12 mod 13.
    Maka
    170a = 12 mod 13
    a = 12 mod 13

    Inilah nilai a.

    ReplyDelete
  23. numpang tanya kak.
    kalo dalam persamaan linear diophantine ini gada pembuktian selain melaluicontoh ya?

    ReplyDelete
  24. terimakasih penjelasannya ...

    ReplyDelete
  25. mencari referensi tentang persamaan Diophantine, dan menyasar sampai di sini. Terima kasih atas artikelnya. Salam.

    ReplyDelete
  26. salam kenal sy Erick ada soal persamaan dipantine sbb:859x-75y=4000 kalo dislsaikan dgn cara kongruensi bagaimana , apa hanya 1 penyelesaian. terima kasih sblm nya

    ReplyDelete
  27. This comment has been removed by the author.

    ReplyDelete
  28. Klo boleh tau bng kenapa untuk persamaan diophantine harus bilangan bulat bng/kk

    ReplyDelete
  29. kira-kira yang punya blog ini masih ada gak ya,udah13 tahun lebih di upload di buat blog ini

    ReplyDelete