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 Diophantine: 

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 Diophantine: 

Jika d = (a, b) dan x0, y0 penyelesaian persamaan Diophantine ax + by = c, maka penyelesaian umum persamaan tersebut adalah
x=x_0 + (b/d)k dan y = y_0 - (a/d)k
 – (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 x0 = 80 dan y0 = -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 x0 = 300 dan y0 = -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\frac{1}{7}

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

Jadi persamaan Diophantine 7x + 5y = 100 mempunyai tepat dua solusi positif yaitu  x1 = 10, y1 = 6 dan  x2 = 5 , y2 = 13 .