Sistem Kongruensi Linier

Kita akan mempertimbangkan sistem dengan lebih dari satu kongruensi yang melibatkan jumlah
variabel yang sama sebagai kongruensi, di mana semua kongruensi memiliki modulus yang
sama.
Misalkan kita ingin menemukan semua bilangan bulat x dan y sehingga kedua kongruensi
3 x+ 4 y ≡5 (mod 13)

2 x+5 y ≡7 (mod 13)

terpenuhi. Untuk mencoba menghilangkan y , kita kalikan kongruensi pertama dengan5 dan
kedua dengan4 , untuk memperoleh
15 x+ 20 y ≡ 25(mod 13)

8 x +20 y ≡ 28(mod 13).

Kita kurangi kongruensi kedua dari yang pertama, untuk menemukan bahwa
7 x ≡−3(mod 13).

Karena 2 adalah invers dari 7(mod 13), kita kalikan kedua sisi kongruensi di atas dengan 2.
Hasilnya adalah
2 ·7 x ≡2 ·−3(mod 13),

yang memberi tahu kita bahwa

x ≡ 7(mod 13).

Demikian pula, untuk menghilangkan x , kita dapat mengalikan kongruensi pertama dengan 2 dan
yang kedua dengan3 (dari sistem asli), untuk melihat bahwa
6 x +8 y ≡ 10(mod 13)

6 x +15 y ≡ 21(mod 13).

Ketika kita mengurangi kongruensi pertama dari yang kedua, kita memperoleh
7 y ≡11(mod 13).

Untuk menyelesaikan y , kita kalikan kedua sisi kongruensi ini dengan 2 , invers dari 7 modulo 13
. Kita peroleh
2 ·7 y ≡2 · 11(mod 13) ,

sehingga
y ≡9 (mod 13).
Yang telah kami tunjukkan adalah bahwa solusi apa pun (x , y ) harus memenuhi

x ≡ 7(mod 13), y ≡9 (mod 13).

Ketika kita memasukkan kongruensi ini untuk x dan y ke dalam sistem asli, kita melihat bahwa
pasangan ini sebenarnya adalah solusi:
3 x+ 4 y ≡3 · 7+ 4 · 9≡ 57 ≡5(mod 13)

2 x+5 y ≡2 · 7+5 · 9≡ 59≡ 7(mod 13).

Oleh karena itu, solusi dari sistem kongruensi ini adalah semua pasangan (x , y )sehingga
x ≡ 7(mod 13)dan y ≡9 (mod 13).

Sekarang kita memberikan hasil umum mengenai sistem tertentu dari dua kongruensi dalam dua
yang tidak diketahui. (Hasil ini menyerupai aturan Cramer untuk menyelesaikan sistem
persamaan linear.)
Teorema 4.16.

Misalkan a , b , c , d ,e , f , dan m adalah bilangan bulat dengan m>0, dan ( ∆ ,m )=1 ,di mana
∆ ¿ ad−bc. Maka sistem kongruensi

ax +by ≡ e(mod m)

cx +dy ≡ f (mod m)

memiliki solusi unik modulo m , yang diberikan oleh

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

y ≡ ∆(af −ce)(mod m),

di mana ∆ adalah invers dari ∆ modulo m .

Pembuktian Untuk menghilangkan y , kita kalikan kongruensi pertama sistem dengand dan yang
kedua dengan b , untuk memperoleh
adx +bdy ≡de (mod m)

bcx +bdy ≡bf (mod m).

Kemudian kita kurangi kongruensi kedua dari yang pertama, untuk menemukan bahwa
(ad −bc) x ≡ de−bf (mod m),

atau, karena ∆ ¿ ad−bc ,

∆ x ≡de−bf (mod m).
Selanjutnya, kita kalikan kedua sisi kongruensi ini dengan ∆ . invers dari ∆ modulo m , untuk
menyimpulkan bahwa
x ≡ ∆ (de−bf )(mod m).

Dengan cara yang sama, untuk menghilangkan x , kita kalikan kongruensi pertama dengan c dan
yang kedua dengan a , untuk memperoleh
acx +bcy ≡ ce(mod m)

acx + ady ≡ af (mod m).

Kita kurangi kongruensi pertama dari yang kedua, untuk menemukan bahwa
(ad −bc) y ≡ af −ce (mod m)

atau
∆ y ≡ af −ce (mod m).

Terakhir, kita kalikan kedua sisi kongruensi ini dengan ∆ untuk melihat bahwa
y ≡ ∆(af −ce)(mod m).

