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 )
Top Related