B. Sistem Perkongruenan Linear

Kita akan mempelajari system perkongruenan linear dari beberapa

perkongruenan linear yang melibatkan variable yang sama dan yang

mempunyai bilangan modulo sama. Misalnya kita ingin menentukan

pasangan bilangan – bilangan bulat x dan y yang memenuhi dua

perkongruenan ini

3x + 4y ≡ 5(mod 13 )

2x + 5y ≡ 7(mod 13 )

Untuk menyelesaiakan system perkongruenan linear ini kita dapat

melakukan dengan eliminasi salah satu variable x atau y lebih dahulu.

Kita mengalikan perkongruenan pertama dengan 5 dan perkongruenan

ke 2 dengan 4, sehingga diperoleh

15x + 20y ≡ 25(mod 13 )

8x + 20y ≡ 28(mod 13 )

Jika perkongruenan pertama dikurangi dengan perkongruenan kedua,

maka diperoleh

7x ≡ -3(mod 13 )

Karena invers 7 ( mod 13 ) adalah 2, maka mengalika kedua ruas dari

perkongruenan terakhir ini dengan 2, sehingga diperoleh

2.7x ≡ 2(-3)( mod 13 )

X ≡ 7 (mod 13 )

Untuk menentukan nilai y kita mengeliminasi variable x, perkongruenan

pertama dikali 2 dan perkongruenan kedua dikali 3, sehingga diperoleh

6x + 8y ≡ 10(mod 13 )

6x + 15y ≡ 21(mod 13 )

Jika perkongruenan pertama dikurangi dengan perkongruenan kedua,

maka diperoleh

-7y ≡ -11(mod 13 )

7x ≡ 11(mod 13 )

2.7y ≡ 2.11(mod 13 )

y ≡ 9 (mod 13 )

Apakah penyelesaian system perkongruenan adalah pasangan (x,y)

dengan

X ≡ 7 (mod 13 ), y ≡ 9 (mod 13 )

Apabila nilai-nilai x dan y yang kita peroleh ini disubstitusikan pada

system perkongruenan semula maka didapatkan

3x + 4y ≡ 3.7 + 4.9 = 57 ≡ 5 ( mod 13)

2x + 5y ≡ 2.7 + 5.9 = 59 ≡ 7 ( mod 13)

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

dengan

X ≡ 7 (mod 13 ), y ≡ 9 (mod 13 )

Contoh ini merupakan ilustrasi dari pembuktian teorema berikut ini :

Teorema 5.15 :

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

maka system perkongruenan linear

ax + by ≡ e (mod m )

cx + dy ≡ f (mod m )

Mempunyai penyelesaian ( x,y ) dengan

x ≡ ∆ -1 ( de – df ) ( mod m )

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

Dengan ∆ -1 adalah invers dari ∆ modulo m

Bukti :

Kita mengalikan perkongruenan pertama dengan d dan perkongruenan

kedua dengan b, sehingga diperoleh

adx + bdy ≡ de(mod m )

bcx + bdy ≡ bf(mod m )

