PERSAMAAN DHIOPANTINE

 

BAB II

PEMBAHASAN

A.    BENTUK UMUM

Persamaan Diophantine adalah persamaan linier yang memuat beberapa variabel, namun harus diselesaikan dalam bilangan bulat. Bentuk paling sederhananya adalah :

ax + by = c

Persamaan Diophantine dapat mempunyai atau tidak mempunyai penyelesaian. Contohnya  . Persamaan ini tidak mempunyai jawab di himpunan bilangan bulat, persamaan ini akan mempunyai jawab di himpunan bilangan real.

Dalam kasus ia mempunyai penyelesaian maka penyelesaiannya banyak. Teorema berikut memberikan syarat perlu dan cukup persamaan Diophantine mempunyai penyelesaian.

Teorema 1

Misalkan a; b dan c bilangan bulat dimana a dan b tidak keduanya nol dan d = gcd(a; b). Maka persamaan Diophantine ax + by = c mempunyai penyelesaian jika hanya jika d|c; dalam kasus ini terdapat takberhingga banyak penyelesaian. Penyelesaian-penyelesaian ini diberikan oleh :

x = x₀ + b/d(n),           y = y₀ - a/d(n), n€Z

dimana (x₀; y₀) merupakan penyelesaian khusus.

Berikut diberikan algoritma untuk menentukan penyelesaian persamaan Diophantine

1.   Hitung d = gcd(a; b); dengan cara langsung atau menggunakan algoritma Euclides.

a = q₁b + r₁; 0 < r₁ < b

b = q₂r₁ + r₂; 0 < r₂ < r₁

r₁ = q₃r₂ + r₃; 0 < r₃ < r₂

2.   Bila d tidak sedemikian hingga c maka persamaan Diophantine tidak mempunyai penyelesaian, stop. Bila d sedemikian hingga c, tulis c = kd.

3.   Temukan bilangan bulat v dan w dengan identitas bezouth sehingga av + bw = d. Kedua ruas dikalikan k diperoleh

akv + bkw = kd

a(kv) + b(kw) = c:

Diambil x0 = kv dan y0 = kw sebagai penyelesaian khususnya.

4.     Gunakan formula (1.6) untuk membangun himpunan semua penyelesaian.

1. Jika a|c dan b|c maka ab|c.

2. Jika a|bc maka a|c.

B.    BENTUK SOAL

Diberikan persamaan Diophantie : 172x + 20y = 1000:

1. Selidikilah apakah persamaan ini mempunyai penyelesaian.

2. Bila ia mempunyai, tentukan semua penyelesaian tersebut.

3. Tentukan penyelesaian yang bernilai positif.

Penyelesaian.

Pertama selidiki dulu gcd(172; 20), yaitu dengan algoritma Euclides berikut :

172 = 8 × 20 + 12

20 = 1 × 12 + 8

12 = 1 × 8 + 4

8       = 2 × 4 + 0

Sehingga diperoleh gcd(172; 20) = 4. Karena 4|1000 maka persamaan Diophantine ini dipastkan mempunyai penyelesaian. Tulis 1000 = 250×4. Untuk menentukan penyelesaian ini digunakan algoritma yang telah diberikan sebelumnya. Dengan cara berjalan mundur pada algoritma Euclides di atas untuk membentuk identitas Bezout berikut.

4 = 12 - 8

   = 12 - (20 × 1 - 12)

   = 2 × 12 - 20

   = 2(172 – 8 × 20) - 20

   = 2 × 172 + (-17) × 20:

Jadi dengan mengalikan kedua ruas dengan 250 diperoleh

500 × 172 + (-4250) × 20 = 1000:

Dari sini diambil x₀ = 500 dan y₀= -4250 sebagai penyelesaian khususnya. Selanjutnya bentuk umum penyelesaian persamaan ini diperoleh

x = 500 + 20/4t = 500 + 5t          y = -4250 – 172/4t = - 4250 - 43t

dimana t bilangan bulat sebarang. Terakhir untuk memilih diantara penyelesaian ini yang bernilai positif, kita perlu memberikan syarat berikut :

500 + 5t > 0

-4250 - 43t > 0

Berdasarkan syarat ini diperoleh t > - 500/5 = -100 untuk syarat pertama  

dan t < ⁴²⁵⁰/_-43 = - 98 ³⁶/₄₃ untuk syarat kedua. Jadi t yang memenuhi kedua syarat ini adalah t = -99 dan penyelesaian positif yang dimaksud adalah

x = 500 + 5(-99) = 5

y = -4250 - 43(-99) = 7: