Modul perkuliahan
Yüklə 0,7 Mb.
|
Definisi 2.2Ditentukan x,y Z yang keduanya tidak bersama-sama bernilai 0, a Z disebut pembagi persekutuan dari x dan y jika a │x dan a │y. a Z disebut pembagi persekutuan terbesar (FPB) dari x dan y jika a adalah bilangan bulat positip terbesar sehingga a│x dan a│y. Untuk selanjutnya jika a adalah pembagi persekutuan terbesar dari x dan y dinyatakan dengan (x,y) = a. Perlu diperhatikan bahwa (x,y) = a didefinisikan untuk setiap pasangan bilangan bulat x,y Z kecuali untuk x = 0 dan y = 0. Demikian pula perlu dipahami bahwa (x,y) selalu bernilai positip yaitu (x,y) > 0, atau (x,y) ≥ 1. Contoh:
Selanjutnya perhatikan bahwa (12,16) = 4, (60,105) = 15, (3,5) = 1, (17,19)= 1. dan seterusnya.
Bukti. Dibentuk kombinasi linear (ax + by) dengan a,b Z. Barisan bilangan ax + by memuat bilangan-bilangan negatip, bilangan nol (untuk a = 0 dan b = 0), dan bilangan-bilangan yang bernilai positip. Ambil S = {ax + by │ ax + by > 0 }, maka dapat ditentukan bahwa S N. Karena N adalah himpunan terurut dan S N, maka S mempunyai unsur terkecil dan sebutlah dengan t, dan t S, maka tentu ada a = ao dan b = bo sehingga t = aox + boy dan selanjutnya dapat dibuktikan bahwa t │ x dan t │ y. Untuk membuktikan apakah t │ x, digunakan bukti tidak langsung . Misal t ┼ x, maka menurut dalil sebelumnya ada q, r Z sehingga x = qt + r dengan 0 < r < t r = x – qt = x – q(aox + boy) r = ( 1-aoq)x + (-boq)y r = a1x + b1y dengan a1 = 1-aoq Z, dan b1 = -boq Z. Jadi r = a1x + b1y Z dengan r, t S, t merupakan unsur terkecil S ran r < t. Hal ini bertentangan dengan dengan pemisalan t ┼ x. Dengan demikian anggapan t ┼ x tidaklah benar. Jadi haruslah t │ x. Dengan cara yang sama dapat ditunjukkan bahwa t │ y. Dari t │ x dan t │ y berarti t adalah pembagi persekutuan dari x dan y. d = (x,y) berarti d │ x sehingga p S sehingga x = dp. d = (x,y) berarti d │ y sehingga p S sehingga y = dp. t = aox + boy = ao (dp) + bo (dp) d │ t, d 0, t > 0 maka sesuai dengan dalil sebelumnya d t dan d tidak lebih kecil dari t, sedangkan d adalah pembagi persekutuan dari x dan y. Jadi d = t = aox + boy Berdasarkan urian di atas jelaslah bahwa d = (x,y) merupakan bilangan bulat positip terkecil yang mempunyai bentuk (ax + by) dengan a,b Z. Dengan demikian terlihat bahwa tidak ada bilangan positip selain d yang membagi x dan y dan mempunyai bentuk (ax + by)
Bukti Sesuai dengan bukti dalil 1 di atas, maka: (tx,ty) = bilangan bulat positip terkecil yang mempunyai bentuk(atx + bty) dengan bilangan a,b Z = atx + bty = t (ax + by) = t merupakan bilangan bulat positip terkecil yang mempunyai bentuk (ax+by) = t (ax +by)
Bukti d = (x,y) berarti d │x dan d │y dan , Z (x,y) = (d. , d. ) = d ( , ) Karena d > 0 maka d ( , ) atau 1 = ( , ) Dengan demikian ( , ) = 1
Bukti (y,w) = 1 maka menurut definisi FPB 1 adalah bilangan bulat positip terkecil yang mempunyai bentuk ay + bw dengan a,b Z ay + bw = 1 berarti ayx + bwx = x w │ xy → w │ axy w │ axy dan w │ bxw → w │ axy + bxw w │ axy + bwx dan axy + bxw = x → w │ x.
Bukti: (x,t) = 1 → terdapat ao dan bo Z sedemikian sehingga aox+bot=1 (y,t) = 1 → terdapat ao dan bo Z sedemikian sehingga a1y+b1t=1 aox+bot=1 → aox = 1 - bot a1y+b1t=1 → a1y = 1 - b1t a1x = 1 - bot dan a1y = 1 - b1t maka: (aox)(a1y) = (1 - bot)(1 - b1t) = 1- (bo - b1 + bob1t)t (aoa1)(xy) = (1- b2)t atau (xy) a2 +b2t=1 dengan a2 = aoa1 dan b2 = bo - b1 + bob1t Karena (xy,t) = 1 adalah bilangan bulat positip tekecil yang mempunyai bentuk (xy) a2 +b2t=1 maka (xy,t) haruslah 1 sehingga (xy,t) = 1
Bukti d = (x,y) maka menurut definisi d adalah bilangan bulat positip terbesar sehingga d │x, d│y, hal ini berarti bahwa d > 0. Demikian pula d = (x,y) berarti d adalah bilangan bulat positip terkecil dan berbentuk (ax + by), dengan a,b Z. Jadi d = ax + by. Misal f adalah sebarang pembagi persekutuan dari x dan y, maka berlaku f │x dan f │y, sehingga f │ax dan f │ay dan menurut sifat keterbagian berlaku f │ ax + by. f │ ax + by dan d = ax + by → f │d. Sebaliknya, jika d > 0 dan d │ x d│ y serta f │ d, dengan f adalah sebarang pembagi persekutuan x dan y maka d f ( karena d = kf, k Z ) untuk sebarang f pembagi persekutuan x dan y. Jadi d adalah pembagi persekutuan terbesar dari x dan y. Atau d = (x,y)
( x,y ) = ( y,x ) = ( x,-y) = ( x, y + ax ). Bukti
d = (x,y) maka menurut definisi d adalah bilangan bulat positip terbesar sehingga d │x, d│y, hal ini berarti bahwa d > 0. Jadi d = (x,y) atau d = (y,x). Karena d merupakan bilangan bulat positip terbesar yang membagi x dan y, dan y membagi (-y), maka d juga merupakan bilangan bulat positip terbesar yang membagi x dan (-y), sehingga d = (x,-y). Selanjutnya (x,y) │x berarti (x,y) │ax. (x,y) │ax dan (x,y) │y → (x,y) │ax + y. (x,y) │ax dan (x,y) │ax + y →(x,y) adalah pembagi persekutuan dari x dan y+ax, sehinggga menurut dalil sebelumnya berarti (x,y) │(x,y+ax) (x,y+ax) adalah pembagi persekutuan dari x dan (y+ax), hal ini berarti (x,y+ax) │x dan (x,y+ax) │ (y+ax) (x,y+ax) │x (x,y+ax) │ax (x,y+ax) │x dan (x,y+ax) │y+ax (x,y+ax) │y Karena (x,y+ax) adalah suatu pembagi persekutuan dari x dan y, maka (x,y+ax) │ (x,y) . Jadi (x,y+ax) = (x,y) Perhatikan bahwa:
Jika r1, r2 Z, dan r1 > r2 dan dengan proses algoritma pembagian dibentuk Suatu barisan menurun bilangan bulat r1, r2, r3, ... , rk-1, rk, rk+1=0 Yaitu:
r1 = q1r2 + r3 , 0 ≤ r3 < r2. r2 = q2r3 + r4 , 0 ≤ r4 < r2. r3 = q3r4 + r5 , 0 ≤ r5 < r2. r4 = q4r5 + r6 , 0 ≤ r6 < r2. ............................................. rk-2 = qk-2rk-1 + rk , 0 ≤ rk < r2. rk-1 = qk-1rk + rk+1 , rk+1 = 0 Maka (r1,r2) = rk. Bukti. (r1,r2) = (q1r2 + r3 , r2) ....................... (substitusi r1) = (r3,r2) ........................ (teorema) = (r3, q2r3 + r4 ) ........................ (substitusi r2) = (r3,r4) .......
....... .......
= (rk,rk+1) = (rk,0) .......................... (rk+1 = 0) (r1,r2) = rk Contoh
1. Tentukan (105,60) dan nyatakan hasilnya sebagai bentuk kombinasi linear ax + by = c, dimana c = (a,b). Dengan Algoritma Euclides diperoleh: 105 = (1) 60 + 45 60 = (1) 45 + 15 45 = (3) 15 + 0, sehingga diperoleh (105,60) = 15. Selanjutnya dengan jalan mundur diperoleh: 15 = 60 – 45 (1)] = 60 – [105 – 60(1)] = 60 – 105 + 60 (1) = (-1) 105 + (2) 60. Akhirnya diperoleh (105,60) = (-1)105 + (2) 60.
(570, 1938) = 114 114 = 570 – 2 (228) = 570 – 2 [1938 – 3.570] = 570 – 2 (1938) + 6(570) = 7 (570) – 2 (1938) = -2(1938) – 7(570). 2.2 Cara Lain Menentukan FPB dan Kombinasi Linear Marilah kita ingat kembali dalil Algoritma Pembagian Euclides Jika r1, r2 Z, dan r1 > r2 dan dengan proses algoritma pembagian dibentuk Suatu barisan menurun bilangan-bilangan bulat r1, r2, r3, ... , rk-1, rk, rk+1=0 Yaitu: r1 = q1r2 + r3 , 0 ≤ r3 < r2. r2 = q2r3 + r4 , 0 ≤ r4 < r2. r3 = q3r4 + r5 , 0 ≤ r5 < r2. r4 = q4r5 + r6 , 0 ≤ r6 < r2. ............................................. rk-2 = qk-2rk-1 + rk , 0 ≤ rk < r2. rk-1 = qk-1rk + rk+1 , rk+1 = 0 Maka (r1,r2) = rk. Sehingga diperoleh : r3 = r1 - q1r2 r4 = r2 - q2r3 r5 = r3 - q3r4 r6 = r4 - q4r5 ............................. ………………….
ri = ri-2 - qi-2ri-1 Berdasarkan persamaan tersebut di atas dapat diketahui bahwa bilangan bulat ri ditentukan oleh r1-1 dan ri-2 Andaikata Algoritma pembagian Euclid di atas dinyatakan dalam bentuk x dan y, yaitu: x1 = q1x2 + x3 , 0 ≤ x3 < x2. y1 = q1y2 + y3 , 0 ≤ y3 < y2. maka dengan cara yang sama (analog) diperoleh bentuk persamaan dalam x dan y yang secara umum dinyatakan oleh xi = xi-2 - qi-2xi-1 dan yi = yi-2 - qi-2yi-1 . Sehingga terdapat 3 persamaan dalam bentuk ri, xi, dan yi dan selanjutnya masing-masing konstanta tersebut dapat dimulai dengan syarat awal yang berbeda. r-1 = r1, ro = r2 x-1 = 1, xo = 0 y-1 = 0, ro = 1 Secara lengkap langkah untuk menentukan masing-masing konstanta dapat dilihat pada table berikut ini: iqi+1rixiyi-1*r1 (b)100...r2 (a)011...…..….…..2…..…..….…..3…..…..….…..dstnya.…..…..….…..Titik-titik pada kolom diisi dengan menyesuaikan bentuk persamaan ri = ri-2 - qi-2ri-1 xi = xi-2 - qi-2xi-1 yi = yi-2 - qi-2yi-1 Contoh.
42823 x + 6409 y = 17 Jawab Tabel untuk masing-masing konstanta adalah i qi+1rixiyi-1-4282310066409011143691-6222040-17372893-6-2(7)=-2041717-1-7(3)=-227-7(-20)=1475-0-- Diperoleh (42823,6409) = 17 dan 17 = 42823(-22) + 6409(147) i qi+1rixiyi-1-1231002560115111-2(0) =1 0 – 2(1) = -221110 – 5(1) = -51 -5(-2)=1130 (123,56) = 1 (relatif prima)
Jawab Tabel untuk masing-masing konstanta adalah sebagai berikut: i qi+1rixiyi-1-74691003246401132771-32 -0-- Diperoleh (7469,2464) = 77 dan 77 = 7469 (1) + 2464 (-3)
Jawab Tabel untuk masing-masing konstanta adalah i qi+1rixiyi-1-49991004110901115631-421546-15332172-9482-65293521522-23536-0--Diperoleh (1109,4999) = 1 dan 1 = 1109 (-2353) + 4999 (522)
Tabel untuk masing-masing konstanta adalah: i qi+1rixiyi-1-503346470510013137640337011118958243681-121124115969-12316540083992-341587807570-3558662008295-86158200938-436977799989148-77832201701-3796089113947881185-1091101806913-156425091115878752749-4410122219038-4313691913114979911375-1824814269239-15688251671561132142751-685821681313-2721944366591718172220303-3561854181496-249249739985131913214712800-7560367201175-72052971155888021114611918097-1911924722529-191233943067812723 291107535067-17250988224-0-- Diperoleh (5033464705,3137640337) = 1 dan 1 = 5033464705 (107535067) + 3137640337 (-172509882) Soal.
423x + 198y = 9 71x – 50y = 1 43x + 64y = 1
Jika x,y Z, x ≠ 0, dan y ≠ 0, maka:
Persamaan Diophantine linear secara umum ditulis sebagai ax + by = c. Nama Diophantine digunakan untuk menghormati jasa-jasa dari ahli matematika bangsa Alexanderia, Mesir bernama Diophantus yang hidup pada abad ke-3 (tahun 250 M). Misal, diberikan persamaan Diophantine 3x + 6y = 18, maka dengan cara sederhana akan diperoleh bentuk kesamaan-kesamaan:
3(-6) + 6(6) = 18 3.10 + 6(-2) = 18, dan seterusnya. Bentuk kesamaan tersebut jika diteruskan akan diperoleh sebanyak tak hingga bentuk. Oleh karena itu dalam persamaan Diophantine ax + by = c dikatakan mempunyai selesaian jika d │c dan d = (a,b). Karena d = (a,b) maka kita tahu bahwa ada bilangan bulat r dan s sehingga sehingga a = dr dan b = ds. Jika selesaian ax + by = c ada , sehingga bentuk axo+byo = c akan sesuai dengan bentuk: c = axo+byo = drxo + dsyo = d (rxo + syo).
|