Minggu, 29 Maret 2015
Sabtu, 21 Maret 2015
persamaan diophantine
1.1
Latar Belakang
Persamaan Diophantine terdiri dari
persamaan Diophantine linear dan persamaan Diophantine non-linear. Persamaan
ini pertama kali ditulis oleh “Diophantus” (250 M ) di dalam bukunya yang
berjudul “Arithmetica” dan buku ini dikenal sebagai buku aljabar yang pertama
kali.
Riwayat dari Diophantus:
Sekitar athun 250 seorang
matematikawan Yunani yang bermukim di Alexandria melontarkan problem matematika
yang tertera di atas batu risanya. Tidak ada catatn terperinci tentang
kehidupan Diophantus, namun meninggalkan problem tersohor itu pada Palatine
Anthology, yang ditulis setelah meninggalnya. Pada batu nisan Diophantus
tersamar (dalam persamaan) umur Diophantus.
Karya Diophantus:
Diophantus menulis Aritmetica yang
mana isinya merupakan pengembangan aljabar yang dilakuakn dengan membuat
beberapa persamaan. Persamaan – persamaan tersebut disebut persamaan
“Diophantine”, digunakan pada matematika sampai sekarang. Diophantus menulis 15
namun hanya 6 buku yang dapat dibaca, sisanya ikut terbakar pada penghancuran
perpustakaan besar Alexandria. Sisa karya Diophantus yang selamat sekaligus
merupakan teks bangsa Yunani yang terakhir dan diterjemahkan. Buku terjemahan
pertama kali dalam bahasa latin diterbitkan pada tahun 1575. Prestasi
Diophantus mer4upakan akhir kejayaan Yunani kuno. Susunan – susunan dalam
Aritmatika tidak secara sistematik operasi – operasi aljabar, fungsi – fungsi
aljabar atau solusi terhadap persamaan – persamaan aljabar. Di dalamnya
terdapat 150 problem, semua diberikan lewat contoh – contoh numeric yang
spesifik meskipun barangkali metode secara umum juga diberiakn. Sebagai contoh
persamaan kuadrat mempunyai hasil dua akar bilangan positif dan tidak mengenal
akar bilangan negative. Diophantus menyelesaiakan problem – problem menyangkut
beberapa bilangan taidak diketahui dan dengan penuh keahlian menyajikan banyak
banyak bilangan – bilangan yang tidak diketahui.
Contoh:
Diketahui bilangan dengan jumlah 20
dan jumlah kuadratnya 208, angka bukan diubah menjadi x dan y, tapi ditulis
sebagai 10 + x dan 10 – x (dalam notasi modern). Selanjutnya (10 + x )2
+ (10 – x)2 = 208, diperoleh x = 2 dan bilangan yang tidak diketahui
adalah 8 dan 12.
Diophantus dan Aljabar:
Dalam Aritmetica meski bukan
merupakan teks aljabar akan tetapi didalamnya terdapat problem persamaan x2
= 1 + 30y2 dan x2= 1 + 26y2 yang kemudian
diubah menjadi persamaan pell x2 = 1 + py2, sekali lagi
didapat jawaban tunggal, karena Diophantus adalah pemecah problem bukan
menciptakan persamaan dan buku berisikan kumpulan problem dan aplikasi pada
aljabar. Problem Diophantus untuk menemukan bilangan x, a dan y, a dalam
persamaan x2 + y2 = a2 atau x3+ y3
= a3, kelak mendasari fermat mencetuskan TTF (Theorema Terakhir Fermat).
Prestasi ini membuat Diophantus seringkali disebut dengan ahli aljabar dan
babylonia dan karyanya disebut dengan aljabar Babylinia.
Misal umur x, sehingga x =
akan
diperoleh x = 84, umur Diophantus.
Di dalam persamaan Diophantine linear paling
sederhana adalah memuat dua variable,dimana pada umumnya dinyatakan dengan ax +
by = c dengan a, b, c Є Z, sedangkan di dalam persamaan Diophantine non-linear
membahas tentang triple Pythagoras dan jumlah kuadrat.
BAB II
PEMBAHASAN
2.1
Persamaan Diophantine Linear
2.1.1 Memuat Dua Variabel
Persamaan Diophantine linear paling sederhana adalah memuat dua
variable. Pada umumnya dinyatakan dengan ax + by = c, dengan a, b, c, Є Z.
Teorema
1.
Tentukan (a,b) c, maka
ax + by = c tidak mempunyai penyelesaian.
Bukti:
Misalkan x dan y adalah bilangan –
bilangan bulat yang memenuhi ax + by = c
d = (a,b) → (d | a dan d | b)
d = | a → d | ax
d | b → d | by
(d | ax dan d | by) → d | (ax + by) → d | c
jadi,jika d | c, maka bertentangan dengan d = 9a,b) dan d | c,
yaitu ax + by = c tidak mempunyai
pemyelesaian.
Contoh :
1.
4x + 6y
= 7
Jawab:
(4,6) = 2 7 persamaan tidak mempunyai
penyelesaian
Teorema
2.
Ditentukan (a,b) | c, maka persamaan ax + by =
c mempunyai penyelesaian bulat yang tak hingga banyaknya, yaitu pasangan (x,y)
dengan: x = x0 + (
dan y
= y0 – (
dengan
n Є Z dan (x0,y0) adalah suatu penyelesaian bulat.
Bukti:
Misalkan x,y Є Z memenuhi ax + by =
c dan d | c
Karena d = ( a,b), maka tentu ada (x1,
y1 Є Z ) sehingga d = ax1 + by1
d | c → c = kd ( k Є Z) → c = k ( ax1 + by1 )
→ c = a (kx1) + b (ky1) → (c = ax1 + by1
atau ax1 + by1 = c)
Ternyata dengan mengambil x0 = kx1 dan y0
= ky1, maka (x0,y0) memenuhi persamaan,
sehingga (x0,y0) merupakan satu penyelesaian.
Untuk menunjukkan terdapat tak hingga banyaknya penyelesaian,
ambil: x = x0 + (
dan y = y0 - (
dengan
n Є Z
Jika nilai – nilai x dan y disubstitusikan ke dalam persamaan, maka
diperoleh:
ax + by = a {x0 + (
} + b {y0 – (
}
= ax0
+ a (
+ by0 – b (
= ax0
+ by0 + (a (
– (a (
/n)
ax + by = c
Karena n Є Z, maka terdapat tak hingga banyaknya (x,y) dengan:
x = x0 + (
dan y = y0 – (
dan memenuhi persamaan ax + by = c.
Sekarang akan
ditunjukkan bahwa setiap penyelesaian dari ax + by = c dalam bentuk:
x = x0 + (
dan y = y0 – (
Misalkan x,y Є Z dan ax + by = c
Karena ax + by + c dan ax0 + by0 = c, maka:
a(x – x0) + b(y – y0) = 0
a(x – x0) = b(y0 – y)
(
(x – x0)
= (
(y0 –y) → (
| (
(y0
– y)
{(
| (
(y0
– y) dan (
,
) = 1} → (
| (y0
– y)
(
| (y0
–y) → y0 – y = n(a/d) → y = y0 – (
{y = y0 – (
dan
a(x – x0) = b(y0 – y) }
→
a(x – x0) = b(
→
x – x0 = (
→
x = x0 + (
Contoh:
2.
4x + 5y
= 10
jawab:
(4,5) = 1 | 10 persamaan mempunyai penyelesaian.
Sesuai dengan dalil Algoritma Euclides, karena (4,5) = 1, maka
tentu ada x1,y1 Є Z sehingga 4x1 + 5y1
= 1.
Karena 5 = 1.4 + 1 atau (4)(-1) + (5)(1) = 1, maka x1 =
-1 dan y1 =1
(4)(-1) + (5)(1) = 1
10{(4)(-1) + (5)(1)} = 10.1
4(-10) + 5(10) = 10 (Ingat:
4x + 5y = 10)
jadi, x0
= -10 dan y0 = 10
Penyelesaian persamaan adalah:
x = -10 + 5k dan y = 10 – 4k dengan k Є Z
3.
91x +
221y = 1066
Jawab:
221 = 2 . 91 + 39 → 39 = 221 – 2 . 91
91 = 2 . 39 + 13 → 13 = 91 – 2 . 39
39 = 3 . 13
(91 . 221) = 13
Karena 1066 = 82 . 13, maka 13 | 1066
13 | 1066 persamaan mempunyai penyelesaian.
Sesuai dengan Dalil: 1 Algoritma Euclides,
karena (91,221) = 13, maka tentu ada x1 . y1 Є Z sehingga
91x1 + 22y1 = 13
13 = 91 . 2(39) = 91 . 2(221 – 2 . 91) = 5 . 91
+ 22(-2)
13= 5.91 + 221(-2) . 91.5 + 221(-2) = 13
82(91.5 + 221 (-2))
= 82.13
91(410 + 221(-64) = 1066
Jadi x0 = 410 dan y0 = -164
Penyelesaian persamaan adalah
x = 410 + 17s dan y = -164 – 7s.s Є Z
2.1.2
Cara Reduksi
Cara
reduksi dalam menyelesaikan persamaan Diophantine linear adalah mereduksi
koefisien (bukan meruduksi variable) melalui pembagian berulang (serupa dengan
pembagian Algoritma), sehingga diperoleh bentuk tanpa pecahan.
Selanjutnya
dengan bekerja mundur, nilai – nilai penyelesaian akan diperoleh dan variable
lain yang digunakan dan tidak tercantum dalam persamaan semula, antara lain: r,
s, t dan u, meskipun tanpa keterangan semuanya diambil bulat.
Contoh:
1.
4x + 5y
= 10
Jawab:
4x + 5y = 10
4x = 10 – 5y
x =
=
=
= (2 – y) +
Ambil t , sehingga:
t ==
atau 2 – y = 4t
atau y = 2 – 4t,
sehingga dari y = 2 –
4t diperoleh:
x = (2 – y) +
= 2 – (2
– 4t) +
= 4t + t
= 5t
x = 0 +
5t
Penyelesaian
persamaan adalah: x = 0 + 5t dan y = 2 –
4t.
2.
3x + 8y
= 11
Jawab:
3x + 8y = 11 3x = 11
8y
Ambil
atau
atau
atau
dari
Ambil u, sehingga:
=
t = -2u y
= ( 1 + 2u) +
= 1 + 2u + u
= 1 + 3u
x = 3 – 2y +
= 3 – 2( 1+ 3u ) +
= 3 – 2 –
6u – 2U
=1 – 8u
Jadi, Penyelesaian
persamaan adalah :
x = 1 – 8u
dan y = 1 + 3u
3.
8x – 5y
+ 7z = 21
Jawab:
8x – 5y + 7z = 21
-5y = -8x – 7z + 21
y =
y = (x +
z – 4) +
Ambil t,sehingga
t =
→ -5t = -3x – 2z + 1 → -2z = 3x – 5t – 1 → z =
z = (-x
+ 2t) +
Ambil u,sehingga:
u =
→ -2u = x – t –
1 →x = -2u +t + 1
z = (-x + 2t) + u = - (-2u + t + 1) + 2t + u +
3u + t – 1
y = (x +
z – 4) + t = 9-2u + t + 1) + (3u + t – 1) – 4 + t = u + 3t – 4
Penyelesaian persamaan adalah:
x = -2u
+ t + 1
y = u +
3t – 4
z = 3u +
t -1
2.1.3 Cara Kongruensi
Penyelesain
persamaan linear dengan menggunakan cara kongruensi melebatkan penyelesaian
kongruensi linear dan system kongruensi linear. Meskipun hasil yang diperoleh
mungkin mempunyai bentuk yang berbeda dengan hsil yang diperoleh dengan
menggunakan cara yang lain, sebenarnya hasil itu adalah sama.
Contoh:
1.
35x + 14y = 91
Jawab:
35x + 14y + 91 → 14y = 91 – 35x → 14y ≡ 91 (mod
35) → 14y ≡ 21 ( mod 35)
Karena ( 14,21) = 7 | 35,
maka kongruensi mempunyai penyelesaian:
14y ≡ 21 ( mod 35) → 2y ≡ 3 (mod 5) → y ≡ 4
(mod 5) → y = 4 + 5t
35x + 14y = 91 → 35x = 91 – 14y = 91 – 14 (4 +
5t) = 91 – 56 – 70t = 35 – 70t
x = 1 – 2t
Penyelesaian persamaan adalah:
x = 1 – 2t
y = 4 + 5t
2.
2x + 5y
= 11
Jawab:
2x +5y = 11→ 5y = 11- 2x
5y
11 (mod 2)
y
1 (mod 2)
y
1 (mod 2) → y =
1 + 2t
2x +5y = 11 →
2x = 11 – 5y
2x
= 11 – 5 ( 1 + 2t )
2x
= 11 -5 -10t
2x = 6 – 10t
x = 3 – 5t
Penyelesaian kongruensi adalah
x
= 3 – 5t
dan y = 1 + 2t
Pengecekan:
|
T
|
x
|
y
|
2x
|
5y
|
2x + 5y
|
|
1
|
2
|
3
|
-4
|
5
|
11
|
|
2
|
-7
|
5
|
-14
|
25
|
11
|
|
4
|
-17
|
9
|
-34
|
45
|
11
|
3. 17x + 13y = 21
Jawab:
17x + 13y = 21 → 13y = 21 – 17x → 13y ≡ 21(mod
17) → 13y ≡ 4(mod 17)
Proses penyelesaian:
13y ≡ 4(mod 17) y
=
17z ≡ -4(mod)
4z ≡ -4 (mod 13) z =
13t ≡ 4(mod 4)
t ≡ 0(mod4) t
= 0
Proses penyelesaian di atas menunjukkan bahwa:
y ≡ -1(mod 17) ≡ 16(mod 17)
y ≡ 16(mod 17) → y = 16 + 17t
17x = 21 – 13y → 17x = 21 – 13(16 + 17t)
= 21 – 208 – 221t
= -187 –
221t
x = -11 – 13t
Penyelesaian persamaan adalah:
x = -11 – 13t
y = 16 + 17t
4. 6x + 15y = 8
Jawab:
6x + 5y = 8 → 6x = 8 – 15y → 6x ≡ 8 (mod 15)
Karena (6,8) = 2 15, maka kongruensi
ini tidak mempunyai
penyelesaian, berarti pula persamaan 6x + 15y = 8 mempunyai tidak mempunyai
penyelesaian.
BAB IIi
PENUTUP
Ø Kesimpulan
:
Suatu sistem persamaan linear dapat
diselesaikan dengan beragam cara yang berbeda. Jika kita hanya tertarik pada
solusi yang merupakan bilangan bulat, dapat digunakan persamaan Diophantine.
Dengan persamaan Diophantine, jika hanya diinginkan hasil yang tak negatif, banyaknya
persamaan dapat kurang dari banyaknya peubah. Untuk lebih menyederhanakan
persamaan Diophantine, dapat kita manfaatkan algoritma Eucliedean. Dengan ini,
kita akan membutuhkan peubah tambahan sebagai parameter. Selanjutnya dengan
melakukan perhitungan terhadap peubah tersebut akan didapat bilangan bulat yang
sesuai. Dengan persamaan Diophantine semula. Satu hal yang harus diingat ketika
melakukan persamaan Diophantine adalah kita harus berhati-hati dalam mencatat
“jejak” dari paramer yang digunakan. Karena diakhir proses, kita harus
menyulihkan kembali setiap “jejak” ke dalam “jejak” sebelummya.
DAFTAR PUSTAKA
Sukirman, 1997. Ilmu Bilangan. Tanggerang Selatan: Universitas
Terbuka.
http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2007-2008/Makalah/MakalahIF2153-0708-030.pdf
Langganan:
Komentar (Atom)