Perkongruenan Linier [PDF]

Citation preview

PERKONGRUENAN LINEAR Definisi 3.5 Pengkongruenan yang variabel berpangkat paling tinggi satu disebut pengkongruenan linear, dengan bentuk umum: ax ≡ b (mod m), dengan a ≡ 0 (mod m)



Contoh: 1.



3x ≡ 4 (mod 5) (perkongruenan linier) Ini sebuah pengkongruenan linear karena 3 ≡ 0 (mod 5) dan pangkat variabel tertinggi adalah satu.



2.



2x ≡ 4 (mod 7) (perkongruenan linier) Ini sebuah pengkongruenan linear karena 3 ≡ 0 (mod 5) dan pangkat variabel tertinggi adalah satu.



3.



x4 + 3x – 3 ≡ 0 (mod 31) (bukan perkongruenan linier) Ini bukan pengkongruenan linear karena pangkat variabel tertinggi lebih besar dari satu yaitu berpangkat empat.



4.



14x ≡ 1 (mod 7) (bukan perkongruenan linier) Ini bukan pengkongruenan linear karena 14 ≡ 0 (mod 7)



Definisi 3.6:



s disebut solusi dari perkongruenan linier ax ≡ b (mod m) jika s adalah residu terkecil modulo m yang memenuhi perkongruenan ax ≡ b (mod m). Contoh: Tentukan solusi dari 2x ≡ 4 (mod 7)



Jawab: Cara I: i. Untuk x = 0, maka 2x ≡ 4 (mod 7) 2 (0) ≡ 4 (mod 7) 0 ≡ 4 (mod 7) Karena 7 | 0 – 4, maka x = 0 bukan solusi. ii. Untuk x = 1, maka 2x ≡ 4 (mod 7) 2 (1) ≡ 4 (mod 7) 2 ≡ 4 (mod 7) Karena 7 | 2 – 4, maka x = 1 bukan solusi. iii. Untuk x = 2, maka 2x ≡ 4 (mod 7) 2 (2) ≡ 4 (mod 7) 4 ≡ 4 (mod 7) Karena 7 | 4 – 4, maka x = 2 bukan solusi. iii. Dengan cara yang sama untuk x = 3, 4, 5, dan 6 diketahui bahwa x = 3, 4, 5, dan 6 bukan solusi dari pengkongruenan 2x ≡ 4 (mod 7). Jadi, solusi dari pengkongruenan 2x ≡ 4 (mod 7) adalah x = 2. Cara II: 2x ≡ 4 (mod 7) 2x ≡ 2.2 (mod 7) Karena (2,7) = 1, berdasarkan Teorema 3.5 maka x ≡ 2 (mod 7) Ini berarti solusi dari pengkongruenan 2x ≡ 4 (mod 7) adalah 2.



Teorema 3.18: Jika a ≡ b (mod m) maka berlaku a ≡ b + km (mod m) untuk setiap bilangan bulat k. Bukti: Ambil a, b, m ϵ Z dengan m > 0 dan a ≡ b (mod m). Akan ditunjukkan bahwa a ≡ b + km (mod m) untuk setiap k ϵ Z. Karena a ≡ b (mod m) maka m | a – b. Karena m | a – b dan m | km untuk setiap k ϵ Z, maka m | (a – b) – km atau m | a – (b + km). Ini berarti a ≡ b + km (mod m). Contoh: Tentukan solusi dari 4x ≡ 6 (mod 18) Jawab: 4x ≡ 6 (mod 18), berdasarkan Teorema 3.18, dengan k = 1, maka 4x ≡ 6 + 1.18 (mod 18) 4x ≡ 24 (mod 18) 4x ≡ 4.6 (mod 18), berdasarkan Teorema 3.5, dengan (4,18) = 2, maka x ≡ 6 (mod 9) Jadi solusi dari 4x ≡ 6 (mod 18) adalah solusi dari x ≡ 6 (mod 9) yaitu 6. Solusi lainnya adalah 6 + 1.9 yaitu 15. Teorema 3.19 Jika (a,m) | b, maka pengkongruenan linear ax ≡ b (mod m) tidak mempunyai solusi. Bukti: Ambil a, b, m ∈ Z dan m > 0 dengan (a,m) | b