Hasil pengurangan dari perkongruenan pertama dan kedua adalah (ad –

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

Dan karena ∆ = ad – bc , maka ∆x ≡ de – bf (mod m )

Selanjutnya karena ( ∆,m) = 1, maka ∆ mempunyai invers modulo, yaitu

∆ -1.

Jika kedua ruas perkongruenan terakhir dikalikan dengan ∆ -1 , maka

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

Dengan cara seperti tersebut pada system perkongruenan semula dengan

a diperoleh

acx + bcy ≡ ce(mod m )

acx + ady ≡ af(mod m )

Jika perkongruenan kedua dikurangi dengan perkongruenan pertama

maka diperoleh

(ad – bc )y ≡ af – cy (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 disini kita telah menunjukkan bahwa

jika ( x,y ) adalah penyelesainan dari system perkongruenan maka x ≡ ∆ -1 (de- bf )(mod m ), y ≡ ∆ -1 (af – ce )( mod m )

Definisi 5.4:

Misalkan A = ( aij ) dan B = ( bij ) masing masing matriks berukuran nxk

yang elemen – elemennya bilangan bulat. Matriks A kongruen dengan

Matriks B modulo m, dinotasikan

A ≡ B ( mod m ) untuk setiap pasangan ( I,j )dengan 1 ≤ i ≤ n dan 1 ≤ j

≤ k.

Contoh :

−

≡

13

34

128

315 (mod 11 ), sebAb 15 ≡ 4 ( mod 11 )

8 ≡ -3 ( mod 11 ) ; 12 ≡ 1 (mod 11 )

Teorema 5 .16 :

Jika A = ( aij ) dan B = ( bij )adalah matriks – matriks berukuran n x k

dengan A ≡ B ( mod m ), C = (cij ) ialah matriks berukuran k xp dan D =

( dij ) ialah matriks berukuran t x n maka AC ≡ BC ( mod m ) dan DA ≡

DB ( mod m ).

Bukti :

Misalkan AC = E = (eij) ialah matriks berukuran n x p dengan e ij =

∑=

k

rrjirca

1dan BC = G =(gij)adalah matriks berukuran n x p dengan gij =

∑=

k

rrjircb

1

Karena A ≡ B (mod m ), maka aij ≡ bij ( mod m ) untuk setiap I dan j

sehingga air crj ≡ bir crj (mod m ) untuk setiap 1≤ r ≤ k .

Akibatnya ∑=

k

rrjir ca

1≡ ∑

=

k

rrjir cb

1( mod m ), yaitu eij ≡ gij (mod m )

Hal ini berarti AC ≡ BC (mod m ).

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

Perhatikan system n perkongruenan linear dengan n variable berikut ini

A11x1 + a12x2 + … + a1nxn ≡ b1(mod m )

A21x1 + a22x2 + … + a2nxn ≡b2 (mod m )

. . .

. . .

. . .

An1x1 + an2x2 + … + annxn ≡ bn (mod m )

Dengan menggunakan notasi matriks system perkongruenan linear ini

dapat dinyatakan sebagai perkongruenan matriks AX ≡ B (mod m )

dengan :

=

=

=

nnnmnn

n

n

b

b

b

danB

x

x

x

X

aaa

aaa

aaa

A......

,

...

............

...

...

2

1

2

1

21

22221

11211

Contoh :

Sistem perkongruenan linera berikut ini

3x + 4y ≡ 5 (mod 13 )

2x + 5y ≡ 7 (mod 13 )

Dapat ditulis sebagai )13(mod7

5

52

43

=

y

x

Selanjutnya kita akan mengembangkan metode penyelesain

perkongruenan dalam bentuk matriks AX≡B(mod m ).

Metode ini menggunakan matriks A -1, ayaitu invers matriks A terhadap

perkalian, sedemikian hingga

A -1.A≡ I (mod m ), dengan I ialah matriks identitas terhadap perkalian.

Definisi 5.5 :

Jika A dan A -1 adalah matriks – mastriks berukuran n x n yang elemen –

elemen nya bilangan bulat sedemikian hingga A.A -1≡ A -1A ≡ I ( mod

m ), dengan I ialah matriks identitas berukuran n, maka A -1 disebut

invers dari A modulo m.

Jika A -1 adalah invers dari A dan B ≡ A -1 (mod m ), maka B juga

invers dari A. Hal ini mengikuti teorema 5.16, karena BA ≡ A -1.A ≡ I

(mod m ). Sebaliknya jika B1 dan B2 masing – masing invers dari A,

maka B1 ≡ B2 (mod m ). Untuk menunjukkan hal ini, kita gunakan

teorema 5.16, dari kekongruenan B1A ≡ B2A ≡ I (mod m ), kita

mempunyai B1AB1 ≡ B2AB1 ( mod m ). Karena AB1 ≡ I(mod m ), kita

dapat menyimpulkan B1≡B2 (mod m ).

Contoh :

=

1610

106

21

43

42

31≡

10

01(mod 5 ) dan

=

115

2511

42

31

21

43≡

10

01(mod 5 )

Tampak disini bahwa matriks

21

43adalah invers dari

42

31(mod 5 )

Teorema 5.17:

Misalkan A =

dc

baadalah matriks yang elemennya bilangan – bilangan

bulat, sedemikian hingga det.A = ∆ = ad – bc prima relative terhadap

bilangan bulat positif. Maka A -1 =∆ -1

−

−ac

bd

Adalah invers dari A modulo m .

Untuk membuktikan teorema ini kita cukup memeriksa kebenaran dari

A.A -1 ≡ A -1.A ≡ I (mod m )

Contoh :

Diketahui A = ,52

43

maka det A = 3.5 – 4.2 =7.

Invers dari 7 ( mod 13 ) adalah 2, sehingga A -1 ≡ 2

−

−32

45≡

−

−64

810≡

69

510(mod 13 )

Untuk mencari rumus invers dari matriks persegi berukuran lebih dari

dua, kita memerlukan beberpa konsep dalam aljabar linerar, khususnya

pengertian adjoint suatu matriks yang didefinisikan sebagai berikut.

Definisi 5.6 :

Misalkan A suatu matriks persegi berukuran n. adjoint dari A diberi

symbol Adj.(A) adalah suatu matriks persegi berukuran n yang elemen

pada baris ke I kolom ke j ialah d ij, dengan d ij = (-1) i+j dan determinan

matriks yang diperoleh dari A dengan menghapus semua elemen pada

baris ke i kolom ke j.

Teorema 5.18:

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

(det A ) I .

Denngan menggunakan teorema ini kita segera akan mendapatkan

rumus invers suatu matriks persegi, seperti yang dinyatakan dalam

teorema ini.

Teorema 5 . 19:

Jika A suatu matriks persegi yang elemen – elemennya bilangan bulat

dan n suatu bilangan positif sedemikian hingga ( ∆,m ) = 1, maka invers

dari A modulo m adalah A -1 = ∆ -1 Adj.(A).

Bukti :

Karena( ∆,m ) = 1, maka ∆ -1 ada. Dan karena ∆ ≠ 0 maka A.Adj.(A) =

∆.I sehingga

A ∆ -1.Adj.(A) ≡ ∆.∆ -1.I ≡ I(mod m )

∆ -1.Adj.(A).A≡ ∆.∆ -1.I ≡ I(mod m )

Ini menunjukkan bahwa A -1 = ∆ -1.Adj.(A) adalah invers dari A

modulo m

Contoh :

Carilah invers dari A =

321

102

652

(mod 7 )

Jawab :

Det.A = ∆ = -5 ≡ 2 (mod 7 ), maka ∆ -1 = 4. Sehingga A -1 = ∆ -1.Adj.(A)

= 4

−−

−−

1014

1005

532

=

−−

−−

40416

40020

20128

≡

242

501

626

(mod 7 )

Selanjutnya kita dapat menggunakan invers dari A modulo m untuk

menyelesaikan perkongruenan

AX ≡ B (mod m ), dengan syarat ( Det.A,m )= 1, yaitu mengalikan

kedua ruas dari pengkongruenan tersebut dengan A -1, sehingga

diperoleh X ≡ A -1B ( mod m ). Cara ini memberikan cara lain untuk

menyelesaikan system dua pengkongruenan linear dengan dua variable

yang dinyatakan dalam teorema 5 .15.

Contoh :

Carilah penyelesaian dari system perkongruenan berikut ini:

2x + 5y + 6z ≡ 3 (mod 7 )

2x + z ≡ 4 (mod 7 )

X + 2y + 3z ≡ 1 (mod 7)

Jawab :

System perkongruenan ini dapat dinyatakan dalam bentuk

perkongruenan matriks

≡

1

4

3

321

102

652

z

y

x

(mod 7 )

Pada contoh di atas invers dari

321

102

652

(mod 7 ) adalah

242

501

626

,

sehingga diperoleh

≡

=

=

3

1

4

24

8

32

1

4

3

.

242

501

626

z

y

x

(mod 7 )