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.

Meskipun sederhana dan

mudah, cara biasa menjadi

semakin sulit dan tidak efisien jika

banyaknya kongruensi linier

bertambah banyak, yaitu barisan

atau daftar bilangan yang dibuat

menjadi panjang.