Makalah Perkongruenan Linier dan Aplikasinya

MAKALAH

PERKONGRUENAN LINIER DAN APLIKASINYA

DISUSUN OLEH :

1.      VEBRUANDA WILZANI PUTRI (A1C214017)

2.      INDRIANI SAFITRI                       (A1C2140

3.      DOLY SATRIA B.B                                    (A1C2140

DOSEN PENGAMPU :

Dra. DEWI IRIANI, M.Pd

PROGRAM STUDI PENDIDIKAN MATEMATIKA

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN

UNIVERSITAS JAMBI

2015

KATA PENGANTAR

Alhamdulillah segala puji dan syukur hanya milik Allah SWT, atas limpahan rahmat, taufiq, hidayah dan inayah-Nya lah penulis sampai saat ini masih diberikan bermacam kenikmatan yang tiada ternilai harganya serta Rasul Allah Muhammad SAW pembawa petunjuk bagi umat Islam, hingga penulis dapat menyelesaikan penulisan makalah dengan judul “Perkongruenan Linier dan Aplikasinya”. Makalah ini disusun sebagai salah satu tugas mata kuliah Teori Bilangan.

Kami sebagai penulis sangat menyadari keterbatasan  dan kemampuan yang dimiliki sehingga banyak kendala dan kesulitan yang dihadapi dalam penulisan makalah ini. Namun demikian berkat bimbingan, arahan, dorongan, perhatian, serta bantuan baik moral maupun materil dari berbagai pihak, akhirnya makalah ini dapat diselesaikan. Untuk itu penulis mengucapkan rasa hormat dan terima kasih kepada semua pihak yang telah membantu dalam penulisan makalah ini.

Penulis menyadari bahwa makalah ini masih jauh dari sempurna, oleh karena itu semua kritik dan saran untuk perbaikan dan kemajuan ke depan sangat diharapkan dan diterima oleh penulis. Akhirnya semoga makalah ini dapat memberikan manfaat bagi penulis khususnya dan bagi pembaca umumnya.

Wassalam.

Jambi,     Juni 2015    

Penulis

DAFTAR ISI

KATA PENGANTAR………............................................................................................. 2

DAFTAR ISI........................................................................................................... 3

BAB I

PENDAHULUAN                

A. LATAR BELAKANG........................................................................................ 4

B. RUMUSAN MASALAH................................................................................... 5

C. TUJUAN PENULISAN..................................................................................... 5

D. MANFAAT PENULISAN................................................................................. 5

BAB II

PEMBAHASAN       

1. PERKONGRUENAN LINIER..........................................................................................  6

2. TEOREMA 5.10................................................................................................. 8

3. TEOREMA 5.11................................................................................................. 8

4. TEOREMA 5.12............................................................................................... 10

5. TEOREMA 5.13............................................................................................... 13

6. TEOREMA 5.14............................................................................................... 14

BAB III         

PENUTUP     

A. KESIMPULAN.................................................................................................15

B. SARAN............................................................................................................. 15

DAFTAR PUSTAKA........................................................................................... 16

BAB I. PENDAHULUAN

A.    Latar Belakang Penulisan Makalah

B.     Rumusan Makalah

Makalah tentang PERKONGRUENAN LINIER DAN APLIKASINYA  ini mencakup beberapa permasalahan, yaitu sebagai berikut :

1.      apakah yang dimaksud dengan perkongruenan linier?

2.      bagaimana aplikasi perkongruenan linier?

C.    Tujuan Penulisan

Tujuan penulisan makalah ini adalah :

1.      agar pembaca dapat mengetahui apakah itu perkongruenan linier.

2.      agar pembaca dapat mengetahui bagaimana aplikasi perkongruenan linier.

D.    Manfaat Penulisan

Penulisan makalah ini diharapkan dapat menjadi sumber informasi tambahan bagi pembaca dan bagi mahasiswa Pendidikan Matematika khususnya. Penulis mengharapkan tulisan ini bisa menjadi suatu pemaparan yang dapat menjelaskan tentang perkongruenan linier dan aplikasinya dalam teori bilangan bagi pelajar yang mengalami kesulitan dalam mengerjakan tugas teori bilangan. Penulis juga mengharapkan agar pembaca dapat memahami pentingnya ilmu teori bilangan dalam kehidupan sehari-hari.

BAB II. PERKONGRUENAN LINEAR

Perkongruenan Linear :

·      Merupakan kalimat terbuka yang menggunakan relasi kekongruenan

·      Pangkat tertinggi satu

·      Bentuk Umum : ax ≡ b (mod m), a≠0 (mod m).

Contoh :

• 3x ≡ 4 (mod 5), merupakan perkongruenan linear.
• X⁴ – 5x + 7 ≡ 5 (mod 7),  bukan merupakan pengkoreanan linear.

Untuk perkongruenan linear 3x ≡ 4 (mod 5),

Jika x = 3 maka   :       3.3   ≡  4 (mod 5)

9 ≡ 4 (mod 5), merupakan suatu kalimat pengkongruenan linear yang benar.

Jika  x = -7 maka :       3 (-7) ≡ 4 (mod 5)

   -21 ≡ 4 (mod 5), merupakan suatu kalimat pengkongruenan linear yang benar.

Dan untuk nilai – nilai x yang lainnya, seperti : ......, -12, -7, -2, 3, 8. ....

Karena ax ≡ b (mod m), berarti ax – b = km atau ax = b + km.

            Jadi, perkongruenan linier ax ≡ b (mod m) akan mempunyai solusi atau penyelesaian jika dan hanya jika ada bilangan-bilangan bulat x dan k yang memenuhi persamaan ax = b + km.

            Misalkan r memenuhi perkongruenan linier ax ≡ b (mod m),berarti ar ≡ b (mod m). Maka setiap bilangan bulat ( (r + m), (r + 2m), (r + 3m), ..., (r – m), (r – 2m),...) memenuhi perkongruenan itu sebab,

a(r +km) ≡ ar ≡ b (mod m) untuk setiap bilangan bulat k.

            Diantara bilangan-bilangan bulat ( r + km ) dengan k = 0, 1, 2, 3, ...,-1, -2, -3,... ada tepat satu dan hanya satu katakan s dengan 0 ≤ s < m, sebab suatu bilangan bulat mesti terletak diantara dua kelipatan m yang berurutan.

            Jadi, jika r memenuhi perkongruenan ax ≡ b (mod m) dan km ≤ r < (k+1)m untuk suatu bilangan bulat k, maka 0 ≤ ( r – km) < m.

             Jadi, s = r – km untuk suatu bilangan bulat k.

            Dengan kata lain, s adalah residu terkecil modulo m yang memenuhi perkongruenan ax ≡ b (mod m). Selanjutnya s disebut solusi ( penyelesaian ) dari perkongruenan itu.             

 ax ≡ b (mod m).

Contoh :

Misalkan 2x ≡ 4 (mod 2)

Nilai-nilai x yang memenuhi perkongruenan 2x ≡ 4 (mod 2) ini adalah ..., -19, -12, -5, 2, 9, 16, ... dengan solusi perkongruenan adalah 2. Yaitu residu terkecil modulo 7 yang memenuhi perkongruenan linier 2x ≡ 4 (mod 2).

            Pada persamaan ax = b dengan a ≠ 0 hanya mempunyai satu solusi, tetapi pada perkongruenan linier ax ≡ b (mod m) dapat mempunyai tepat satu solusi, banyak solusi, bahkan ada yang tidak mempunyai solusi.

Contoh :

1.              2x ≡ 1 (mod 4)

Jika 2x ≡ 1 (mod 4) maka 4 │ (2x – 1) tidak mempunyai solusi karena tidak ada suatu bilangan bulat x yang memenuhi 4 │ (2x – 1) berarti 4 │ (2x – 1)

2.             3x ≡ 5 (mod 11)

Jika 3x ≡ 5 (mod 11) maka 11 │ (3x – 5) hanya mempunyai tepat satu solusi yaitu 9

3.             2x ≡ 4 (mod 6)

Jika 2x ≡ 4 (mod 6) maka 6 │ (2x – 4) mempunyai beberapa solusi yaitu yaitu 2 dan 5.

TEOREMA 5. 10

            Jika (a,m) + b maka perkongruenan linier ax ≡ b (mod m) tidak memiliki solusi.

BUKTI : (Pembuktian dengan kontraposisi)

            Misalkan r adalah solusi dari ax ≡ b (mod m) maka ar ≡ b (mod m) sehinggan ar – b = km untuk suatu bilangan bulat k.

            Perhatikan bahwa ar – b = km, (a,m) │a dan (a,m) │b. Terbuktilah kontraposisi dari teorema itu, sehingga terbukti pula teorema itu.

Contoh :

6x ≡ 7 (mod 8) karena ( 6,8 ) = 2 dan 1 + 7  maka pengkongruenan 6x ≡ 7 (mod 8) tidak mempunyai solusi.

TEOREMA 5.11

Jika ( a,m ) = 1, maka ada bilangan bulat r dan s sehingga ar + ms = 1. Jika kedua ruas dari persamaan ini dikalikan b, diperoleh :

(ar) b + (ms) b = b

a (rb) + m (sb) = b

a (rb) – b = -(sb) m

Persamaan terakhir ini berarti  bahwa a (rb) – b adalah kelipatan m.

            Jadi, a (rb) = b (mod m)

Maka residu terkecil dari rb modulo m adalah solusi dari perkongruenan linier itu. Sekarang tinggal menunjukkan bahwa solusi itu tunggal.

            Andaikan solusi perkongruenan linier itu tidak tunggal, misalkan dan masing-masing solusi dari ax ≡ b (mod m), maka

            ar ≡ b (mod m) dan as ≡ b (mod m)

Dengan sifat transitif diperoleh bahwa

            ar ≡ as (mod m). Karena (a,m) = 1, maka

            r ≡ s (mod m). Ini berarti m │(r – s)

            Tetapi karena r dans adalah solusi dari perkongruenan itu, maka r dan s masing-masing residu terkecil modulo m, sehingga

            0 ≤ r < m dan 0 ≤ s < m

            Dari kedua ketidaksamaan ini diperoleh bahwa -m < r - s < m, tetapi karena m │(r - s) maka r - s = 0 atau r = s. Ini berarti bahwa solusi dari perkongruenan linier tunggal (terbukti).

            Salah satu cara menyelesaikan perkongruenan linier adalah memanipulasi koefisien atau konstan pada perkongruenan itu, sehingga memungkinkan kita untuk melakukan konselasi (penghapusan).

Contoh :

1.         4x ≡ 1 ( mod 15 )

            4x ≡ 16 ( mod 15 )

              x ≡ 4 ( mod 15 )

             x  = 4 + 15 k  untuk suatu k = 0, ±1, ±2, ±3, ...

Residu terkecil dari 4x ≡ 1 ( mod 15 ) adalah 4.

2.         14 x ≡ 27 ( mod 31 )

            14 x ≡ 58 ( mod 31 )

               7x ≡ 29 ( mod 31 )

               7x ≡ 91 ( mod 31 )

                 x ≡ 13 ( mod 31 ) 

                 x = 13 + 31 k untuk suatu k = 0, ±1, ±2, ±3, ...

            Residu terkecil dari 14 x ≡ 27 ( mod 31 ) adalah 13.

            Jika ( a,m ) = 1 berdasarkan teorema 5.11 maka perkongruenan ax ≡ 1 ( mod m ) juga mempunyai tepat satu solusi. Solusi itu disebut invers dari a modulo m  yang disebut a^-1.

                        a^-1 (mod m ) dapat ditulis dengan ax ≡ 1 (mod m)

Contoh : 

Tentukan 2^-1 (mod 13)

Jawab :

            2x ≡ 1 ( mod 13 )

            2x ≡ 14 ( mod 13 )

  x ≡ 7 ( mod 13 )

 x = 7 + 13 k    untuk k = 0, ±1, ±2, ±3, ...

Residu terkecil dari 2x ≡ 1 ( mod 13 ) adalah 7.

TEOREMA 5.12

Jika ( a,m ) = d dan  d │ b maka perkongruenan linier  ax  ≡  b ( mod m ) memiliki tepat d  solusi.

BUKTI :

1.        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.

2.        Tak ada solusi lain, kecuali d buah solusi.

Jadi diambil bahwa r adalah solusi dari perkongruenan ax b (mod m). Misalkan solusi lain maka as ≡ b (mod m) dan ar ≡ b (mod m).

Jadi, as ≡ ar ≡ b (mod m).

Karena (a,m) = d dan as ≡ ar (mod m) diperoleh bahwa

     s ≡  r (mod ^m/_d)

     s ≡ r (mod m¢) karena m = dm¢.

Ini berarti s - r = tm¢ atau s = r + tm¢ untuk suatu bilangan bulat t.

 Karena s adalah residu terkecil modulo m, sedangkan semua residu terkecil modulo m berbentuk  r + km¢ dengan k = 0, 1, 2, 3, ..., (d - 1).

Maka s = r + tm¢ adalah salah satu di antara r + km¢.

Jadi tak ada solusi lain, kecuali d buah solusi, yaitu r + km¢ dengan k = 0, 1, 2, 3, ..., (d - 1).

Contoh :  

Selesaikanlah  6x  ≡ 15 ( mod 33)

Jawab :

            6x  ≡ 15 ( mod 33)                  karena (6 , 33) = 3 maka

            2x  ≡ 5 ( mod 11)                    karena (2 , 11) = 1 maka

            2x  ≡ 16 ( mod 11)

              x  ≡ 8 ( mod 11)

            ini berarti x = 8 + 11k, untuk setiap bilangan bulat k.

            untuk k = 0 maka x = 8

            untuk k = 1 maka x = 19

            untuk k = 2 maka x = 30

            Jadi 6x  ≡ 15 ( mod 33) mempunyai 3 buah solusi yang berbeda yaitu 8,  19, dan 30.

TEOREMA 5.13

Bentuk umum persamaan linear Diophantus adalah

ax + by = c dengan a, b ≠ 0 dan a, b, c, x , y bilangan-bilangan bulat.

Dari persamaan ax + by = c dapat dibentuk

ax  ≡ c ( mod b) atau by  ≡ c ( mod a)

Untuk menyelesaikan persamaan linear Diophantus kita dapat menyelesaikan salah satu perkongruenan linear tersebut.

Contoh :

Tentukan himpunan penyelesaian dari 9x + 16y = 35

Jawab :

            16y  ≡ 35 ( mod 9)                  karena (16 , 9) = 1 maka

16y  ≡ 44 ( mod 9)a

4y    ≡ 11 ( mod 9)                  karena (4 , 9) = 1 maka

4y    ≡ 20 ( mod 9)

y     ≡ 5 ( mod 9)

ini berarti y = 5 + 9t untuk setiap bilangan bulat t

Subsitusikan y = 5 + 9t ke persamaan 9x + 16 = 35

9x + 16(5 + 9t) = 35

9x + 80 + 144t = 35

x  = -5 – 16t untuk setiap bilangan bulat t

Jadi himpunan penyelesaian dari 9x + 16y = 35 adalah {(x, y) │ x = -5 - 16t, y = 5 + 9t dan t bilangan bulat} Jika t = 0, maka x = -5, y = 5, sehingga (-5, 5) adalah suatu penyelesaian dari persamaan 9x + 16y = 35.

Hal tersebut dapat dikatakan bahwa apabila (x_0, y₀) adalah suatu solusi dari persamaan linier Diophantus ax + by = c maka solusi-solusi lainnya adalah (x_0, + bt, y₀ - at) untuk setiap bilangan bulat t.

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 ( TEOREMA SISA)

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

BUKTI :

1.        Sistem perkongruenan linier x ≡ a₁ (mod m_i) untuk i = 1, 2, 3, ..., t mempunyai solusi bersama modulo (m₁, m₂, ..., m_t).

Pembuktian dengan induksi matematika untuk bilangan asli k.

Untuk k = 1 berarti x ≡ a₁ (mod m₁) jelas mempunyai solusi.

Untuk k = 2, yaitu sistem perkongruenan x ≡ a₁n(mod m) dan x ≡ a₂ (mod m₂) dengan (m₁, m₂) = 1.

x ≡ a₁ (mod m₁) berarti x = a₁ + k₁ m₁ untuk suatu bilangan bulat k₁.

Sehingga a₁ + k₁ m₁ ≡ a₂ (mod m₂)

                 k₁ m₁ ≡ a₂ ­- a₁ (mod m₂) dengan k₁ suatu variabel.

     Karena (m₁, m₂) = 1 maka perkongruenan terakhir ini mempunyai satu solusi untuk k₁ modulo m₂, katakanlah t, maka k₁ = t + k₂ m₂  untuk suatu k₂ memenuhi perkongruenan terakhir itu.

Jadi x = a₁ + k₁ m₁ = a₁ + (t + k₂ m₂) m₁

       x = (a₁ + tm₁) + k₂ m₁ m₂

Ini berarti x ≡ (a₁ + tm₁)(mod m₁ m₂).

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

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

     x ≡ s (mod m₁, m₂, m₃, ..., m_{r - 1})

Sehingga r perkongruenan itu dapat dinyatakan sebagai dua perkongruenan yaitu :

     x = s (mod m₁, m₂, m₃, ..., m_{r - 1})

     x = a_r (mod m_r)

Sistem perkongruenan dari dua perkongruenan ini mempunyai solusi bersama mod (m₁, m₂, m₃, ..., m_{r - 1}, m_r) = 1 sebab m_i dan m_j saling prima untuk i ≠ j.

2.        Solusi bersama itu tunggal.

Misalkan r dan s adalah solusi-solusi bersama dari sistem tersebut, maka :

     r ≡ a_i (mod m_i) dan s ≡ a_i (mod m_i)

     Sehingga (r - s) ≡ 0 (mod m_i) ini berarti bahwa m_i │ (r - s) untuk setiap i = 1, 2, 3, ..., k.

Jadi (r - s)suatu kelipatan persekutuan dari m₁, m₂, m₃, ..., m_k, Karena (m_i, m_j) = 1 untuk setiap i ≠ j, maka (m₁, m₂, m₃, ..., m_k) │ (r - s).

Tetapi ingat bahwa r maupun s adalah solusi-solusi perkongruenan, berarti r dan s adalah residu terkecil modulo (m₁, m₂, m₃, ..., m_k) sehingga :

     -m₁, -m₂, -m₃, ..., m_k < r - s < m₁, m₂, m₃, ..., m_k

Mengingat bahwa (r - s) adalah kelipatan persekutuan dari m₁, m₂, m₃, ..., m_k dam (m_i, m_j) untuk i ≠ j dapat disimpulkan bahwa :

     r - s = 0 atau r = s

Jadi solusi bersama dari sistem x = a_i (mod m_i) untuk i = 1, 2, 3, ..., k adalah tunggal.

catatan :

(m_i, m_j) =1, untuk i ≠ j dengan i = 1, 2, 3, ..., k dan j = 1, 2, 3, ..., k dikatakan m₁, m₂, m₃ saling prima dua-dua.    

BAB III. PENUTUP

A.    Simpulan

B.     Saran

DAFTAR PUSTAKA

Sukarman, Herry. 1993. Materi Pokok Teori Bilangan. Jakarta: Depdikbud