Perkongruenan Linier

Hallo sobat Mathematics, kali ini saya akan membahas tentang materi Perkongruenan. ini adalah lanjutan dari postingan saya sebelumnya, agar kalian lebih paham alangkah baiknya melihatnya terlebih dahulu postingan saya sebelumnya.

Semoga bermanfaat and enjoyyy

Teorema 5.12

Jika (a, m) = d dan d | b maka perkongruenan linear ax ≡ b (mod m) memiliki tepat d solusi

Bukti :

 Pengkongruenan linier memiliki d solusi.

(a,m) = d, berarti ada a' dan m'  sehingga

a = da'  dan m = dm' 

d │b berarti ada b'  sehingga b = db' 

sehingga dari ax ≡ b (mod m) memberikan

                    da' x ≡ db'  (mod dm' ) atau

                      a' x ≡ b'  (mod m' ).

Dari (a,m) = d memberikan (da' , dm) = d atau (a' ,m' ) = 1. Menurut teorema 5.11. Jika (a' , m' ) = 1, mka a' x ≡ b'  (mod m' ) memiliki satu solusi. Misalkan solusi itu r, maka d buah bilangan, yaitu r, r + m' , r + 2m' , ..., r + (d - 1) m'  atau e + km'  untuk k = 0, 1, 2, 3, ..., (d -1) semuanya adalah solusi dari perkongruenan ax ≡ b (mod m). Hal ini ditunjukkan demikian.

Pertama setiap r + km'  dengan k = 0, 1, 2, 3, ..., (d - 1) memenuhi perkongruenan ax ≡ b (mod m).

ax = a (r + km' ) = da'  (r + km' )

     = da' r + da'  km' 

     = a' rd + a'  km'  d

Karena a¢r ≡ b¢ (mod m¢) dan m¢d = m, maka

ax ≡ a¢rd + a¢ km¢ d (mod m)

     ≡ b¢ d + a¢ km (mod m)

     ≡ b¢ d (mod m)

ax ≡ b (mod m) karena  b = b¢ d

Jadi, r + km¢ untuk k = 0, 1, 2, 3, ..., (d - 1) memenuhi perogruenan ax ≡ b (mod m).

Kedua, setiap r + km¢ dengan k = 0, 1, 2, 3, ..., (d - 1) adalah residu terkecil modulo m. Ditunjukkan demikian

     r adalah solusi dari a¢x ≡ b¢ (mod m) berarti r ≥ 0 sehingga 0 ≤ r + km¢

     r + km¢ ≤ r + (d - 1) m¢ untuk setiap k = 0, 1, 2, 3, ..., (d - 1)

     r + (d - 1) m¢ < m¢ + (d - 1) m¢

                                m + (d - 1) m¢ = dm¢ = m

Jadi, 0 ≤ r + km¢ < 1.

Ini mengatakan bahwa r + km¢ untuk k = 0, 1, 2, 3, ..., (d - 1) adalah residu-residu terkecil modulo m.

Ketiga, tak ada dua bilangan di antara r + km¢ untuk k = 0, 1, 2, 3, ..., (d - 1) yang kongruen modulo m, sebab r + km¢ untuk k = 0, 1, 2, 3, ..., (d - 1) adalah residu-residu terkecil modulo m yang berbeda

Teorema 5.13

Persamaan linear diophantus a’x + b’y = c’ yang diperoleh dari ax + by = c  dengan a’ = a : (a , b), b’ = b : (a , b), c’ = c : (a , b) mempunyai suatu penyelesaian (solusi)  x = r dan y = s, maka himpunan semua penyelesaian dari ax + by = c adalah {(x, y) │ x ≡ r + b’t, y ≡ s – a’t dan t bilangan bulat}.

Teorema 5.14

Sistem perkongruenan linier x ≡ a1 (mod mi), i = 1, 2, 3, ..., k dengan (mi, mj) = 1 untuk setiap i ≠ j memiliki solusi bersama modulo m dan solusi bersama itu tunggal dengan m = m1,m2,m3,.....mk

Bukti :

Sistem perkongruenan linier x ≡ a1 (mod mi) untuk i = 1, 2, 3, ..., t mempunyai solusi bersama modulo (m1, m2, ..., mt).

Pembuktian dengan induksi matematika untuk bilangan asli k.

Untuk k = 1 berarti x ≡ a1 (mod m1) jelas mempunyai solusi.

Untuk k = 2, yaitu sistem perkongruenan x ≡ a1n(mod m) dan x ≡ a2 (mod m2) dengan (m1, m2) = 1.

x ≡ a1 (mod m1) berarti x = a1 + k1 m1 untuk suatu bilangan bulat k1.

Sehingga a1 + k1 m1 ≡ a2 (mod m2)

                 k1 m1 ≡ a2 ­- a1 (mod m2) dengan k1 suatu variabel.

     Karena (m1, m2) = 1 maka perkongruenan terakhir ini mempunyai satu solusi untuk k1 modulo m2, katakanlah t, maka k1 = t + k2 m2  untuk suatu k2 memenuhi perkongruenan terakhir itu.

Jadi x = a1 + k1 m1 = a1 + (t + k2 m2) m1

       x = (a1 + tm1) + k2 m1 m2

Ini berarti x ≡ (a1 + tm1)(mod m1 m2).

     Perkongruenan ini memenuhi perkongruenan untuk k = 2. Sekarang, sebagai hipotesis diambil bahwa sistem perkongruenan linier x ≡ a1 (mod m1) mempunyai satu solusi bersama untuk i = 1, 2, 3, ..., (r - 1).

    Misalkan solusi bersama itu    s, maka sistem x ≡ a1 (mod m1), i = 1, 2, 3, ..., (r - 1) dapat dinyatakan sebagai suatu perkongruenan, yaitu :

     x ≡ s (mod m1, m2, m3, ..., mr - 1)

Sehingga r perkongruenan itu dapat dinyatakan sebagai dua perkongruenan yaitu :

   x = s (mod m1, m2, m3, ..., mr - 1)

   x = ar (mod mr)

Sistem perkongruenan dari dua perkongruenan ini mempunyai solusi bersama mod (m1, m2, m3, ..., mr - 1, mr) = 1 sebab mi dan mj saling prima untuk i ≠ j.



Postingan sebelumnya
https://nurainynovitasari.blogspot.com/2019/07/perkongruenan-linear.html