Pendidikan & Pembelajaran: Teori Bilangan (Persamaan Linier Deophantine

BAB I

PENDAHULUAN

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 )² + (10 – x)² = 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 x² = 1 + 30y² dan x²= 1 + 26y² yang kemudian diubah menjadi persamaan x² = 1 + py², 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 x² + y² = a²atau x³+ y³ = a³, 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 Linear Diophantine

Persamaan Linear Diophantine adalah persamaan yang koefisien dan variabel-nya berupa bilangan bulat. Ada 3 kemungkinan solusi persamaan diophantine, yaitu:

- Tidak ada

- Hanya ada satu penyelesaian

- Lebih dari satu penyelesaian

2.1.1 Algoritma Euclid

· Algoritma Euclidean adalah algoritma untuk mencari FPB dari dua buah bilangan bulat.

· Euclid, penemu algoritma Euclidean, adalah seorang matematikawan Yunani yang menuliskan algoritmanya tersebut dalam bukunya yang terkenal, Element.

· Diberikan dua buah bilangan bulat tak-negatif m dan n (m ³n). Algoritma Euclidean berikut mencari pembagi bersama terbesar dari m dan n.

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 = x₀ + ( dan y = y₀ – ( dengan n Є Z dan (x₀,y₀) adalah suatu penyelesaian bulat.

Bukti:

Misalkan x,y Є Z memenuhi ax + by = c dan d | c

Karena d = ( a,b), maka tentu ada (x₁, y₁ Є Z ) sehingga d = ax₁ + by₁

d | c → c = kd ( k Є Z) → c = k ( ax₁ + by₁ ) → c = a (kx₁) + b (ky₁) → (c = ax₁ + by₁ atau ax₁ + by₁ = c)

Ternyata dengan mengambil x₀= kx₁ dan y₀ = ky₁, maka (x₀,y₀) memenuhi persamaan, sehingga (x₀,y₀) merupakan satu penyelesaian.

Untuk menunjukkan terdapat tak hingga banyaknya penyelesaian,

ambil: x = x₀ + ( dan y = y₀ - ( dengan n Є Z

Jika nilai – nilai x dan y disubstitusikan ke dalam persamaan, maka diperoleh:

ax + by = a {x₀ + ( } + b {y₀ – ( }

= ax₀ + a ( + by₀ – b (

= ax₀ + by₀ + (a ( – (a ( /n)

ax + by = c

Karena n Є Z, maka terdapat tak hingga banyaknya (x,y) dengan:

x = x₀ + ( dan y = y₀ – (

dan memenuhi persamaan ax + by = c.

Sekarang akan ditunjukkan bahwa setiap penyelesaian dari ax + by = c dalam bentuk:

x = x₀ + ( dan y = y₀ – (

Misalkan x,y Є Z dan ax + by = c

Karena ax + by + c dan ax₀+ by₀ = c, maka:

a(x – x₀) + b(y – y₀) = 0

a(x – x₀) = b(y₀ – y)

( a/d) (x – x₀) = ( (y₀ –y)

( a/d) | ( (y₀ – y)

{(a/d)| ( (y₀ – y) dan (a/d , b/d ) = 1}

( a/d)| (y₀ – y)

( a/d)| (y₀ –y)

y₀ – y = n(a/d)

y = y₀ – (n(a/d))

{y = y₀ – ( a/d)n dan a(x – x₀) = b(y₀ – y) }

→ a(x – x₀) = b( a/d)n

→ x – x₀ = (b/d)n

→ x = x₀ + (b/d)n

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 x₁,y₁ Є Z sehingga 4x₁ + 5y₁ = 1.

Karena 5 = 1.4 + 1 atau (4)(-1) + (5)(1) = 1, maka x₁ = -1 dan y₁ =1

(4)(-1) + (5)(1) = 1

10{(4)(-1) + (5)(1)} = 10.1

4(-10) + 5(10) = 10 (Ingat: 4x + 5y = 10)

jadi, x₀ = -10 dan y₀ = 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 x₁ . y₁ Є Z sehingga 91x₁ + 22y₁ = 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 x₀ = 410 dan y₀ = -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 = 10-5y/4

= 8-4y+2-y/4

= 8-4y/4 + 2-y/4

= (2 – y) + 2-y/4

Ambil t , sehingga:

t == atau 2 – y = 4t atau y = 2 – 4t,

sehingga dari y = 2 – 4t diperoleh:

x = (2 – y) + 2-y/4

= 2 – (2 – 4t) + 2-(2-4t)/4

= 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

x = 11-8y/3

x = 9-6y+2-2y/3

x = 9-6y/3 + 2-2y/3

x = (3-2y) + 2-2y/3

Ambil t = 2-2y/3 atau 2-2y=3t atau y = 2-3t/2 atau y = 2-2t-t/2

dari y = (1-t) - t/2

Ambil u, sehingga:

u = -t/2 = -2u

t = -2u y = ( 1 + 2u) + 2u/2

= 1 + 2u + u

= 1 + 3u

x = 3 – 2y + 2-2y/3

= 3 – 2( 1+ 3u ) +2-2(1+3u)/3

= 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 = -8x-7z+21/-5

y = (x + z – 4) + (-3x-2z+1)/-5

Ambil t, sehingga

t = (-3x-2z+1)/-5

-5t = (-3x-2z+1)

-2z = 3x-5t-1

z = 3x-5t-1/-2

z = (-x+20t) + x-t-1/2

Ambil u,sehingga:

u =x-t-1/-2

-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 hasil yang diperoleh dengan menggunakan cara yang lain, sebenarnya hasil itu adalah sama.

Teorema 3.

Persamaan Linear Diophantine

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 + 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 =17(-1)+4/13 = -1

17z ≡ -4(mod)

4z ≡ -4 (mod 13) z =13 . 0 - 4 / 4= -1

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.