Persamaan Linier Diofantos

1. Siapa itu Diofantos?

Diofantos dari Alexandria (Διόφαντος ὁ Ἀλεξανδρεύς); diyakini lahir antara 201 dan 215 M; wafat pada usia 84 tahun, diyakini antara 285 dan 299 M; adalah seorang matematikawan Helenistik Aleksandria. Ia adalah seorang penulis seri buku berjudul Arithmetica, beberapa diantaranya sekarang hilang. Buku tersebut berisi soal pemecahan persamaan aljabar.

2. Bentuk Umum Persamaan Linier Diofantos

Pada umumnya persamaan linier Diofantos berbentuk ax + by = c, dengan a, b, c merupakan bilangan bulat, dan x, y merupakan variabel yang bernilai bulat.

3. Persamaan Linier Diofantos dan Perkongruenan Linier

Persamaan ax + by = c berarti sama dengan perkongruenan linier:

ax ≡ c (mod b) atau by ≡ c (mod a).

Oleh karena itu, untuk menyelesaikan suatu persamaan linier Diofantos dengan cara menyelesaikan salah satu dari kedua perkongruenan linier tersebut. Setelah itu solusi dari perkongruenan itu disubstitusikan ke persamaan semula untuk menyelesaikan persamaan linier tersebut.

Contoh:

Selesaikan persamaan 7x + 15y = 31

7x + 15y = 31 berarti 7x ≡ 31 (mod 15)

7x ≡ 91 (mod 15), karena (7, 15) = 1 maka dapat disederhanakan:

x ≡ 13(mod 15)

berarti x = 13 + 15t untuk suatu bilangan bulat t.

Nilai x disubstitusikan ke persamaan 7x + 15y = 31 diperoleh:

7(13 + 15t) + 15y = 31

91 + 105t + 15y = 31

15y = 31 – 91 – 105t 

15y = –60 – 105t

y = –4 – 7t

Sehingga himpunan penyelesaian dari 7x + 15y = 31 adalah:

{(x, y) | x = 13 + 15t, y = –4 – 7t, dengan t bilangan bulat}

4. Solvabilitas

Suatu persamaan linier Diofantos ax + by = c diselesaikan dengan cara menyelesaikan salah satu dari perkongruenan ax ≡ c (mod b) atau by ≡ c (mod a). Oleh karena itu, suatu persamaan linier ax + by = c terkadang memiliki solusi dan terkadang tidak memiliki solusi. Berikut solvabilitas dari suatu persamaan linier Diophantus:

• Persamaan Linier Diophantus ax + by = c; a, b ≠ 0 memiliki solusi bila (a, b) | c.

• Persamaan Linier Diophantus ax + by = c; a, b ≠ 0 tidak memiliki solusi bila (a, b) ∤ c.

5. Penyederhanaan

Persamaan Linier Diofantos ax + by = c jika (a, b) = d dan d | c maka dapat disederhanakan menjadi (a/d)x + (b/d)y = c/d.

Bukti sebagai berikut:

(a, b) = d maka d | a dan d | b, dan dikarenakan juga d | c maka a/d, b/d, c/d merupakan bilangan bulat, sehingga ax + by = c dapat disederhanakan menjadi (a/d)x + (b/d)y = c/d. ∎

Bila persamaan terakhir ini memiliki penyelesaian x = r dan y = s maka himpunan semua penyelesaian dari ax + by = c adalah:

{(x, y) | x = r + k.b/d, y = s – k.a/d, dengan k bilangan bulat}

Contoh:

Selesaikan persamaan linier Diofantos 6x + 9y = 15.

(6, 9) = 3 | 15, Oleh karena itu 6x + 9y = 15 dapat disederhanakan menjadi:

(6/3)x + (9/3)y = 15/3 ⇔ 2x + 3y = 5

2x ≡ 5 (mod 3) 

2x ≡ 2 (mod 3), karena (2, 3) = 1 maka dapat disederhanakan menjadi:

x ≡ 1 (mod 3) 

Berarti x = 1 + 3t untuk suatu bilangan bulat t.

Nilai x disubstitusikan ke persamaan 2x + 3y = 5 diperoleh:

2(1 + 3t) + 3y = 5

2 + 6t + 3y = 5

3y = 5 – 2 – 6t

3y = 3 – 6t

y = 1 – 2t

Sehingga himpunan penyelesaian dari 2x + 3y = 5 adalah:

{(x, y) | x = 1 + 3t, y = 1 – 2t, dengan t bilangan bulat}