PERSAMAAN DIOPHANTINE

Suatu persamaan berbentuk ax + by = c dengan a, b, c bilangan-bilangan bulat dan a, b dua-duanya bukan nol disebut persamaan linear Diophantine jika penyelesaiannya dicari untuk bilangan-bilangan bulat.

TEOREMA:

Persamaan linear Diophantine ax + by = c mempunyai penyelesaian jika dan hanya jika (a, b) c.

Bukti :

Misalkan (a, b) = d dan d   c.

d     c ⇔ ada k sehingga c = kd.

d     (a, b) ⇔ ada m dan n sehingga am + bn = d

⇔ a(km) = b (kn) = kd

⇔ a(km) + b(kn) = c

Diperoleh x = m k dan y = nk

TEOREMA :

Jika d = (a, b) dan x₀, y₀ penyelesaian persamaan Diophantine ax + by = c, maka penyelesaian umum persamaan tersebut adalah

x = x₀ + (b/d) k  dan y = y₀ – (a/d)k dengan k parameter bilangan bulat.

CONTOH

1.  Tentukan penyelesaian umum persamaan diphantine 738 x + 621 y = 45. Penyelesaian:

738 =1×621+117

621 =5×117+36

117 =3×36+9

36    = 4×9+0

Jadi (738, 621) = 9. Karena 9 45 maka persamaan di atas mempunyai penyelesaian.

9 = 117 – 3.36

=    117 – 3( 621 - 5 × 117)

=    -3×621+16(738–621)

=  16×738–19×621 Kalikan kedua ruas dengan 5 45=80×738–95×621 Didapat x₀ = 80 dan y₀ = -95

Penyelesaian umumnya adalah

x= 80 + (621/9) k = 80 + 69 k

y = -95 – (738/9)k = -95-82 k

2.  Tentukan bilangan bulat positif x dan y yang memenuhi 7x + 5y = 100 Penyelesaian :

(7, 5 ) =1. Karena 1  100 maka persamaan di atas mempunyai penyelesaian.

1  = 3.7 – 4.5

100  = 7 × 300 + 5 × (-400). Didapat x₀ = 300 dan y₀ = -400 Penyelesaian umumnya adalah :

x = 300 + 5 k

y = -400 – 7 k

Karena yang dicari adalah solusi positif maka haruslah

300 + 5k > 0 dan -400 – 7 k > 0, yaitu -60 < k < -57 .

Sehingga didapat k = -58 dan k = -59.

Jadi persamaan Diophantine 7x + 5y = 100 mempunyai tepat dua solusi positif yaitu x₁ = 10, y₁ = 6 dan x₂ = 5 , y₂ = 13