Sistem Pengkongruenan Linier

Teorema 5.15

Misalkan m suatu bilangan asli dan (∆, m) = 1 dengan ∆= ad – 

bc, makasystem perkongruenan linear

ax + by ≡ e (mod m)

cx + dy ≡ f (mod m)

 mempunyai penyelesaian (x,y), dengan

x ≡ ∆^-1 (de – bf) (mod m)

y ≡ ∆^-1 (af  – ce) (mod m)

dengan ∆^-1 adalah invers dari ∆ modulo m

 Bukti

Untuk menyelesaikan system perkongruenan linear ini, kita dapatmelakukan dengan eliminasi salah satu variable x atau y lebih dulu.Pertama kita akan mencari x dengan mengeliminasi variable y terlebih dahulu. Mengeliminasi variable y dengan mengalikan perkongruenan pertama dengan ddan perkongruenan kedua dengan b, sehingga diperoleh

adx + bdy ≡ de (mod m)

 bcx + bdy ≡ bf (mod m)

 hasil pengurangan dari perkongruenan pertama dan kedua adalah

adx + bcx ≡ de  – bf (mod m)

(ad – bc)x≡ de – bf (mod m)

dan karena ∆= ad – bc, maka

∆x ≡ de – bf (mod m)

Selanjutnya karena gcd dari (∆,m) = 1, maka ∆ mempunyai invers modulo m,yaitu ∆^-1. Jika kedua ruas perkongruenan terakhir dikalikan dengan ∆^-1maka diperoleh

∆^-1. ∆ x ≡ ∆^-1 . de – bf (mod m)

x ≡ ∆^-1  (de – bf) (mod m)

dengan cara yang sama seperti diatas, kita dapat mencari nilai y denganmengeliminasi variable x yaitu pada system perkongruenan semula kita kalikandengan perkongruenan pertama dengan c dan perkongruenan kedua dengan a,diperoleh

acx + bcy ≡ ce (mod m) 

acx + ady ≡ af (mod m)

jika perkongruenan kedua dikurangi dengan perkongruenan pertama, makadiperoleh

(ad – bc) y ≡ af – ce (mod m)

atau ∆y ≡ af – ce (mod m)

Selanjutnya karena (∆, m) = 1, maka ∆ mempunyai invers modulo m, yaitu ∆^-1. Jika kedua ruas perkongruenan terakhir dikalikan dengan ∆^-1 maka diperoleh

y ≡ ∆^-1 (af  – ce) (mod m)

sampai di sini, kita telah menunjukkan bahwa jika (x,y) adalah penyelesaian darisystem perkongruenan, maka

x ≡ ∆^-1(de – bf) (mod m), y ≡ ∆^-1 (af – ce) (mod m).

Teorema 5.16

Jika A = (a_ij) dan B = ( b_ij) adalah matriks-matriks berukuran n x k dengan A ≡ B (mod m),

C = (c_ij) ialah matriks berukuran k x p dan D = (d_ij)ialah matriks AC ≡ BC ( mod m ) dan DA ≡ DB (mod m )

 Bukti

Cara pertama

Misalkan AC = E = (e_ij) ialah matriks berukuran n x p dengan

dan BC = G = (g_ij)adalah matrik berukuran n x p

dengan  

Karena A ≡ B (mod m), maka a_ij = b_ij (mod m) untuk setiap i dan j, sehingga a_ijc_rj = b_ijc_rj (mod m) untuk setiap 1 ≤ r ≤ k 

Akibatnya 

 (mod m), 

yaitu e_ij = g_ij (mod m)

Hal ini berarti AC ≡ BC (mod m)

Cara kedua

Misalkan C = (c_ij) adalah matriks berukuran n x k sehingga

A ≡ B (mod m)

A ≡ B + k m

A.C ≡ B. C + C. k m

A.C ≡ B. C + (C. k) m

m| AC – BC atau AC ≡ BC ( mod m )

Bukti untuk DA ≡ DB (mod m) mirip dengan bukti tersebut.

Perhatikan system n pengkronguenan linier dengan n variable berikut ini.

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n = b₁ (mod m)

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n = b₂ (mod m)

    .

    .

    .

a_n1x₁ + a_n2x₂ + ... + a_nnx_n = b_n (mod m)

 Dengan menggunakan notasi matriks, system pengkronguenan linier ini dapatdinyatakan sebagai perkonguenan matriks AX ≡ B (mod m), dengan

 Kita mengembangkan metode penyelesaian perkongruenan dalam bentuk matriks AX ≡ B (mod m). Metode ini menggunakan matriks A^-1 yaitu invers matriks A terhadap perkalian , sedemikian hingga A^-1 A ≡ 1 (mod m), dengan I ialah matriks identitas terhadap perkalian.

Teorema 5.17

Misalkan 

  adalah matriks yang elemennya bilangan bilanganbulat, sedemikian hingga det A≡  ∆ ≡ ad -bc prima relative terhadapbilangan bulat positif m. Maka diperoleh 

adalah invers dari modulo m.

Bukti

Untuk membuktikannya, teorema ini kita cukup memeriksa kebenaran

A^-1 A ≡ 1 (mod m)

Teorema 5.18

Jika A suatu matriks persegi dengan ∆ ≡ det A ≠ 0, maka A adj (A) = (det A) I

Dengan menggunakan teorema ini, kita segera akan mendapatkan rumus inverssuatu matriks persegi, seperti yang dinyatakan teorema ini.

Teorema 5.19

Jika A suatu matriks persegi dengan yang elemen elemennya bilanganbulat dan m suatu bilangan bulat positif sedemikian hingga (∆, m) = 1, maka invers dari A modulo m adalah

A^-1 = ∆^-1 adj (A)

 Bukti :

Karena

(∆, m) = 1, maka A^-1 ada. Dan karena ∆ ≠ 0 maka A adj (A) = ∆ I sehingga

A ∆^-1 adj (A) ≡ ∆ ∆^-1 I ≡ I (mod m)

∆^-1 adj (A) ≡ ∆ ∆^-1 I ≡ I (mod m)

Ini menunjukkan bahwa A^-1 = ∆^-1 adj (A) adalah invers dari modulo m.