Kita telah menunjukkan bahwa jika (x , y ) adalah solusi dari sistem kongruensi, maka

x ≡ ∆ (de−bf )(mod m), y=∆(af −ce)(mod m).

Kita dapat dengan mudah memeriksa bahwa setiap pasangan (x , y ) adalah solusi. Ketika
x ≡ ∆ (de−bf )(mod m)dan y ≡ ∆(af −ce )(mod m), kita memiliki

ax +by ≡ a ∆(de−bf )+ b ∆(af −ce )

≡ ∆ ( ade – abf +abf – bce )

≡ ∆(ad−bc)e
≡∆∆e

≡ e(mod m),

dan
cx +dy ≡ c ∆ ( de−bf ) +d ∆(af −ce)

≡ ∆(cde−bcf +adf −cde)

≡ ∆(ad−bc) f
≡∆∆ f
 ≡ f (mod m).

Ini menetapkan teorema.

Dengan metode yang sama, kita dapat memecahkan sistem n kongruensi yang melibatkan
n variabel yang tidak diketahui. Akan tetapi, kita akan mengembangkan teori penyelesaian sistem
tersebut, serta sistem yang lebih besar, dengan metode yang diambil dari aljabar linier.
Sistem n kongruensi linier yang melibatkan n variabel tak dikenal akan muncul dalam
studi kriptografi kita berikutnya. Untuk mempelajari sistem tersebut ketika n besar, akan
membantu untuk menggunakan bahasa matriks. Kita akan menggunakan beberapa pengertian
dasar aritmatika matriks, yang dibahas dalam sebagian besar teks aljabar linier.
Sebelum kita melanjutkan, kita perlu mendefinisikan kongruensi matriks.

Definisi. Misalkan A dan B adalah matriks n × k dengan entri integer, dengan entri (i , j)th a ij

dan b ij, masing-masing. Kita katakan bahwa A kongruen dengan B modulo m jika a ij ≡ b ij
(mod m) untuk semua pasangan (i , j) dengan 1 ≤i ≤ n dan 1 ≤ j≤ k . Kita tulis A≡ B (mod m) jika
A kongruen dengan B modulo m .

Kekongruenan matriks A ≡ B(mod m) menyediakan cara ringkas untuk menyatakan

nk kongruen a ij ≡ b ij (mod m) untuk 1 ≤i ≤ n dan 1 ≤ j≤ k

Contoh 4.24.

(58 123 )≡ (−34 31)(mod 11).

Proposisi berikut akan dibutuhkan.
Teorema 4.17.

Jika A dan B adalah matriks n × k dengan A ≡ B (mod m) ,C adalah matriks k × p , dan D adalah
adalah matriks p ×n , semuanya dengan entri integer, maka AC ≡ BC (mod m)dan
DA ≡ DB (mod m) .

Pembuktian.

Misalkan masukkan A dan Badalah a ij dan b ij, masing-masing, untuk 1 ≤i ≤ n dan 1 ≤ j≤ k , dan
misalkan masukkan C adalah c ij untuk 1 ≤i ≤ k dan 1 ≤ j≤ p. Masukkan (i , j)dari AC dan BC
 k k
adalah ∑ a¿ c tj dan ∑ b¿ c ij masing-masing, untuk 1 ≤i ≤ n dan 1 ≤ j≤ p. Karena A ≡ B( mod m),
t =1 t =1
kita tahu bahwa a ¿ ≡ b ¿ (mod m)untuk semua i dan k . Oleh karena itu, berdasarkan Teorema 4.4,
k k
kita melihat bahwa ∑ a¿ c tj ≡ ∑ b¿ ctj (mod m). Akibatnya, AC ≡ BC (mod m).
t =1 t =1

Pembuktian bahwa DA ≡ DB (mod m) serupa dan dihilangkan.

Sekarang mari kita pertimbangkan sistem kongruensi

a 11 x 1 +a 12 x 2+· ··+ a1 n x n ≡b 1(mod m)

a 21 x 1+ a22 x 2 +·· ·+a2 n x n ≡ b2 (mod m)

a n 1 x 1+ an 2 x 2 +· ··+ ann x n ≡b n(mod m).

Dengan menggunakan notasi matriks, kita melihat bahwa sistem n kongruensi ini setara dengan

kongruensi matriks AX ≡ B(mod m), di mana

( ) () ()
a 11 a12 … a1 n x1 b1
x2 b
A= a 21 a 22 … a2 n , X = , dan B= 2
⋱ ⋮ ⋮
an 1 an 2 … ann an bn