Akan ditunjukkan: Perkongruenan linier ax ≡ b (mod m) tidak memiliki solusi. Bukti kontraposisi dari teorema tersebut adalah: Jika ax ≡ b (mod m) memiliki solusi, maka (a,m) | b. Misalkan r adalah solusi dari ax ≡ b (mod m), maka ar ≡ b (mod m), sehingga ar – b = km untuk suatu bilangan bulat k. Perhatikan ar – b = km. Karena (a,m) | a dan (a,m) | km, maka (a,m) | b. Karena (a,m) | b mempunyai solusi, maka terbukti bahwa (a,m) | b. Terbuktilah kontraposisi dari teorema itu, sehingga terbukti pula teorema itu. Contoh: Tentukan apakah 6x ≡ 7 (mod 8) mempunyai solusi atau tidak. Jawab: Karena (6,8) = 2 dan 2 | 7, maka perkongruenan linier 6x ≡ 7 (mod 8) tidak mempunyai solusi. Teorema 3.20 Jika (a,m) = d dan d |b, maka perkongruenan linier ax ≡ b (mod m) memiliki d buah solusi. Bukti: Ambil a, b, m ϵ Z, di mana (a,m)= d dan d|b. Karena (a,m) = d, maka d|a dan d|m Akan ditunjukkan bahwa perkongruenan linier ax ≡ b (mod m) memiliki d solusi. Dan seterusnya harus ditunjukkan bahwa tak ada solusi lain kecuali d solusi itu. Sekarang akan dibuktikan bahwa perkongruenan linier itu memilki d solusi.



(a,m) = d berarti ada a’ dan m’, sehingga a = da’ dan m = dm’, d|b berarti ada b’, sehingga b = db’. Sehingga dari ax ≡ b (mod m) menjadi da’x ≡ db’(mod m) atau a’x ≡ b’ (mod m’) Dari (a,m) =d memberikan (da’,dm’) = d atau (a’,m’) = 1. Menurut teorema 5.11, jika (a’,m’) = 1, maka a’x ≡ b’ (mod m’) memiliki satu solusi. Misalkan solusi itu r, maka d buah bilangan, yaitu: r, r + m’, r + 2m’,..., r + (d – 1 )m’, atau r + km’ untuk k = 0, 1, 2, ..., (d – 1) memenuhi perkongruenan ax ≡ b (mod m). Hal ini ditunjukkan sebagai berikut: Pertama, setiap r + km’ dengan k = 0, 1, 2, ...,(d – 1 ) memenuhi perkongruenan ax ≡ b (mod m). ax = a(r + km) ax = da’(r + km’) ax = da’r + da’km’ ax = (a’r) d + (a’k) (m’d) Karena a’r ≡ b’ (mod m’) dan m’d = m, maka ax ≡ b’d + (a’k) m (mod m) ax ≡ b’d (mod m) ax ≡ b (mod m) karena b = b’d Jadi r + km’ untuk k = 0, 1, 2, ..., (d – 1) memenuhi perkongruenan ax ≡ b (mod m). Kedua, setiap r + km’ dengan k = 0, 1, 2, ..., (d – 1 ) adalah residu terkecil modulo m. Ditunjukkan sebagai berikut: r adalah solusi dari a’x ≡ b’ (mod m’) berarti m ≥ 0 , sehingga 0 ≤ r + km’.



r + km’ ≤ r + (d – 1)m’ untuk setiap k = 0, 1, 2, ..., (d – 1) r + (d – 1)m’ ¿ m’ + (d – 1)m’ = dm’ = m Jadi, 0 ≤ r + km’ ¿ m Hal ini menunjukkan bahwa r + km’ untuk k = 0, 1, 2, ..., (d – 1) yang kongruen modulo m, sebab r + km’ untuk k = 0, 1, 2, ..., (d – 1) adalah residu-residu terkecil modulo m yang berbeda. Sekarang akan ditunjukkan bahwa tidak ada solusi lain, kecuali d buah solusi itu. Tadi diambil bahwa r adalah solusi dari perkongruenan linier ax ≡ b (mod m). Misalkan s adalah solusi lain, maka as ≡ b (mod m) dan ar ≡ b (mod m). Jadi as ≡ ar ≡ b (mod m) Karena (a,m) = d dan as ≡ ar (mod m) diperoleh bahwa: s ≡ r (mod



m ) d



s ≡ r (mod m’) karena m = dm’. Ini berarti s – r = tm’ atau s = r + tm’ untuk semua bilangan bulat t. Karena s adalah residu terkecil modulo m, sedangkan semua residu terkecil modulo m berbentuk r + km’ dengan k = 0, 1, 2, ..., (d – 1) Maka s = r + tm’ adalah salah satu diantara r + km’ dengan k = 0, 1, 2, ..., (d – 1) Contoh: 1. Tentukan solusi dari pengkongruenan 2x ≡ 4 (mod 6). Jawab: 2x ≡ 4 (mod 6) Karena (2,6) = 2 dan 2 | 4, maka pengkongruenan ini memiliki 2 buah solusi. 2x ≡ 4 (mod 6)



