BAB IX
PERSAMAAN DIOPHANTIN
Kita
telah mengenal Fungsi linier ax + by = c
dengan x dan y menyatakan bilangan-bilangan riil. Dengan kata lain, fungsi
linier itu diselesaikan dalam domain (himpunan semesta) himpunan bilangan riil.
Apabila domainnya dipersempit, yaitu himpunan bilangan bulat, maka persamaan ax + by = c dengan a, b
dan c bilangan-bilangan bulat disebut
Persamaan Linier Diophantin.
Persamaan
ax + by = c berarti ax ≡ c (mod b)
Dapat
pula bahwa ax + by = c berarti by ≡ c (mod a)
Oleh karena itu, untuk menyelesaikan
persamaan ax + by = c dengan a, b, c, x dan y bilangan-bilangan bulat, kita dapat menyelesaikan salah satu perkongruenan
ax ≡ c
(mod b) atau by ≡ c (mod a)
Selanjutnya solusi dari salah satu dari
pengkongruenan itu disubsitusikan pada persaman semula untuk memperoleh
penyelesaian dari persamaan linier tersebut.
Contoh 1:
Misalkan kita harus menyelesaikan 9x + 16y = 35
9x + 16y = 35 berarti 16y ≡ 35 (mod 9)
7y ≡ 35
( mod 9)
y ≡ 5 ( mod
9)
Berarti y
= 5 + 9t untuk suatu bilangan bulat t.
Nilai y
ini disubsitusikan pada 9x + 16y = 35
memberikan
9x + 16(5 + 9t) = 35
9x + 144t = - 45
x + 16t = - 5
x = - 5 – 16t
sehingga himpunan penyelesaian dari 9x + 16y = 35 adalah
{(x,y) ∣ x = -5-16t, y =5 + 9t dan t bilangan bulat}
Jika t = 0, maka x = -5, y = 5, sehingga (-5,
5) adalah salah satu penyelesaian dari persamaan 9x + 16y = 35.
Penyelesaian itu secara
umum dapat dikatakan bahwa apabila (
) adalah suatu solusi dari persamaan linier Diopantus ax + by = c, maka solusi lainnya (
) untuk setiap bilangan bulat. Perlu diingat bahwa ax
+ by = c sama artinya dengan ax ≡ c (mod b) atau by ≡ c (mod a). Kedua
perkongruenan ini akan mempunyai solusi, apabila (a,b)∣c, dan pengkongruenan itu tidak mempunyai solusi, apabila (a,b) ł c.
Jadi dapat disimpulkan
bahwa :
(1)
Persamaan Linier Diophantus ax + by = c dengan ab # 0 tidak mempunyai penyelesaian, bila (a,b) ł c
(2)
Persamaan Linier Diophantus ax + by = c dengan ab # 0 mempunyai penyelesaian (solusi), bila (a,b) ∣ c
Contoh 2 :
Persamaan
Linier Diophantus 2x + 4y = 5 tidak
mempunyai solusi, karena (4,2) ł 5. Mudah pula diperiksa bahwa jika y = t, maka
x =
Untuk
setiap bilanga bulat t maka (5 – 4t) adalah suatu bilangan ganjil, sehingga
x
=
tidak akan menyatakan bilangan bulat untuk
setiap bilangan bulat t.
Contoh 3 :
Apabila
x dan y menyatakan bilangan-bilangan bulat positif, selesaikanlah 7x
+ 15y = 51
Jawab :
7x + 15y = 51 berarti 15
y ≡ 51 (mod 7)
5y ≡ 17 ( mod 7)
5y ≡ 10 (mod 7)
y ≡ 2 (mod 7)
Jadi y = 2 + 7t
dengan t bilangan cacah
Subsitusikan nilai y pada persamaan semula, sehingga
diperoleh
7x + 15(2 + 7t) = 51
7x + 105t = 21
x
= 3 – 15t
Karena x bilangan bulat positif dan t bilangan cacah, maka x = 3, yaitu untuk t = 0, sehingga y = 2,
jadi bilangan-bilangan bulat positif x
dan y yang memenuhi 7x = 15y = 51 berturut-turut adalah 3 dan 2.
Contoh 4 :
Selesaikan persamaan linier
Diophantus 2x + 6y = 20
Jawab :
2x
+ 6y = 20 berarti 2x ≡ 20 (mod 6)
x ≡ 10 (mod 3)
x ≡ 1 (mod 3)
Berarti x = 1 + 3t dengan t
bilangan bulat
Substitusi 1 + 3t
pada x dalam 2x + 6y = 20
2 (1+ 3t) + 6y = 20
6y = 18 – 6t
y = 6 – t
Himpunan penyelesaian dari 2x + 6y = 20 adalah
{(x,y)|x = 1 + 3t, y
= 6 – t, t bilangan bulat}.
Hal lain yang berhubungan dengan perkongruenan
linier, salah satu diantaranya adalah sistem pengkongruenan linier. Masalah
yang penyelesaiannya menggunakan sistem pengkongruenan ini telah muncul dalam
suatu tulisan bangsa Cina kuno sebagai berikut :
Tentukan suatu bilangan bulat yang bersisa 2
jika dibagi 3, bersisa 4 jika dibagi 5 dan bersisa 6 jika dibagi 7.
Jika
bilangan yang dicari dimisalkan x,
maka kalimat dalam masalah itu dapat dinyatakan sebagai berikut :
x
≡ 2 (mod 3)
x
≡ 4 (mod 5)
x
≡ 6 (mod 7)
Apakah
bilangan bulat yang dicari itu adalah 104?
Adakah bilangan lain yang masih memenuhi ?
Untuk
menjawab pernyataan ini, ikutilah uraian berikut ini :
Dari
pengkongruenan pertama x ≡ 2 (mod 3)
berarti x = 2 + 3
,
untuk suatu bilangan buat
.
Substitusikan
nilai x itu dalam perkongruenan kedua
dan diperoleh:
2 + 3
≡ 4
(mod 5)
3
≡ 2 (mod 5)
Ini
berarti
= 4 +
5
untuk suatu bilangan bulat
.
Substitusikan
nilai
ini dalam persamaan x = 2 + 3
sehingga diperoleh :
x = 2 + 3 ( 4 + 5
)
x
= 14 + 15
Subsitusikan
nilai x ini dalam pengkongruenan
ketiga dan diperoleh :
14 + 15
≡ 6
(mod 7)
15
≡ -8
(mod 7)
Hal ini
berarti
= 6 +
7t untuk suatu
bilangan bulat t.
Subsitusikan
nilai
dalam persamaan x = 14 + 15
dan diperoleh :
x = 14 + 15 (6 + 7t)
x = 104 + 105t untuk suatu bilangan bulat t.
Persamaan
terakhir ini dapat dinyatakan sebagai x ≡
104 (mod 105) yang memenuhi ketiga pengkongruenan diatas. Solusi
pengkongruenan x ≡ 104 (mod 105) adalah 104, yang juga merupakan solusi bersama
dari ketiga pengkongruenan (sistem perkongruenan) diatas.
Contoh 5 :
Carilah penyelesaian umum dari persamaan 80x + 60y = 5000
Penyelesaian :
Karena (80,60)
= 20 kita dapat menyederhanakan menjadi bentuk 4x + 3y = 250. Selanjutnya kita nyatakan Variabel y dalam x sehingga menjadi :
3y = 250 – 4x
y =
Misalkan t
=
t =
⇔ 3t = 1 – x
⇔ x = 1 – 3t
dan
y =
= 83
– x +
= 83 – ( 1 – 3t) + t
= 82 + 4t
Jadi penyelesaian umum dari persamaan di atas
adalah :
x = 1 – 3t
y = 82 + 4t
untuk suatu t bilangan bulat.
Contoh 6 :
Tentukan penyelesaian khusus, yaitu nilai x dan y positif yang memenuhi persamaan 80 x + 60y = 5000
Penyelesaian :
Dari contoh
5 diatas telah diperoleh :
x = 1 – 3t
y = 82 + 4t
untuk suatu bilangan bulat.
karena x
> 0 dan y > 0, maka :
1 – 3t > 0 ⇔ t <
dan 82 + 4t > 0 ⇔ t > -20
Karena t
bilangan bulat dan -20
< t
<
, maka t = -20, -19, ..., -1, 0
sehingga :
|
t
|
-20
|
-19
|
-18
|
-17
|
-16
|
-15
|
-14
|
-13
|
-12
|
-11
|
-10
|
...
|
-1
|
0
|
|
x
|
61
|
58
|
55
|
52
|
49
|
46
|
43
|
40
|
37
|
34
|
31
|
...
|
4
|
1
|
|
y
|
2
|
6
|
10
|
14
|
18
|
22
|
26
|
30
|
34
|
38
|
42
|
...
|
78
|
82
|
Dengan demikian permasalahan tentang perangko
diatas dapat dijawab sebagai berikut :
61 perangko 80-an dan 2 perangko 60-an atau
58 perangko 80-an dan 6 perangko 60-an atau
.....................................................................
7 perangko 80-an dan 74 perangko 60-an atau
4 perangko 80-an dan 78 perangko 60-an atau
1 perangko 80-an dan 82 perangko 60-an
Sebanyak
21 pasangan kombinasi yang mungkin.
Contoh 7 :
Tentukan
penyelesaian umum dan penyelesaian khusus dari persamaan 5x – 8y = 39 !
Penyelesaian
:
5x – 8y = 39
⇔ 5x = 8y + 39
⇔ x =
⇔ x = y + 7 +
....................(1)
Misalkan
: t =
t =
⇔ 5t = 3y + 4
⇔ 3y = 5t – 4
⇔ y =
⇔ y =
t – 1 +
........................ (2)
Misalkan : u =
u
=
⇔ 3u = 2t – 1
⇔ 2t = 3u + 1
⇔ t =
⇔ t = u +
............................... (3)
Misalkan : v =
v
=
⇔ 2v = u + 1
⇔ u = 2v – 1 ............................ (4)
Selanjutnya
substitusikan (4) ke (3) :
u
= 2v – 1 substitusi ke t = u +
t =
u
+
⇔ t = (2v – 1) + v
⇔ t = 3v – 1
............................... (5)
Selanjutnya substitusikan (5) ke (2) :
t
= 3v – 1 substitusikan ke y = t – 1 +
y =
t – 1 +
⇔ y = 3v – 1 – 1 +
⇔ y = 3v – 2 +
⇔ y = 3v – 2 +
⇔ y = 3v – 2 + 2v – 1
⇔ y = 5v – 3
Maka :
x = y + 7 +
⇔ x = (5v – 3) + 7 +
⇔ x = 5v – 3 + 7 +
⇔ x = 5v + 4 + 3v – 1
⇔ x = 8v + 3
Jadi :
a. Penyelesaian umum persamaan 5x – 8y = 39 adalah : y = 5v – 3 dan x = 8v + 3 dengan v
bilangan bulat.
b. Penyelesaian khusus untuk x dan y positif adalah :
5v
– 3 > 0 ⇔ v >
8v
+ 3 > 0 ⇔ v
>
Agar x dan y positif maka v = 1, 2, 3,
...
|
v
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
...
|
|
x
|
11
|
19
|
27
|
35
|
43
|
51
|
59
|
67
|
...
|
|
y
|
2
|
7
|
12
|
17
|
22
|
27
|
32
|
37
|
...
|
LATIHAN SOAL
1.
Jika 9x
≡ k (mod 12) dengan k suatu unsur dari himpunan residu terkecil modulo 12. Tentukan nilai k agar
perkongruenan itu :
a.
Tidak memiliki solusi
b.
Memiliki Solusi
2. Tentukan
solusi dari 4x ≡ 6 (mod 18)
3.
Tentukan banyaknya solusi dari tiap-tiap
perkongruenan linier berikut ini dan selesaikan !
a.
3x ≡ 6 (mod 15)
b.
6x ≡ 11 (mod 15)
c.
3x ≡ 6 (mod 18)
d.
3x ≡ 1 (mod 17)
4.
Jika x
dan y menyatakan bilangan-bilangan
bulat, tentukan solusi dari :
a.
2x + 6y = 18
b.
6x + 15y = 51
5.
Carilah penyelesaian dari persamaan :
a.
15x + 14y = 570
b.
123x + 57y = 531
c.
12x + 501y = 274
d.
84x – 438y = 156
Tidak ada komentar:
Posting Komentar