Contoh 4.25.
Sistem
3 x+ 4 y ≡5 (mod 13)

2 x+5 y ≡7 (mod 13)

dapat ditulis sebagai

(32 45 )( xy) ≡ (57)(mod 13).

Sekarang kita kembangkan sebuah metode untuk menyelesaikan kongruensi berbentuk
AX ≡ B(mod m) .

Metode ini didasarkan pada pencarian matriks A sedemikian sehingga A A ≡ I (mod m), di mana
I adalah
matriks identitas.
Definisi. Jika A dan A adalah matriks bilangan bulat yang berordo n × n dan A A ≡ A A ≡ I (mod m)

( )
1 0 … 0
0 1 … 0
dimana I = adalah matriks identitas berordo n, maka A dikatakan sebagai invers dari
⋮ ⋮ ⋱ ⋮
0 0 … 1
A modulo m.

Jika A adalah invers dari A dan B≡ A(mod m) , maka B juga merupakan invers dari A .
Hal ini mengikuti dari Teorema 4.17, karena BA ≡ A A ≡ I (mod m). Sebaliknya, jika B1 dan B2
keduanya adalah invers dari A , maka B1 ≡ B 2 ( mod m ) . Untuk melihat ini, gunakan Teorema 4.17 dan
kongruensi B1 A ≡ B2 A ≡ I (mod m), kita punya B1 A B1 ≡ B 2 A B2 ( mod m ) . Karena
A B1 ≡ I ( mod m ), kita simpulkan bahwa B1 ≡ B 2(mod m) .

Contoh 4.26
Diketahui bahwa

(12 34)( 31 42)=(106 1610)=( 10 01)(mod 5)

dan

(31 42 )(12 34)=(115 2511 )=( 10 01)(mod 5)

maka terlihat bahwa matriks (31 42 ) adalah inverse dari (12 34) modulo 5.
Teorema 4.18.
Misalkan

A= ( ac bd)
adalah matriks bilangan bulat, sehingga ∆=det A=ad−bc relatif prima terhadap bilangan bulat
positif m. Maka matriks
 A=∆ (−cd −b
a )
di mana ∆ adalah invers dari ∆ modulo m, merupakan inverse dari A modulo m.

Pembuktian.

Untuk memverifikasi bahwa matriks A adalah inverse dari A modulo m, kita hanya perlu
membuktikan bahwa A A ≡ A A ≡ I (mod m).

Untuk melihat hal ini, perhatikan bahwa:

A A≡ (ac bd ) ∆ (−cd −b
a ) (
≡∆
ad−bc
0
0
−bc +ad )
≡∆ ( ∆0 ∆0 )≡ ( ∆0∆ 0
∆∆ )( )
≡
1 0
0 1
= I (mod m).

dan

A A≡∆ (−cd )( ) (
−b a b
a c d
≡∆
ad−bc
0
0
−bc +ad )
≡∆ ( ∆0 ∆0 )≡ ( ∆0∆ 0
∆∆
≡)( )
1 0
0 1
= I ≡.

