Sistem Perkongruenan Linier Satu Variabel

1. Apa itu Sistem Perkongruenan Linier?

Sistem perkongruenan linier terdiri dari beberapa perkongruenan linier yang melibatkan variabel yang sama dan yang mempunyai bilangan modulo sama. Masalah yang penyelesaiannya menggunakan sistem perkongruenan ini telah muncul dalam suatu tulisan bangsa Cina kuno.

2. Teorema Sisa Cina (Chinese Remainder Theorem)

Misalkan m₁ , m₂ , … , m_r​ adalah bilangan bulat positif selain 1 yang saling relatif prima. Untuk setiap bilangan bulat a₁ , a₂ , … , a_r sistem kongruensi linear

​mempunyai solusi, dan tiap dua solusi kongruen modulo m = m₁ × m₂ × … × m_r​.

Bukti:

Misalkan m = m₁ × m₂ × … × m_r​ dan y_j​ menyatakan hasil bagi antara m dengan m_j​. Dengan kata lain, y_j merupakan hasil kali semua modus selain m_j.

Karena m₁, m₂​, …, m_r​ saling relatif prima, maka y_j dan m_j juga relatif prima. Akibatnya, terdapat bilangan bulat z_j sedemikian sehingga

y_j z_j  ​≡ 1 (mod m_j​), j = 1, 2, …, r

Kita akan menunjukkan bahwa nilai X₀ berikut merupakan solusi dari sistem kongruensi semula.

X₀ ​= a₁​ y₁​ z₁ ​+ a₂​ y₂ ​z₂​+ … + a_r y_r z_r​

Untuk i = 1, 2, …, r diperoleh

X₀ ​ ≡ (a₁ y₁ z₁ + … + a_i y_i z_i + … + a_r y_r z_r) (mod m_i)

Perhatikan bahwa y_j ≡ 0 (mod m_i​) untuk j ≠ i, sehingga a_j y_j z_j​ ≡ 0 (mod m_i​). Akibatnya

X₀ ≡ a_i y_i z_i(mod m_i)

Karena y_i z_i​ ≡ 1 (mod m_i​) maka diperoleh

X₀ ​​ ≡ a_i y_i​ z_i ​(mod m_i)

     ≡ a_i​ ⋅ 1 (mod m_i)

     ≡ a_i ​(mod m_i)​

Karena i = 1, 2, …, r maka dapat disimpulkan bahwa x₀​ memenuhi setiap kongruensi pada sistem semula. Dengan ini, terbukti bahwa sistem kongruensi tersebut mempunyai solusi.

Berikutnya, akan ditunjukkan bahwa tiap dua solusi kongruen modulo m. Misalkan x₁​ adalah solusi lain dari sistem tersebut. Untuk i = 1, 2, …, r diperoleh

                                                      X₀​ ≡ a_i​ (mod m_i​) dan x₁ ​ ≡ a_i (mod m_i)

sehingga x₀ ≡ x₁ ​(mod mi​). Hal ini berakibat

                                       x₀ ≡ x₁ (mod KPK(m₁, m₂​, …, m_r))

Karena m₁​, m₂, …, m_r​ saling relatif prima, maka nilai KPK sama dengan hasil kalinya, yaitu m. Dengan demikian, x₀ ​≡ x₁​(mod m). ∎

3. Langkah-Langkah Menyelesaikan Sistem Perkongruenan Linier

Tentukan bilangan bulat yang bersisa 3 jika dibagi 4, bersisa 1 jika dibagi 5, dan bersisa 1 jika dibagi 6.

Terbentuk sistem perkongruenan linier berikut:

x ≡ 3 (mod 4) → x = 3 + 4k₁ (i)

x ≡ 1 (mod 5) → x = 1 + 5k₂ (ii)

x ≡ 1 (mod 6) → x = 1 + 6k₃ (iii)

Substitusikan nilai x pada persamaan (i) dalam perkongruenan (ii), dengan k₁, k₂, k₃ bilangan bulat, diperoleh:

x = 3 + 4k₁ ∧ x ≡ 1 (mod 5) → 3 + 4k₁ ≡ 1 (mod 5) 

4k₁ ≡ 1 − 3 (mod 5) 