2x ≡ 2.2 (mod 6), berdasarkan Teorema 3.5 dengan d = 2, maka x ≡ 2 (mod 3). Jadi solusi dari pengkongruenan ini adalah 2 dan 2 + 1.3 yaitu 5. 2. Tentukan solusi dari 6x ≡ 15 (mod 33). Jawab: 6x ≡ 15 (mod 33) Karena (6,33) = 3 dan 3 | 15, maka pengkongruenan ini memiliki 3 buah solusi. 6x ≡ 15 (mod 33) 3.2x ≡ 3.5 (mod 33), berdasarkan Teorema 3.5 dengan (3,33) = 3, maka 2x ≡ 5 (mod 11) 2x ≡ 5 + 1.11 (mod 11) 2x ≡ 16 (mod 11) 2x ≡ 2. 8 (mod 11), berdaraskan Teorema 3.5 dengan (2,11) = 1, maka x ≡ 8 (mod 11). Jadi solusi dari pengkongruenan 6x ≡ 15 (mod 33) adalah 8. Solusi lainnya adalah 8 + 1.11 yaitu 19 dan 8 + 2.11 yaitu 30.



PERKONGRUENAN LINEAR DIOPHANTUS Pada persamaan linear biasa, domain x dan y adalah bilangan real dan domain hasil juga bilangan real. Sedangkan pada persamaan linear Diophantus, domain x dan y adalah bilangan bulat dan domain hasil juga bilangan bulat. Bentuk umum persamaan linear Diophantus (juga dibaca:Diophantin) adalah: ax + by = c, di mana a, b, c ϵ Z dan a, b ≠ 0. Definisi 3.7 Bilangan bulat x dan y yang memenuhi persamaan linear ax + by = c, di mana a, b, c ϵ Z dan a, b ≠ 0 disebut solusi persamaan linear Diophantus. Teorema 3.21 1. Persamaan linear Diophantus ax + by = c mempunyai solusi jika dan hanya jika d|c dimana d = (a,b). 2. Jika (x0,y0) adalah salah satu solusi dari persamaan linear Diophantus ax +by = c, maka solusi lainnya adalah



( db ) t dan y= y −( da ) t ,



x=x 0 +



0



di mana t anggota bilangan bulat. Persamaan ax + by = c berarti ax ≡ c (mod b) atau 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 dari perkongruenan ax ≡ c (mod b) atau by ≡ c (mod a). Kemudian nilai x atau y yang diperoleh dengan parameter t disubstitusikan ke persamaan ax + by = c untuk mencari nilai x atau y. Contoh: Tentukan solusi dari persamaan diophantin 7x + 15 y = 51



Jawab: Cara I: 7x + 15 y = 51 (7, 15) = 1 dan 1|51, ini berarti persamaan Diophantin di atas mempunyai satu solusi. 7x + 15y = 51 15y – 51 = -7x 15y – 51 = 7(-x) Ini berarti 7|15y – 51 atau 15y ≡ 51 (mod 7) 3 . 5y ≡ 3 . 17 (mod 7), berdasarkan Teorema 3.5, dengan (3,7) = 1, maka 5y ≡ 17 (mod



7 ) (3,7)



5y ≡ 17 (mod 7) 5y ≡ 17 – 1.7 (mod 7) 5y ≡ 10 (mod 7) 5y ≡ 5 . 2 (mod 7), berdasarkan Teorema 3.5, dengan (5,7) = 1, maka y ≡ 2 (mod 7), atau y = 2 + 7t (t bilangan bulat) Substitusi nilai y = 2 + 7t ke persamaan semula 7x + 15y = 51 7x + 15 (2 + 7t) = 51 7x + 30 + 105t = 51 7x = 21 – 105t x = 3 – 15t Jadi, himpunan penyelesaian: {(x, y)| x = 3 – 15t, y = 2 + 7t, t bilangan bulat}



Cara II: 7x + 15 y = 51 (7, 15) = 1 dan 1|51, ini berarti persamaan Diophantin di atas mempunyai satu solusi. 7x + 15y = 51 7x – 51 = -15y 7x – 51 = 15(-y) Ini berarti 15|7x – 51 atau 7x ≡ 51 (mod 15) 7x ≡ 51 – 2.15 (mod 15) 7x ≡ 21 (mod 15) 7x ≡ 7.3 (mod 15), berdasarkan Teorema 3.5, dengan (7,15) = 1, maka x ≡ 3 (mod 15), atau x = 3 + 15t (t bilangan bulat) Substitusi nilai x = 3 + 15t ke persamaan semula 7x + 15y = 51 7(3 + 15t) + 15y = 51 21 + 105t + 15y = 51 15y = 30 – 105t y = 2 – 7t Jadi, himpunan penyelesaian: {(x, y)| x = 3 + 15t, y = 2 – 7t, t bilangan bulat}