di mana ∆ adalah invers dari ∆ modulo m, yang ada karena (∆ ,m ¿=1.

Contoh 4.27

Misalkan A= (12 34). Karena 2 adalah invers dari det A=7 modulo 13, maka kita punya:
A=2 (−25 −4
3)(
≡
10 −8
−4 6
≡
10 5
9 6)(
(mod 13))
Untuk memberikan rumus invers dari matriks n x n, di mana n adalah bilangan bulat positif yang
lebih besar dari 2, kita memerlukan hasil dari aljabar linier. Hal ini melibatkan gagasan tentang
adjoint dari sebuah matriks, yang didefinisikan sebagai berikut.
Definisi. Adjoin dari matriks n×n, A, adalah matriks n×n dengan entri (i, j), C ij, di mana
i+ j
C ij =(−1) dikalikan determinan dari submatriks hasil menghapus baris ke-i dan kolom ke-j dari A.
Adjoin A dilambangkan sebagai adj A.

Teorema 4.19

Jika A adalah matriks n×n dan det A ≠ 0, maka A ( adj A )=¿, di mana adj A adalah adjoin dari A.

Dengan menggunakan teorema ini, teorema berikut ini dapat dengan mudah diikuti.
Teorema 4.20
Jika A adalah matriks n×n dengan entri bilangan bulat, dan m adalah bilangan bulat positif
sedemikian hingga maka ( det A , m) =1, maka matriks

A=∆ ( adj A )

adalah invers dari modulo m, di mana ∆ sebagai invers dari

∆=det A modulo m

Pembuktian.

Jika ( det A , m) =1, maka kita tahu bahwa det A ≠ 0. Oleh karena itu, dari Teorema 4.19 kita punya:

A(adj A)=¿

Karena ( det A , m) =1, maka ada invers ∆ dari ∆ modulo m. oleh karena itu,

A ( ∆ adj A ) ≡ A . ( adj A ) ∆ ≡ ∆ ∆ I ≡ I (mod m) ,

dan

∆ ( adj A ) A ≡ ∆( ( adj A ) A)≡∆ ∆ I ≡ I (mod m),

Hal ini menunjukkan bahwa A=∆ ( adj A ) adalah invers dari A modulo m.
Contoh 4.28
Misalkan

( )
2 5 6
2 0 1
1 2 3

Maka det A = -5. Selanjutnya, kita memiliki ( det A ,7 )=1, dan kita melihat bahwa 4 adalah kebalikan
dari det A= -5 (mod 7). Akibatnya, kita menemukan bahwa

( )( )( )
−2 −3 5 −8 −12 20 6 2 6
A=4 ( adj A )=4 −5 0 10 = −20 0 40 ≡ 1 0 5 (mod 7)
4 1 −10 16 4 −40 2 4 2

Kita dapat menggunakan invers dari A modulo m untuk menyelesaikan sistem

AX ≡ B(mod m)

Di mana (det A, m) = 1. Berdasarkan Teorema 4.17, ketika kita mengalikan kedua sisi dari
kesebangunan ini dengan sebuah invers A dari A, kita mendapatkan:

A( AX )≡ A B(mod m)

( A A) X ≡ A B (mod m)

X ≡ A B(mod m)

Oleh karena itu, kita menemukan solusi X dengan membentuk A B (mod m).

Bukti Alternatif Teorema 4.16

Misalkan AX=B di mana A= ( ac bd), X =( xy), dan B=(ef). Jika ∆=det A=ad−bc relatif prima
terhadap m, maka
 ( xy )= X ≡ A B ≡ ∆ (−cd )( ) (
−b e
a f
=∆
de−bf
af −ce )
(mod m)

Sehingga (x,y) adalah solusi jika dan hanya jika:

x ≡ ∆ ( de−bf ) , y =∆ ( af −ce ) (mod m)

Contoh 4.28
Sistem 3 kongruensi:
2 x1 +5 x 2+ 6 x3 ≡3 (mod 7)

2 x1 + x 3 ≡4 (mod 7)

x 1+ 2 x 2 +3 x3 ≡1(mod 7)

Ini kongruen dengan matriks

( )( ) ( )
2 5 6 x1 3
2 0 1 x 2 ≡ 4 (mod 7)
1 2 3 x3 1

( ) ( )
6 2 6 2 5 6
Sebelumnya telah ditunjukkan bahwa matriks 1 0 5 adalah invers dari 2 0 1 ( mod 7 ) .
2 4 2 1 2 3

Sehingga:

( ) ( )( ) ( ) ( )
x1 6 2 6 3 32 4
x 2 = 1 0 5 4 = 8 ≡ 1 (mod 7)
x3 2 4 2 1 24 3

.
Berdasarkan Teorema 4.16,
Berikut soal tidak relatif prima
4 x+ 6 y ≡ 2(mod 10)

2 x+ 4 y ≡6 (mod 10)
Selanjutnya eliminasi dengan mengalikan 2

(2) 2 x+ 4 y ≡2(6)(mod 10)

4 x+ 8 y ≡12(mod 10) ≫ 4 x +8 y ≡2( mod 10)

Bandingkan dengan (1)

4 x+ 6 y ≡ 2(mod 10)

Kurangkan:
( 4 x+ 8 y )−( 4 x +6 y )=2 y ≡ 0(mod 10)

y ≡0(mod 10)

Subsitusi nilai y

Ambil y=0, seubsitusi ke (2):

2 x+ 4 (0)≡ 6(mod 10) ≫ 2 x ≡6 (mod 10)

Bagi 2 kedua sisi:

x ≡ 3(mod 5)

Berarti x ∈ { 3 , 8 ,13 … . } mod 10 , dimana solusi mod 10 : x ≡ 3 , 8(mod 10)

Karena y ≡0 atau y ≡ 5 tidak memiliki solusi unik, tapi solusi tak hingga dalam mod 10