Sistem Perkongruenan Linier Dua Variabel

A. Menyelesaikan Sistem Perkongruenan Linier Dua Variabel dengan Eliminasi dan Substitusi

Kita akan mempelajari sistem perkongruenan linier dari beberapa perkongruenan linier yang melibatkan variable yang sama dan yang memiliki bilangan modulo yang sama.

Misalkan kita ingin menentukan pasangan bilangan bulat x dan y yang memenuhi dua perkongruenan linier

3x + 4y ≡ 5 (mod 13) ...(i)

2x + 5y ≡ 7 (mod 13) ...(ii)

Cara menyelesaikan sistem perkongruenan linier:

1. Eliminasi salah satu variable x atau y

Misal kita coba mengeliminasi variabel y

15x + 20y ≡ 25 (mod 13)

8x + 20y ≡ 28 (mod 13), maka diperoleh:

7x ≡ −3 (mod 13), selesaikan

7x ≡ −3 (mod 13)

7x ≡ 49 (mod 13)

x ≡ 7 (mod 13)

2. Substitusikan x ke salahsatu perkongruenan, misal kita pilih (i)

3.7 + 4y ≡ 5 (mod 13)

21 + 4y ≡ 5 (mod 13)

4y ≡ −16 (mod 13)

y ≡ −4 (mod 13)

y ≡ 9 (mod 13)

Jadi penyelesaian sistem perkongruenan linier adalah semua pasangan (x, y) dengan

x ≡ 7 (mod 13) dan y ≡ 9 (mod 13)

B. Menyelesaikan Sistem Perkongruenan Linier Dua Variabel dengan Invers

Misalkan m suatu bilangan asli dan (∆, m) = 1 dengan ∆ = ad − bc, maka sistem perkongruenan linier

ax + by ≡ e (mod m)

cx + dy ≡ f (mod m)

Memiliki penyelesaian (x, y) dengan

x ≡ ∆⁻¹(de − bf) (mod m)

y ≡ ∆⁻¹(af − ce) (mod m)

Dengan ∆⁻¹ adalah invers dari ∆ modulo m

Contoh:

2x + 3y ≡ 6 (mod 7)

x + 4y ≡ 5 (mod 7)

∆ = ad − bc = 2.4 − 1.3 = 5

∆⁻¹(mod 7) dapat dicari dengan menyelesaikan 5δ ≡ 1 (mod 7)

5δ ≡ 1 (mod 7)

5δ ≡ 15 (mod 7)

δ ≡ 3 (mod 7)

Memiliki penyelesaian (x, y) dengan

x ≡ 5⁻¹(4.6 − 3.5) (mod 7)

x ≡ 3.9 (mod 7)

x ≡ 6 (mod 7)

y ≡ 5⁻¹(2.5 − 1.6) (mod 7)

y ≡ 3.4 (mod 7)

y ≡ 5 (mod 7)

Jadi penyelesaian system perkongruenan linier adalah semua pasangan (x, y) dengan

x ≡ 6 (mod 7) dan y ≡ 5 (mod 7)

C. Kekongruenan Matriks

Misailan A = (a_ij) dan B = (b_ij) masing-masing matriks berukuran n × k yang elemen-elemennya bilangan bulat. Matriks A kongruen dengan matriks B modulo m, dinotasikan

A ≡ B (mod m)

Jika  a_ij ≡ b_ij (mod m) untuk setiap pasangan (i, j) dengan 1 ≤ i ≤ n dan 1 ≤ j ≤ k

Contoh:

D. Invers Matriks Modulo m

Misal matriks A

adalah matriks yang elemennya bilangan bulat, sedemikian sehingga det(A) = ∆ = ad − bc koprim terhadap m. Maka

adalah invers matriks A modulo m.

Contoh:

Diberikan matriks

det(A) = ∆ = 3.5 − 2.4 = 7

Misal akan ditentukan A⁻¹(mod 13)

Mula-mula, tentukan ∆⁻¹(mod 13) = 7⁻¹(mod 13)

7δ ≡ 1 (mod 13)

7δ ≡ 14 (mod 13)

δ ≡ 2 (mod 13)

E. Menyelesaikan Sistem Perkongruenan Linier Dua Variabel dengan Matriks

Sistem Perkongruenan Linier

3x + 4y ≡ 5 (mod 13)

2x + 5y ≡ 7 (mod 13)

Dapat ditulis sebagai:

Kita dapat menyelesaikan perkongruenan tsb dengan menggunakan bentuk matriks:

AX ≡ B (mod m)

Kita perlu mencari A⁻¹ yang memenuhi A⁻¹A ≡ I (mod m)

Dengan I matriks identitas terhadap perkalian.

Kita bisa mencari solusi:

Jadi penyelesaian sistem perkongruenan linier adalah semua pasangan (x, y) dengan

x ≡ 7 (mod 13) dan y ≡ 9 (mod 13)