Download - Kelompok 2 (menyelesaikan kongruensi linear)
MENYELESAIKAN KONGRUENSI LINIER
KELOMPOK 2 :
RISNA AFRIANI (30610E3025)
DAN
IKA MELIANI (30610E3008)
Menyelesaikan Kongruensi
LinierPada kongruensi ax ≡ b (mod m)dengan nilai-nilai a, b, dan m yangrelative besar dilakukan denganmenyederhanakan kongruensi, yaitumengganti kongruensi semula dengankongruensi lain yang mempunyaibilangan modulo lebih kecil. Prosedur inibisa diulangi sampai diperoleh suatukongruensi yang selesaiannya mudahditentukan.
Diketahui kongruensi linier ax ≡ b (mod m),misalkan a < m (jika a > m, maka a dapat“dikecilkan” dengan jalan mencari residu (sisa)positif terkecil dari a modulo m).
ax ≡ b (mod m), maka m│ax – b, sehingga
ax – b = my untuk suatu y Z, berarti
my + b = ax, dan akibatnya a│my + b, atau
my ≡ – b (mod a).
Karena m > a, maka m dapat “dikecilkan”dengan jalan mencari residu positif terkecil darim modulo a. Sampai pada tahap ini jelasbahwa kongruensi linier semula ax ≡ b (modm) berubah menjadi kongruensi linier my ≡ – b(mod a) yang lebih “sederhana” karenamempunyai modulo a yang lebih kecil dari a.
Selesaikan kongruensi linier my ≡ –b
(mod a) jika memang sudah menjadi
lebih mudah untuk diselesaikan,
misalkan selesaiannya adalah y = yo.
Dengan demikian dari ax – b = my,
atau x = (my+b)/a, dapat ditentukan
bahwa x0 = (my0+b)/a merupakan suatu
selesaian kongruensi linier ax ≡ b (mod
m).
Ulangi langkah serupa jika memangkongruensi linier my ≡ – b (mod a)masih sulit untuk diselesaikan. Misalkanresidu positif terkecil m modulo aadalah k, maka my ≡ – b (mod a) dapatdiubah menjadi az ≡ b (mod a).Demikian seterusnya sehingga padatahapan tertentu dapat diperoleh suatuselesaian, dan dari selesaian yangdiperoleh dapat diproses mundursehingga diperoleh selesaian darikongruensi ax ≡ b (mod m).
Contoh
Selesaikan 19x ≡ 2 (mod 49)
Jawab:
19x ≡ 2 (mod 49)
49y ≡ - 2 (mod 19) atau
11y ≡ - 2 (mod 19)
19z ≡ 2 (mod 11) atau
8z ≡ 2 (mod 11)
11r ≡ - 2 (mod 8) atau
3r ≡ - 2 (mod 8)
Diperoleh selesaian, yaitu r0 ≡ 2 (mod 8)
Selanjutnya
z0 = (11r0 + 2)/8
= (11.2 + 2)/8 = 3,
y0 = (19z0 – 2 )/11
= (19.3 – 2 )/11 = 5, dan
x0 = (49y0 + 2)/19
= (49.9 + 2)/19 =13.
Selesaian kongruensi adalah
x ≡ 13 (mod 49)
Langkah – langkah memperoleh selesaian
di atas dapat diperagakan sebagai berikut :
19x ≡ 2 (mod 49) x0 = (49y0 + 2)/19 = 13
49y ≡ - 2 (mod 19)
11y ≡ - 2 (mod 19) y0 = (19z0 – 2 )/11 = 5
19z ≡ 2 (mod 11)
8z ≡ 2 (mod 11) z0 = (11r0 + 2)/8 = 3
11r ≡ - 2 (mod 8)
3r ≡ - 2 (mod 8) r0 = 2
Selesaian kongruensi adalah x ≡ 13 (mod 49)
Sistem Kongruensi Linier Simultan
Sistem Kongruensi Linier Simultan adalahgabungan dari dua atau lebih kongruensi linierdengan satu variabel.
Definisi 4.3
Sistem kongruensi linier satu variabel :
x ≡ a1(mod m1), x ≡ a2(mod m2), …, x ≡ ar(modmr), disebut sistem kongruensi linear simultan
Untuk mencari selesaian system kongruensilinier simultan, kita memerlukan pembahasanawal tentang system yang terdiri dari duakongruensi linier.
Teorema 4.2
Sistem kongruensi linier simultan :
x ≡ a1(mod m1), x ≡ a2(mod m2)
dapat diselesaikan jika dan hanya
jika
a1 ≡ a2 (mod (m1,m2))
Beberapa cara yang dapat digunakan
menyelesaikan sistem kongruensi linier
simultan adalah cara biasa, cara iterasi,
dan cara sisa China.
Cara Biasa
Cara ini disebut biasa karena kita hanya
membuat barisan bilangan yang memenuhi
masing-masing kongruensi, dan dilanjutkan
dengan pencarian unsur persekutuan dari
semua kongruensi.
Contoh 1 :
Selesaikan sistem kongruensi linier simultan
x ≡ 13 (mod 16) dan x ≡ 5 (mod 14)
Jawab :
13 ≡ 5 (mod (16,14)), atau 8 ≡ 0 (mod 2),
maka sistem kongruensi dapat diselesaikan.
x ≡ 13 (mod 16) ≡ 13,29,45,61,77,93,109, … (mod
16)
x ≡ 5 (mod 14) ≡ 5,19,33,47,61,75,89,103, … (mod
14)
Unsur persekutuan dari kedua kongruensi linier
adalah 61, sehingga :
x ≡ 61 (mod 16) dan x ≡ 61 (mod 14)
dan sesuai dengan teorema 3.6 (b),
x ≡ 61 (mod [16,14]) ≡ 61 (mod 112)
Contoh :
Sistem kongruensi linier simultan x ≡ 15
(mod 51) dan x ≡ 7 (mod 42) tidak
mempunyai selesaian sebab 15 tidak
kongruen 7 modulo (51,42) = 3.