Persamaan Diophantine

Salah satu subbab menarik dalam Teori Bilangan adalah persamaan Diophantine {Diophantine Equation}.

Diophantine menyatakan bahwa :
Suatu persamaan linear Diophantine ac+by=c dengan a,b dan c bilangan bulat mempunyai penyelesaian bilangan bulat jika dan hanya jika GCD(a,b) membagi habis c.

Kali ini, tidak akan dibahas mengenai bukti Teorema Persamaan Diophantine diatas akan tetapi lebih mengacu ke penyelesaian soal.

Contoh Soal :

Carilah semua solusi bilangan bulat yang memenuhi

3456x + 246y =234.

Jawab :

Menurut persamaan diophantine, persamaan diatas mempunyai penyelesaian bulat jika GCD(3456,246) membagi habis 234.

*
Jadi, langkah pertama yang perlu dilakukan adalah mencari GCD(3456,246). Untuk bilangan-bilangan yang kecil, faktorisasi prima bisa jadi pilihan yang tepat. Akan tetapi, untuk bilangan-bilangan besar, sepertinya perlu dihindari mencari GCD menggunakan faktorisasi prima. Metode yang digunakan disini yaitu dengan menggunakan Algoritma Euclid.

3456 = 14.246 + 12
246 = 20.12 + 6
12 = 2.6 + 0
Dari sini diperoleh GCD(3456,246) = 6.

*
Selanjutnya, cek apakah GCD(3456,246) membagi habis 234.
Jelas, karena 234 : 6 = 39.
Jadi, persamaan diatas mempunyai penyelesaian bilangan bulat.

*
Langkah berikutnya yaitu, merubah persamaan-persamaan pada Algoritma Euclid. Diperoleh,
12 = 3456 - 14.246
6 = 246 - 20.12.

Dari kedua persamaan ini diperoleh
6 = 246 - 20.(3456-14.246)
= -20.3456 + 281.246.
Pada persamaan terakhir ini, terlihat penyelesaiannya yaitu dengan mengalikan dengan hasil bagi 234 terhadap 6, yaitu 39.

*
Kalikan persamaan terakhir dengan 39 diperoleh 234 = -780.3456 + 10959.246. Jelas, bahwa ruas kanan sama dengan ruas kiri.
Jadi salah satu penyelesaian untuk persamaan diatas adalah latex (x,y) =(-780,10959).