4k₁ ≡ −2 (mod 5)

4k₁ ≡ 8 (mod 5)

k₁ ≡ 2 (mod 5) → k₁ = 5k₂ + 2 (iv)

Dari (i) dan (iv) x = 3 + 4k₁ ∧ k₁ = 5k₂ + 2 diperoleh x = 3 + 4.(5k₂ + 2) = 11 + 20k₂ (v)

Substitusikan nilai x pada persamaan (v) dalam perkongruenan (iii) diperoleh:

x = 11 + 20k₂ ∧ x ≡ 1 (mod 6) → 11 + 20k₂ ≡ 1 (mod 6)

20k₂ ≡ 1 − 11 (mod 6)

20k₂ ≡ −10 (mod 6), karena (20, 6) = 2 | (−10), dapat disederhanakan

10k₂ ≡ −5 (mod 3)

10k₂ ≡ 10 (mod 3), karena (10, 3) = 1

k₂ ≡ 1 (mod 3)

k₂ ≡ 1 (mod 3) → k₂ = 1 + 3k₃ (vi)

Dari (v) dan (vi) x = 11 + 20k₂ ∧ k₂ = 1 + 3k₃ diperoleh x = 11 + 20(1 + 3k₃)

x = 11 + 20 + 60k₃ 

x = 31 + 60k₃ 

Dkl x ≡ 31 (mod 60)

Penyelesaian umum dari sistem perkongrueanan di atas adalah 31

4. Cara Penyelesaian Khusus untuk Saling Koprim Sepasang-Sepasang

Sistem perkongruenan linier x ≡ a_i (mod m_i), i = 1, 2, 3, …, k dengan (m_i, m_j) = 1 untuk setiap i ≠ j memiliki solusi bersama modulo m dan solusi bersama itu tunggal, dengan m = m₁.m₂.m₃…m_k.

Catatan : 

(m_i, m_j) = 1 untuk setiap i ≠ j dengan i, j = 1, 2, 3, …, k dikatakan bahwa m₁, m₂, m₃, …, m_k saling prima sepasang-sepasang.

Untuk mendapatkan penyelesaian bersama dari sistem perkongruenan linier yaitu:

Misalkan sistem berbentuk :  

x ≡ a_i (mod m_i), untuk i = 1, 2, 3, …, k  dengan (m_i, m_j) = 1 untuk i ≠ j dapat kita kerjakan sebagai berikut:

M_i = m/m_i = (m₁.m₂.m₃…m_k)/m_i untuk i = 1, 2, 3, …, k

s_i adalah penyelesaian dari M_ix ≡ 1 (mod m_i), untuk i = 1, 2, 3, …, k

Maka:

s = a₁s₁M₁ + a₂s₂M₂ + … + a_ks_kM_k memenuhi x ≡ a_i (mod m_i)

Sehingga solusi bersama dari sistem perkongruen x ≡ a_i (mod m_i) adalah solusi dari x ≡ s (mod m₁.m₂.m₃…m_k)

Contoh:

Tentukan solusi dari sistem perkongruenan berikut:

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 1 (mod 4)

Penyelesaian:

Dari teorema x ≡ a_i (mod m_i) dan soal di atas diketahui bahwa : 

a₁ = 2 , m₁ = 3 

a₂ = 3, m₂ = 5 

a₃ = 1, m₃ = 4 

Selanjutnya, diperoleh: 

M₁ = 5 . 4 = 20 sehingga 20x ≡ 1(mod 3)  atau x ≡ 2(mod 3)

M₂ = 3 . 4 = 12 sehingga 12x ≡ 1(mod 5)  atau x ≡ 3(mod 5)

M₃ = 3 . 5 = 15 sehingga 15x ≡ 1(mod 4)  atau x ≡ 3(mod 4)

Sehingga, diperoleh: 

Hal ini berarti , s₁ = 2, s₂ = 3 dan s₃ =3, maka :

s =  a₁s₁ M₁ + a₂s₂M₂ + a₃s₃M₃

  = 2.2.20 + 3.3.12 + 1.3.15 = 80 + 108 + 45

  = 233

Sehingga: x ≡ 233 (mod 3.5.4) ↔ x ≡ 233(mod 60)

x ≡ 53(mod 60)