Teorema 3.22 (Teorema Sisa) Sistem pengkongruenan linear x ≡ ai (mod mi), i = 1, 2, 3, ... ,k dengan (mi,mj) = 1 untuk setiap i ≠ j memiliki solusi bersama modulo m dan solusi bersama itu tunggal dengan m = mi. m2. m3 ... mk.



Contoh: Tentukan sebuah bilangan yang jika dibagi 3 sisanya 2, jika dibagi 5 sisanya 3, dan jika dibagi 4 sisanya 1. Jawab: Cara I: Misalkan bilangan tersebut adalah x, maka x ≡ 2 (mod 3) ..... (1) x ≡ 3 (mod 5) ..... (2) x ≡ 1 (mod 4) ..... (3) Dari (1), (2), dan (3) di atas dapat ditulis x = 3k1 + 2 ..... (4) x = 5k2 + 3 ..... (5) x = 4k3 + 1 ..... (6) Substitusikan (4) ke (3) x ≡ 1 (mod 4) 3k1 + 2 ≡ 1 (mod 4) 3k1 + 2 – 2 ≡ 1 – 2 (mod 4) (Ingat Teorema: “Jika a ≡ b (mod m), maka a + c ≡ b + c (mod m) untuk setiap bilangan bulat c”)



3k1 ≡ -1 (mod 4) 3k1 ≡ -1 + 1.4 (mod 4) 3k1 ≡ 3 (mod 4), karena (3,4) = 1 maka k1 ≡ 1 (mod 4) k1 ≡ 4k3 + 1 ..... (7) Substitusikan (7) ke (4) x = 3k1 + 2 x = 3(4k3 + 1) + 2 x = 12k3 + 5 ..... (8) Substitusikan (8) ke (2) x ≡ 3 (mod 5) 12k3 + 5 ≡ 3 (mod 5) 12k3 + 5 – 5 ≡ 3 – 5 (mod 5) 12k3 ≡ -2 (mod 5) 2.6k3 ≡ 2(-1) (mod 5), karena (2,5) = 1, maka 6k3 ≡ -1 (mod 5) 6k3 ≡ -1 + 5.5 (mod 5) 6k3 ≡ 24 (mod 5) 6k3 ≡ 6.4 (mod 5), karena (6,5) = 1, maka k3 ≡ 4 (mod 5) atau k3 = 4 + 5t ..... (9) Substitusikan (9) ke (8) x = 12k3 + 5



x = 12(4 + 5t) + 5 x = 48 + 60t + 5 x = 53 + 60t, atau x ≡ 53 (mod 60) Jadi bilangan yang dicari adalah x = 53. Cara II: Misalkan bilangan tersebut adalah x, maka x ≡ 2 (mod 3) x ≡ 3 (mod 5) x ≡ 1 (mod 4) Sehingga diketahui bahwa a1 = 2,



a2 = 3, a3 = 1, m1 = 3, m2 = 5, dan m3 = 4.



Mi = (m1m2m3) : mi, untuk i = 1, 2, 3, dan si adalah solusi dari Mi x ≡ 1 (mod mi), i = 1, 2, 3. M1 = 5.4 = 20, sehingga 20x ≡ 1 (mod 3) 20x ≡ 1 + 13.3(mod 3) 20x ≡ 40 (mod 3) atau x ≡ 2 (mod 3), sehingga s1 = 2. M2 = 3.4 = 12, sehingga 12x ≡ 1 (mod 5) 12x ≡ 1 + 7.5(mod 5) 12x ≡ 36 (mod 5) atau x ≡ 3 (mod 5), sehingga s2 = 3. M3 = 3.5 = 15, sehingga 15x ≡ 1 (mod 4) 15x ≡ 1 + 11.4 (mod 4)



15x ≡ 45 (mod 4) atau x ≡ 3 (mod 4), sehingga s3 = 3 Maka s = a1s1M1 + a2s2M2 + a3s3M3 = 2.2.20 + 3.3.12 + 1.3.15 = 80 + 108 + 45 = 233 Maka sistem perkongruenan di atas dapat dinyatakan sebagai x ≡ s (mod m1m2m3) x ≡ 233 (mod 3.5.4) x ≡ 233 (mod 60) x ≡ 233 – 3.60 (mod 60) x ≡ 53 (mod 60) Jadi bilangan yang dicari adalah x = 53. Jika yang ditanyakan solusi dari sistem perkongruenan linear maka nilainya banyak, yaitu: 53, 113, 173,….