KONGRUENSI LINIER

MODUL 4

KONGRUENSI LINIER

Gatot Muhsetyo

 

Pendahuluan

       Dalam modul kongruensi linier ini diuraikan tentang sifat-sifat dasar kongruensi linier dan penyelesaiannya, kongruensi linier simultan, teorema sisa China, system kongruensi linier, dan penerapan kongruensi linier.

Sebagai bahasan yang berkaitan dengan aljabar (biasa), kongruensi linier serupa dengan persamaan linier, tetapi dengan semesta pembicaraan himpunan bilangan modulo. Meskipun demikian, terdapat banyak uraian dalam kongruensi linier yang memerlukan pemahaman yang berbeda dengan persamaan linier, misalnya terkait dengan banyaknya selesaian, yaitu kongruensi linier dapat tidak mempunyai selesaian, dan mempunyai satu atau lebih selesaian. Berikutnya, berbeda dengan persamaan linier satu variabel yang tidak bisa digabung dengan persamaan linier satu variabel yang lain, dua atau lebih kongruensi linier dapat digabung dan gabungannya disebut kongruensi linier simultan. Pada akhirnya pembahasan kongruensi linier yang serupa dengan persamaan linier adalah system kongruensi linier, dengan banyak variabel sama dengan banyaknya kongruensi.

 

Kompetensi Umum

Kompetensi Umum dalam mempelajari modul ini adalah mahasiswa mampu memahami konsep dan sifat kongruensi linier, penyelesaian kongruensi linier, kongruensi linier simultan, dan sistem kongruensi linier.

 

Kompetensi Khusus

Kompetensi Khusus dalam mempelajari modul ini adalah mahasiswa mampu menjelaskan konsep kongruensi linier dan sifat-sifatnya, konsep kongruensi linier simultan dan sifat-sifatnya, konsep sistem kongruensi linier dan sifat-sifatnya, serta keterkaitan satu sama lain untuk diterapkan dalam menyelesaikan masalah-masalah tertentu.

 

 

Susunan Kegiatan Belajar

       Modul 4 ini terdiri dari dua Kegiatan Belajar. Kegiatan Belajar pertama adalah Kongruensi Linier, dan Kegiatan Belajar kedua adalah Sistem Kongruensi Linier. Setiap kegiatan belajar memuat Uraian, Contoh, Tugas dan Latihan, Rambu-Rambu Jawaban Tugas dan Latihan, Rangkuman, dan Tes Formatif. Pada bagian akhir modul 2 ini ditempatkan  Rambu-Rambu Jawaban Tes Formatif 1 dan Tes Formatif 2.

 

Petunjuk Belajar

1. Bacalah Uraian dan Contoh dengan cermat dan berulang-ulang sehingga Anda benar-

benar memahami dan menguasai materi pembahasan.

2. Kerjakan Tugas dan Latihan yang tersedia secara mandiri. Jika dalam kasus  atau  ta-

hapan tertentu Anda mengalami kesulitan menjawab, maka pelajarilah Rambu-Ram-

bu Jawaban Tugas dan Latihan. Jika langkah ini belum berhasil menjawab  permasa-

lahan, maka mintalah bantuan tutor Anda, atau orang lain yang lebih tahu.

3. Kerjakan Tes  Formatif  secara  mandiri, dan  periksalah  Tingkat  Penguasaan  Anda

dengan cara mencocokkan jawaban Anda dengan Rambu-Rambu Jawaban Tes  For-

matif. Ulangilah pengerjaan Tes Formatif sampai Anda benar-benar merasa  mampu

mengerjakan semua soal dengan benar.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

MODUL 4

KEGIATAN BELAJAR 1

KONGRUENSI LINIER

Uraian

       Di dalam aljabar (biasa), pembahasan utama tentang persamaan adalah mencari akar, atau selesaian dari persamaan polinomial dengan koefisien bulat f(x) = 0 dengan :

f(x) = anxn + an-1xn-1 + … + ao

Nilai-nilai x yang memenuhi persamaan f(x) = 0 disebut akar atau  selesaian  persamaan f(x) = 0 . Persamaan f(x) = 0 berderajad n paling banyak mempunyai n selesaian.

Serupa dengan persamaan aljabar, pembahasan  utama  kongruensi  adalah  mencari bilangan-bilangan bulat yang memenuhi f(x) ≡ 0 (mod m) dengan :

f(x) = anxn + an-1xn-1 + … + ao

Sebagai peragaan, kongruensi

f(x) ≡ x3 + 6x2 – 11 ≡ 0 (mod 5)

dipenuhi oleh x = 3 sebab jika x diganti 3 diperoleh pernyataan yang benar :

f(3) = 33 + 6.32 – 11 = 27  + 54 – 11 ≡ 0 (mod 5)

Nilai x = 3 disebut selesaian kongruensi f(x) = x3 + 6x2 – 11 ≡ 0 (mod 5).

Menyelesaikan kongruensi berarti mencari selesaian kongruensi.

 

Definisi 4.1

Ditentukan  f(x)  adalah  suatu  polynomial  dengan  koefisien-koefisien  bulat,  dan

{ao , a1 , … , am-1} adalah suatu system residu yang lengkap modulo m.

Banyaknya selesaian kongruensi :

f(x) ≡ 0 (mod m)

adalah banyaknya ai , dengan ai = 0,1,2, … , m – 1 yang memenuhi kongruensi :

f(ai) ≡ 0 (mod m)

 

Kita perlu memperhatikan bahwa jika x = xo adalah suatu selesaian kongruensi           f(x) ≡ 0 (mod m) , dan diketahui x1 ≡ xo (mod m), maka :

f(x1) ≡ f(xo) (mod m) ≡ 0 (mod m)

Dengan demikian x1 adalah juga suatu selesain. Jadi, jika satu unsure dari suatu klas kongruensi modulo m adalah suatu selesaian, maka semua unsur dari klas kongruensi modulo m adalah juga selesaian-selesaian. Banyaknya selesaian suatu kongruensi modulo  m  adalah  banyaknya  selesaian  tidak  kongruen  modulo m,  yaitu  banyaknya

m klas kongruensi modulo m yang memberikan selesaian.

Contoh 4.1

Diketahui f(x) = 2x – 4

Banyaknya selesaian dari f(x) = 2x – 4 ≡ 0 (mod 6) ditentukan oleh banyaknya unsur tidak kongruen dari suatu sistem residu lengkap modulo 6, atau dari banyaknya klas residu modulo 6 yang memberikan satu unsur yang memenuhi kongruensi. Untuk keperluan menyelesaikan f(x) = 2x – 4 ≡ 0 (mod 6), suatu langkah yang lebih mudah adalah dengan mengambil {0,1,2,3,4,5} sebagai suatu sistem residu yang lengkap modulo 6. Karena pasangan unsur-unsur himpunan {0,1,2,3,4,5} tidak ada yang kongruen, maka selesaian dari f(x) = 2x – 4 ≡ 0 (mod 6) dapat dilakukan  dengan mencari unsur-unsur {0,1,2,3,4,5} yang memenuhi kongruensi, yaitu :

f(0) = 2.0 – 4 = – 4 , tidak kongruen 0 (mod 6)

f(1) = 2.1 – 4 = – 4 , tidak kongruen 0 (mod 6)

f(2) = 2.2 – 4 = 0 ≡ (mod 6)

f(3) = 2.3 – 4 = 2 , tidak kongruen 0 (mod 6)

f(4) = 2.4 – 4 = 4 , tidak kongruen 0 (mod 6)

f(5) = 2.5 – 4 = 6 ≡ 0 (mod 6)

Dengan demikian selesaian kongruensi adalah x ≡ 2 (mod 6) dan x ≡ 5 (mod 6), dan banyaknya selesaian adalah dua.

 

Definisi 4.2

Suatu kongruensi yang mempunyai bentuk :

ax ≡ b (mod m)

dengan a, b, m Z disebut suatu kongruensi linier satu variabel.

Perhatikan bahwa jika x = xo adalah suatu selesaian ax ≡ b (mod m), dan jika diketahui bahwa x1 ≡ xo (mod m), maka ax1 ≡ axo (mod m), dengan demikian x1 juga suatu selesaian.

 

Contoh 4.2

Kongruensi linier 7x ≡ 3(mod 12) mempunyai satu selesaian x ≡ 9 (mod 12) sebab x = 9 merupakan satu-satunya unsur dalam suatu klas residu modulo 12 yang memberikan satu unsur yang memenuhi kongruensi. Dengan demikian x = 9 merupakan satu unsur dari suatu sistem residu yang lengkap modulo 12 yang memenuhi kongruensi, x = 9 adalah satu unsur dari sistem residu lengkap modulo 12 yaitu {0,1,2,3,4,5,6,7,8,9,10,11}

 

Contoh 4.3

Kongruensi linier 6x ≡ 9 (mod 15) mempunyai tiga selesaian, x = 4 + 15r,  x = 9 + 15r, dan x = 14 + 15r untuk sebarang bilangan bulat r.

Nilai-nilai x {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14} tidak ada yang memenuhi kongruensi 6x ≡ 9 (mod 15) selain 4, 9, dan 14.

 

Berikut ini adalah suatu teorema yang penting karena dapat memberikan alasan dapat atau tidak dapat suatu kongruensi linier diselesaikan, serta memberikan jawaban tentang banyaknya selesaian suatu kongruensi linier.

 

Teorema 4.1

Jika (a,m) = d dan kongruensi ax ≡ b (mod m) mempunyai selesaian, maka d│b

Jika d│b , maka kongruensi ax ≡ b (mod m) mempunyai d selesaian.

Bukti :

ax ≡ b (mod m), maka menurut definisi 3.1, m│ax – b

Diketahui d = (a,m), maka menurut definisi 2.3, d│a dan d│m. Karena d│a, maka

sesuai teorema 2.1, d│ax untuk sebarang bilangan bulat x. Selanjutnya, dari d│m

dan m│ax – b , sesuai dengan teorema 2.2, d│ax – b .

Berdasarkan teorema 2.9, d │ax dan d │ax – b , berakibat d │– b , sehingga d │b.

Selanjutnya, ax ≡ b (mod m) dapat dinyatakan sebagai  d(a/d)x ≡ d(b/d) (mod m),

dan  sesuai  dengan  teorema 3.6 (a),  dapat  ditentukan  (a/d)x ≡ (b/d) (mod m/d).

Karena (a/d,m/d) = 1 dan (a/d)x ≡ (b/d) (mod m/d) , maka menurut teorema 3.10,

kongruensi linier (a/d)x ≡ (b/d) (mod m/d) mempunyai suatu selesaian x = xo + t.

dengan xo ≡ .(mod m) dan t Z. Dengan demikian seluruh selesaian

kongruensi adalah :

x = x0 , x0 + 1() , x0 + 2() + … + x0 + (d – 1)( )

 

 

Contoh 4.4

Selesaikan kongruensi-kongruensi linier :

(a) 36x ≡ 8 (mod 102)

(b) 3x ≡ 2 (mod 5)

(c) 15x ≡ 6 (mod 18)

Jawab :

(a) (36,102) = 6 dan 6 tidak membagi 8, maka 36x ≡ 8 (mod 102) tidak mempunyai

selesaian.

(b) (3,5) = 1 dan 1│2, maka 3x ≡ 2 (mod 5) mempunyai satu selesaian x ≡ 4 (mod 5)

(c) (15,18) = 3  dan  3│6, maka  15x ≡ 8 (mod 18)  mempunyai  tiga  selesaian, yaitu

x ≡ 4,10,16 (mod 18)

 

Contoh 4.5

Selesaikan kongruensi linier 144x ≡ 216 (mod 360)

Jawab:

FPB dari 144 dan 360 dicari dengan menggunakan teorema 2.20 Algoritma Euclides

360 = 2.144 + 72

144 = 2.72 + 0

(144,360) = 72

72│216, maka 144x ≡ 216 (mod 360) mempunyai 72 selesaian. Seluruh selesaian dicari sebagai berikut :

144x ≡ 216 (mod 360)

2x ≡ 3 (mod 5)

x ≡ 23.3 (mod 5) ≡ 8.3 (mod 5) ≡ 4(mod 5)

Selesaian kongruensi linier 144x ≡ 216 (mod 360) adalah :

x ≡ 4, 4 + 1.5, 4 + 2.5, … , 4 + (72 – 1).5 (mod 360)

x ≡ 4, 9, 14, … , 359 (mod 360)

 

Perhatikan tiga hal dalam menyelesaikan kongruensi linier.

(1) ax ≡ ay (mod m) diselesaikan melalui x ≡ y (mod )

(2) ax ≡ ay (mod m) dan (a,m) = 1 diselesaikan melalui x ≡ y (mod m)

(3) ax ≡ b (mod m) dengan nilai-nilai a, b, dan m yang relative besar dilakukan dengan

menyederhanakan kongruensi, yaitu mengganti kongruensi semula dengan kongru-

ensi lain yang mempunyai bilangan modulo lebih kecil. Prosedur ini bisa diulangi

sampai diperoleh suatu kongruensi yang selesaiannya mudah ditentukan.

Diketahui kongruensi linier ax ≡ b (mod m), misalkan a < m (jika a > m, maka

a dapat “dikecilkan” dengan jalan mencari  residu (sisa) positif  terkecil  dari a

modulo m).

ax ≡ b (mod m),  maka  m│ax – b,  sehingga  ax – b = my   untuk  suatu y Z,

berarti my + b = ax, dan akibatnya  a│my + b, atau  my ≡ – b (mod a).  Karena

m > a, maka m dapat “dikecilkan” dengan jalan mencari residu positif  terkecil

dari m modulo a. Sampai pada tahap ini jelas bahwa  kongruensi  linier  semula

ax ≡ b (mod m) berubah menjadi kongruensi linier my ≡ – b (mod a) yang lebih

“sederhana” karena mempunyai modulo a yang lebih kecil dari a.

Selesaikan kongruensi linier my ≡ – b (mod a) jika memang sudah menjadi lebih

mudah untuk diselesaikan, misalkan selesaiannya adalah y = yo .  Dengan  demi-

kian dari ax – b = my,  atau x = , dapat  ditentukan  bahwa  x0 =

merupakan suatu selesaian kongruensi linier ax ≡ b (mod m).

Ulangi langkah serupa jika memang  kongruensi  linier  my ≡ – b (mod a)  masih

sulit untuk diselesaikan. Misalkan  residu  positif  terkecil m  modulo a  adalah k,

maka my ≡ – b (mod a) dapat diubah menjadi az ≡ b (mod a).  Demikian  seterus-

sehingga pada tahapan tertentu dapat diperoleh suatu selesaian, dan dari selesaian

yang diperoleh dapat diproses mundur sehingga diperoleh selesaian  dari kongru-

ensi ax ≡ b (mod m).

Contoh 4.6

Selesaikan 10x ≡ 3 (mod 23)

Jawab :

Dari 10x ≡ 3 (mod 23) dapat diperoleh   kongruensi lain yang lebih “sederhana”,

misalnya dengan variabel y, yaitu 23y ≡ – 3 (mod 10), dan berikutnya dapat dica-

ri residu positif  terkecil 23  modulo 10,  yaitu 3,  sehingga  diperoleh kongruensi

3y ≡ – 3 (mod 10), dan kita sudah dapat menentukan selesaian 3y ≡ – 3 (mod 10)

yaitu y ≡  – 1 (mod 10) atau y ≡  9 (mod 10), berarti yo = 9, sehingga dapat diten-

tukan x0 =

 

Contoh 4.7

Selesaikan 19x ≡ 2 (mod 49)

Jawab :

Dari 19x ≡ 2 (mod 49) dapat diperoleh kongruensi lain  49y ≡ – 2 (mod 19)  atau

11y ≡  – 2 (mod 19). Karena kita relative masih sulit untuk menentukan selesaian

11y ≡  – 2 (mod 19) , maka langkah serupa dilakukan dengan memilih suatu vari-

abel lain sehingga diperoleh 19z ≡ 2 (mod 11), atau 8z ≡ 2 (mod 11). Karena kita

merasakan masih sulit untuk menyelesaikan, langkah serupa diulang sehingga di-

peroleh 11r ≡  – 2 (mod 8), atau 3r ≡  – 2 (mod 8). Ternyata kita sudah lebih  mu-

memperoleh   selesaian,  yaitu  r0 ≡ 2 (mod 8),  selanjutnya  z0 = (11r0 + 2)/8 = 3,

y0 = (19z0 – 2 )/11 = 5, dan x0 = (49y0 + 2)/19 = 13. Selesaian kongruensi adalah

x ≡ 13 (mod 49)

 

Jika kita cermati contoh 4.7, langkah-langkah memperoleh selesaian dapat  diperaga-

kan sebagai berikut :

19x ≡  2 (mod 49)     x0 =

———————-

49y ≡ -2 (mod 19)

11y ≡ -2 (mod 19)     y0 =

———————-

19z ≡  2 (mod 11)

8z ≡  2 (mod 11)      z0 =

———————-

11r ≡ -2 (mod 8)

3r ≡ -2 (mod 8)        r0 = 2

 

Contoh 4.8

Selesaikan kongruensi linier 67320x ≡ 136 (mod 96577)

Jawab :

(67320,96577) dicari dengan menggunakan teorema 2.20 Algoritma Euclides :

96577 = 1.67320 + 29257

67320 = 2.29257 + 8806

29257 = 3.8806 + 2839

8806 = 3.2839 + 289

2839 = 9.289 + 238

289 = 1.238 + 51

238 = 4.51 + 34

51 = 1.34 + 17

34 = 2.17 + 0

Karena (67320,96577) = 17, dan 17│136, maka kongruensi dapat diselesaikan

dan mempunyai 17 selesaian.

Selanjutnya, dari 67320x ≡ 136 (mod 96577), atau :

17.3960 x ≡ 17.8 (mod 17.5681)

dengan  (67320,96577) = 17, kita dapat menggunakan teorema 3.6 (a) sehingga

diperoleh 3960 x ≡ 8 (mod 5681), dan diselesaikan seperti uraian sebelumnya.

3960 x ≡    8  (mod 5681)     x0 =

——————————-

5681 y ≡ – 8  (mod 3960)

1721 y ≡ – 8  (mod 3960)     y0 =

——————————-

3960 z ≡   8  (mod 1721)

518 z ≡   8  (mod 1721)      z0 =

——————————

1721 r ≡ – 8  (mod  518)

167 r ≡ – 8  (mod  518)      r0 =

——————————

518 s ≡    8  (mod  167)

17 s ≡    8  (mod  167)      s0 =

——————————

167 t ≡ – 8  (mod    17)

14 t ≡ – 8  (mod    17)      t0 =

——————————

17 m ≡   8  (mod    14)

3m ≡   8  (mod    14)      m0 = 12

Selesaian kongruensi adalah :

x ≡ 4694,4694 + 1.5681, … , 4694 + 16.5681 (mod 96577)

x ≡ 4694,10375, … , 95560 (mod 96577)

 

Marilah sekarang kita bahas lebih lanjut gabungan dari dua atau lebih kongruensi linier dengan satu variabel, dan gabungan ini disebut sistem kongruensi linier simultan.

Definisi 4.3

Sistem kongruensi linier satu variabel :

x ≡ a1(mod m1), x ≡ a2(mod m2), … , x ≡ ar(mod mr),

disebut system kongruensi linear simultan

Untuk mencari selesaian system kongruensi linier simultan, kita memerlukan pembahasan awal tentang system yang terdiri dari dua kongruensi linier.

 

Teorema 4.2

Sistem kongruensi linier simultan :

x ≡ a1(mod m1), x ≡ a2(mod m2)

dapat diselesaikan jika dan hanya jika a1 ≡ a2 (mod (m1,m2))

Bukti :

() Diketahui x ≡ a1(mod m1), maka sesuai teorema 3.1, x = a1+ m1k , k Z

Selanjutnya, dari x = a1+ m1k dan x ≡ a2(mod m2), dapat ditentukan bahwa

a1+ m1k ≡ a2 (mod m2), atau m1k ≡ a2 – a1 (mod m2)

Sesuai teorema 4.1, kongruensi linier m1k ≡ a2 – a1 (mod m2) dapat diselesai-

kan jika (m1,m2)│a2 – a1, dan sesuai definisi 3.1, a1 ≡ a2 (mod (m1,m2))

() Buktikan !

 

Teorema 4.2 juga memberikan petunjuk, jika banyaknya kongruensi linear dalam system yang simultan lebih dari dua, maka penyelidikan dapat  dilakukan untuk semua  kemungkinan pasangan kongruensi. Demikian pula dapat ditentukan, jika (m1,m2) = 1, maka system kongruensi linier simultan x ≡ a1(mod m1), x ≡ a2(mod m2) selalu dapat di-

selesaikan, dan hal ini dapat diperluas untuk sistem kongruensi linier simultan yang terdiri lebih dari dua kongruensi linier.

Berikutnya, beberapa cara yang dapat digunakan menyelesaikan sistem kongruensi linier simultan adalah cara biasa, cara iterasi, dan cara sisa China.

 

Cara Biasa

Cara ini disebut biasa karena kita hanya membuat barisan bilangan yang memenuhi masing-masing kongruensi, dan dilanjutkan dengan pencarian unsur persekutuan dari semua kongruensi. Penetapan selesaian didasarkan pada teorema 3.6 (b).

 

Contoh 4.9

Selesaikan sistem kongruensi linier simultan x ≡ 13 (mod 16) dan x ≡ 5 (mod 14)

Jawab :

13 ≡ 5 (mod (16,14), atau 8 ≡ 0 (mod 2),  maka  sistem kongruensi dapat  diselesai-

kan.

x ≡ 13 (mod 16) ≡ 13,29,45,61,77,93,109, … (mod 16)

x ≡ 5 (mod 14) ≡ 5,19,33,47,61,75,89,103, … (mod 14)

Unsur persekutuan dari kedua kongruensi linier adalah 61, sehingga :

x ≡ 61 (mod 16) dan x ≡ 61 (mod 14)

dan sesuai dengan teorema 3.6 (b), x ≡ 61 (mod [16,14]) ≡ 61 (mod 112)

 

Contoh 4.10

Sistem kongruensi linier simultan x ≡ 15 (mod 51) dan x ≡ 7 (mod 42) tidak mempunyai

selesaian sebab 15 tidak kongruen 7 modulo (51,42) = 3.

 

Meskipun sederhana dan mudah, cara biasa  menjadi semakin sulit dan tidak efisien jika

banyaknya kongruensi linier bertambah banyak, yaitu barisan atau daftar bilangan yang dibuat menjadi panjang.

Cara Iterasi

Makna iterasi memuat adanya langkah atau proses berulang. Ini berarti bahwa langkah berikutnya dikerjakan serupa setelah langkah sebelumnya dilakukan. Sebagai ilustrasi, jika ada tiga kongruensi linier yang simultan, maka dua kongruensi diselesaikan lebih dahulu, sehingga diperoleh selesaian, dilanjutkan dengan penyelesaian kongruensi ketiga dengan selesaian dua kongruensi yang telah dikerjakan.

Contoh 4.11

Selesaikan sistem kongruensi linier simultan 2x ≡ 3 (mod 5), 3x ≡ 4 (mod 7), dan

5x ≡ 8 (mod 12)

Jawab :

Ketiga kongruensi belum memenuhi syarat “baku”, sehingga masing-masing perlu

disesuaikan, diperoleh x ≡ 4 (mod 5), x ≡ 3 (mod 7), dan x ≡ 4 (mod 12).

x = 4 + 5t sebab x ≡ 4 (mod 5).

Dari substitusi x = 4 + 5t kepada x ≡ 3 (mod 7) diperoleh 4 + 5t ≡ 3 (mod 7), atau

5t ≡ – 1  (mod 7) ≡ 6 (mod 7), sehingga t ≡ 4 (mod 7), atau t = 4 + 7s.

Dari substitusi t = 4 + 7s kepada x = 4 + 5t diperoleh x = 4 + 5(4 + 7s) = 24 + 35s.

Dengan demikian x ≡ 24 (mod 35).

Berikutnya kita akan menyelesaikan x ≡ 24 (mod 35) dan x ≡ 4 (mod 12).

x ≡ 24 (mod 35), berarti x = 24 + 35s.

Substitusi x = 24 + 35s kepada x ≡ 4 (mod 12) diperoleh 24 + 35s ≡ 4 (mod 12),

11s ≡ 4 (mod 12), atau s ≡ 8 (mod 12), sehingga s = 8 + 12r.

Dari substitusi s = 8 + 12r kepada x = 24 + 35s diperoleh x = 24 + 35(8 + 12r)

= 304 + 420s. Dengan demikian x ≡ 304 (mod 420)

 

Sebelum kita membicarakan cara China, marilah kita lihat suatu teorema yang diperlukan untuk membuktikan teorema sisa China.

 

Teorema 4.3

       Jika p1│q , p2│q , dan (p1,p2) = 1 , maka p1p2 │q

Bukti :

(p1,p2) = 1, maka sesuai teorema 2.12, xp1 + yp2 = 1 untuk suatu x,y  Z, sehingga

xp1q + yp2q = q .

p1│q dan p2│q , maka sesuai teorema 2.8, p1p2│p2q dan p1p2│p1q.

Selanjutnya, dari p1p2│p2q dan p1p2│p1q, sesuai teorema 2.1, p1p2│yp2q

dan p1p2│xp1q , dan berdasarkan teorema 2.4, pr│xpq + yqr , atau pr│q .

 

Teorema 4.4

Jika p1│q, p2│q, … , pr│q, dan (p1,p2, … ,pr) = 1 , maka p1p2 … pr│q

Buktikan !

 

Cara China

Masalah kongruensi linier muncul pada awal abad satu,  dan dapat ditemukan di dalam aritmetika matematisi China yang bernama Sun-Tsu (Rosen, 1993:136). Cara China untuk menyelesaikan system kongruensi linier didasarkan pada suatu teorema yang disebut Teorema Sisa China, dimana pasangan dari setiap dua modulo dari  kongruensi adalah relatif prima.

 

Teorema 4.5. Teorema Sisa China

Ditentukan bahwa m1,m2, … , mr adalah bilangan-bilangan bulat positif yang setiap

pasang adalah relative prima, dan a1,a2, … , ar adalah sebarang r bilangan bulat.

Sistem kongruensi linier simultan :

x ≡ a1 (mod m1) , x ≡ a2 (mod m2) , … , x ≡ ar (mod mr)

mempunyai suatu selesaian yang tunggal modulo M = m1.m2 …  mr

Bukti :

M = m1.m2 …  mr , dan ambil Mi = M/mi , maka mi│M sehingga (Mi ,mi) = 1

dengan 1 ≤ i ≤ r .

Sesuai dengan teorema 4.1, karena (Mi ,mi) = 1, maka tentu ada satu bi  Z

sedemikian hingga Mibi ≡ 1 (mod mi) , dan Mibi ≡ 0 (mod mj) jika i  j .

Ambil x = M1b1a2 + M2b2a2+ … + Mrbrar, maka x adalah suatu selesaian simultan

dari r kongruensi linier. Untuk menunjukkan hal ini, kita harus  membuktikan bah-

wa x ≡ ai (mod mi) untuk i = 1,2, … , r .

x = M1b1a2 + M2b2a2+ … + Mrbrar

≡ (M1b1a1 + M2b2a2+ … + Mibiai + … + Mrbrar) (mod mi)

≡ (0.a1 + 0.a2 + … + 1.ai + … + 0.ar) (mod mi)

x ≡ ai (mod mi) , i = 1,2, … ,r

Untuk menunjukkan ketunggalan selesaian, dimisalkan ada dua selesaian yaitu x0

dan x1 , maka x0 ≡ x1 ≡ ai (mod mi) , yaitu x0 ≡ x1 (mod mi), atau mi│x0 – x1 .

Dengan demikian m1│x0 – x1, m2│x0 – x1, … , mr│x0 – x1 , dan sesuai dengan teo-

rema 4.4, m1m2 … mr│x0 – x1 , atau M│x0 – x1, berarti x0 ≡ x1 (mod M).

Jadi selesaian simultan dari r kongruensi linier adalah tunggal dengan modulo m.

 

Contoh 4.12

Selesaikan system kongruensi linier simultan x ≡ 5 (mod 8), x ≡ 3 (mod 7), dan

x ≡ 4 (mod 9)

Jawab :

a1 = 5 , a2 = 3 , a3 = 4 , m1 = 8 , m2 = 7 , dan m3 = 9

(m1,m2) = (m1,m3) = (m2,m3) = 1

M = m1m2m3 = 8.7.9 = 504

(M/m1)b1 ≡ 1 (mod m1) , maka 7.9b1 ≡ 1 (mod 8) , sehingga b1 = 7

(M/m2)b2 ≡ 1 (mod m2) , maka 8.9b2 ≡ 1 (mod 7) , sehingga b2 = 4

(M/m3)b3 ≡ 1 (mod m3) , maka 8.7b3 ≡ 1 (mod 9) , sehingga b3 = 5

Jadi x = 7.9.7.5 + 8.9.4.3 + 8.7.5.4 = 4189

x ≡ 157 (mod 504)

 

Contoh 4.13

Selesaikan system kongruensi linier simultan 3x ≡ 2 (mod 5) , 4x ≡ 3 (mod 7) ,

8x ≡ 5 (mod 9) , dan 4x ≡ 7 (mod 11)

Jawab :

Masing-masing kongruensi linier perlu diubah menjadi kongruensi lain dengan

koefisien x adalah 1 :

3x ≡ 2 (mod 5) , maka x ≡ 4 (mod 5)

4x ≡ 3 (mod 7) , maka x ≡ 6 (mod 7)

8x ≡ 5 (mod 9) , maka x ≡ 4 (mod 9)

4x ≡ 7 (mod 9) , maka x ≡ 10 (mod 11)

a1 = 4 , a2 = 6 , a3 = 4 , a4 = 10 , m1 = 5 , m2 = 7 , m3 = 9 , m4 = 11

(m1,m2) = (m1,m3) = (m1,m4) = (m2,m3) = (m2,m4) = (m3,m4) = 1

M = m1m2m3m4 = 5.7.9.11 = 3465

(M/m1)b1 ≡ 1 (mod m1) , maka 7.9.11b1 ≡ 1 (mod 5) , sehingga b1 = 2

(M/m2)b2 ≡ 1 (mod m2) , maka 5.9.11b2 ≡ 1 (mod 7) , sehingga b2 = 3

(M/m3)b3 ≡ 1 (mod m3) , maka 5.7.11b3 ≡ 1 (mod 9) , sehingga b3 = 4

(M/m4)b4 ≡ 1 (mod m4) , maka   5.7.9b4 ≡ 1 (mod 9) , sehingga b4 = 8

Jadi x = 7.9.11.2.4 + 5.9.11.3.6 + 5.7.11.4.4 + 5.7.9.8.10 = 4581

x ≡ 769 (mod 3465)

 

 

Tugas dan Latihan

Tugas

Setelah banyak mempelajari tentang bahan paparan pada kegiatan belajar 1 ini, maka cobalah jelaskan atau uraikan bagaiman cara menyelesaikan suatu sistem kongruensi linier simultan yang dapat diselesaikan tetapi tidak semua pasangan modulo adalah relatif prima.

Berikutnya, dari suatu kongruensi linier ax ≡ b (mod m) y, pilih suatu nilai m lebih dari 10000, nilai a lebih dari 1000, dan nilai b lebih dari 10, sedemikian hingga (a,m) > 1 dan (a,m)│b. Selesaikan kongruensi linier ini.

 

Latihan

1. Selesaikan kongruensi linier 19x ≡ 1 (mod 140)  menggunakan teorema sisa China

2. Selesaikan kongruensi linier 29393x ≡ 4743 (mod 2805)

3.Selesaikan system kongruensi linier simultan 2x ≡ 8 (mod 20) dan 3x ≡ 2 (mod 7)

4. Selesaikan system kongruensi linier simultan x ≡ 1 (mod 2), x ≡ 1 (mod 3),

x ≡ 1 (mod 4), x ≡ 1 (mod 5), x ≡ 2 (mod 7), dan x ≡ 2 (mod 11)

5. Seorang  gadis  membawa  sekeranjang  telur. Jika  telur-telur itu  dihitung dua-dua,

maka akan tertinggal satu telur. Jika telur-telur itu dihitung tiga-tiga, maka akan ter-

tinggal dua telur. Jika  dilanjutkan  dengan  menghitung  lima-lima dan  tujuh-tujuh,

maka secara berturut-turut akan tertinggal empat telur dan enam telur. Tidak ada te-

lur yang tertinggal jika dihitung  sebelas-sebelas. Berapa  banyaknya  telur  minimal

di dalam keranjang ?

 

Rambu-Rambu Jawaban Tugas Dan Latihan

Rambu-Rambu Jawaban Tugas

Bagian dari kongruensi-kongruensi linier yang memenuhi syarat (mi,mj) = 1 untuk ij

diselesaikan dengan teorema sisa China, dan bagian dari  kongruensi-kongruensi  yang

lain diselesaikan dengan iterasi, kemudian gabungannya  diselesaikan  dengan  memlih

cara yang memungkinkan untuk digunakan.

Pilih suatu kongruensi 3375x ≡ 30 (mod 21480). Gunakan Algoritma Euclides untuk mencari (3375,21480) sehingga diperoleh 15. Karena 15 membagi 30, maka kongruensi linier mempunyai selesaian. Selesaikan dengan cara bertahap sehingga diperoleh :

x ≡ 1362, 2794, … , 21410 (mod 21480)

 

Rambu-Rambu Jawaban Latihan

1. 140 = 4.5.7 dan (4,5) = (4,7) = (5,7) = 1, sehingga kongruensi 19x ≡ 30 (mod 140)

dapat dipecah menjadi sistem kongruensi linier simultan 19x ≡ 30 (mod 4),

19x ≡ 30 (mod 5), dan 19x ≡ 30 (mod 7)

Masing-masing kongruensi linier secara berturut-turut diubah menjadi x ≡ 3 (mod 4),

x ≡ 4 (mod 5), dan x ≡ 3(mod 7).

35b1 ≡ 1 (mod 4) , maka b1 = 3

28b2 ≡ 1 (mod 5) , maka b2 = 2

20b3 ≡ 1 (mod 7) , maka b3 = 6

x = 35.3.3 + 28.2.4 + 20.6.3 = 899 ≡ 59 (mod 140)

2. 29393x ≡ 4743 (mod 2805) diubah menjadi 1343x ≡ 1938 (mod 2805)

2805 = 2.1343 + 119

1343 = 11.119 + 34

119 = 3.34 + 17

34 = 2.17 + 0

(1343,2845) = 17 dan 17│1938, berarti terdapat 17 selesaian

1343x ≡ 1938 (mod 2805)

79x ≡ 114 (mod 165)        x0 =

——————————–

165y ≡ – 114  (mod 79)

7y ≡      44  (mod 79)       y0 =

——————————–

79z ≡    – 44  (mod 7)

2z ≡         5 (mod 7)         z0 = 6

Jadi x ≡ 156,321, … , 2796 (mod 2805)

3. 2x ≡ 8 (mod 20 , maka x ≡ 4 (mod 20) dan x ≡ 14 (mod 20)

3x ≡ 2 (mod 7)  , maka x ≡ 3 (mod 7)

Dari kongruensi linier simultan x ≡ 4 (mod 20) dan x ≡ 3 (mod 7) ,dengan cara

biasa atau cara iterasi dapat diperoleh x ≡ 24 (mod 140)

Dari kongruensi linier simultan x ≡ 14 (mod 20) dan x ≡ 3 (mod 7) ,dengan cara

biasa atau cara iterasi dapat diperoleh x ≡ 94 (mod 140)

4. Dari x ≡ 1 (mod 2), x ≡ 1 (mod 3), x ≡ 1 (mod 4), dan x ≡ 1 (mod 6), dapat ditentukan

bahwa x ≡ 1 (mod [2,3,4,5]), atau x ≡ 1 (mod 60).

Selanjutnya, dari  x ≡ 2 (mod 7), dan x ≡ 2 (mod 11) dapat ditentukan bahwa

x ≡ 2 (mod 77)

Dengan demikian 77b1 ≡ 1(mod 60) dan 60b2 ≡ 1 (mod 77) , sehingga diperoleh

b1 = 53 dan b2 = 9

Jadi x = 77.53.1 + 60.9.2 = 5161 ≡ 541 (mod 4620)

5. Misalkan banyaknya telur sekeranjang adalah x, maka : x ≡ 1 (mod 2), x ≡ 2 (mod 3),

x ≡ 2 (mod 5), x ≡ 2 (mod 7), dan x ≡ 0 (mod 11)

Dari x ≡ 2 (mod 3), x ≡ 2 (mod 5), dan x ≡ 2 (mod 7) dapat ditentukan bahwa

x ≡ 2 (mod 105)

Dengan demikian dapat ditentukan suatu system kongruensi linier simultan

x ≡ 1 (mod 2), x ≡ 2 (mod 105) dan x ≡ 0 (mod 11)

kemudian dapat dicari :

105.11b1 ≡ 1 (mod 2), atau b1 = 1

2.11b2 ≡ 1 (mod 105), atau b2 = 43

105.2b3 ≡ 1 (mod 11), atau b3 = 1

Jadi x = 105.11.1.1 + 2.11.43.2 + 105.2.1.0 = 3047 ≡ 737 (mod 2310)

Banyaknya telur minimal dalam keranjang adalah 737.

Jika tidak dibatasi oleh minimal, maka jawaban yang diperoleh banyak, yaitu :

737, 737 + 2310, 737 + 2.2310, … , 737 + k.2310 dengan k Z+

 

Rangkuman

Berdasarkan seluruh paparan pada Kegiatan Belajar 1 ini, maka garis besar bahan yang dibahas meliputi Definisi, Teorema, dan penerapan dalam penyelesaian masalah terkait,

terutama tentang konsep kongruensi linier , cara menyelesaikan kongruensi linier, konsep system kongruensi linier simultan, dan cara menyelesaikan system kongruensi linier simultan.

1. Definisi 4.1 tentang banyaknya selesaian kongruensi

2. Definisi 4.2 tentang kongruensi linier simultan satu variabel

3. Tiga hal yang perlu diperhatikan dalam menyelesaikan kongruensi linier

(a) ax ≡ ay (mod m) jika (a,m)  1

(b) ax ≡ ay (mod m) jika (a,m) = 1

(c) ax ≡ b (mod m) untuk nilai-nilai a, b, dan m yang relatif besar

4. Definisi 4.3 tentang sistem kongruensi linier simultan

5. Teorema 4.2

Sistem kongruensi linier simultan :

x ≡ a1(mod m1), x ≡ a2(mod m2)

dapat diselesaikan jika dan hanya jika a1 ≡ a2 (mod (m1,m2))

6  Cara-cara menyelesaikan sistem kongruensi linier simultan : cara biasa, cara iterasi,

dan cara China

7. Teorema 4.3

       Jika p1│q , p2│q , dan (p1,p2) = 1 , maka p1p2 │q

8. Teorema 4.4

Jika p1│q, p2│q, … , pr│q, dan (p1,p2, … ,pr) = 1 , maka p1p2 … pr│q

9. Teorema 4.5. Teorema Sisa China

Ditentukan bahwa m1,m2, … , mr adalah bilangan-bilangan bulat positif yang setiap

pasang adalah relative prima, dan a1,a2, … , ar adalah sebarang r bilangan bulat.

Sistem kongruensi linier simultan :

x ≡ a1 (mod m1) , x ≡ a2 (mod m2) , … , x ≡ ar (mod mr)

mempunyai suatu selesaian yang tunggal modulo M = m1.m2 …  mr

 

Tes Formatif 1

1. Skor 20

Selesikan kongruensi linier 23x ≡ 17 (mod 180) dengan dua cara:

(a) cara penyelesaian kongruensi linier

(b) cara penyelesaian sistem kongruensi linier simultan

2. Skor 20

Sekelompok 13 orang perompak akan membagikan sekantung butir berlian.

Dalam usaha pembagian pertama, ternyata tersisa 5 butir berlian, dan karena dirasa

tidak bisa adil, terjadi perkelaihan dan 4 perompak terbunuh.

Dalam usaha pembagian kedua, ternyata tersisa 6 butir berlian, dank arena dirasa ma-

sih belum adil, terjadi perkelaihan dan 2 perompak terbunuh.

Dalam usaha pembagian ketiga, ternyata tersisa 3 butir berlian, dan perkelaihan kem-

bali terjadi dengan 2 orang terbunuh.

Dalam usaha pembagian keempat, ternyata tidak ada butir berlian yang tersisa, semua

perompak yang masih hidup menerima bagian yang banyaknya sama.

Berapa banyaknya butir berlian minimal dalam kantung ?

 

3. Skor 20

Selesaikan sistem kongruensi linier simultan 5x ≡ 1 (mod 6), 3x ≡ 10 (mod 11),

2x ≡ 7 (mod 13), 3x ≡ 4 (mod 5), 4x ≡ 3 (mod 7)

4. Skor 10

Selesaikan sistem kongruensi linier simultan 9x ≡ 4 (mod 14), 5x ≡ 17 (mod 21) dan

7x ≡ 10 (mod  30)

5. Skor 20

Carilah suatu bilangan kelipatan 13 yang bersisa 2 jika dibagi 3,5,7, dan 8, serta ber-

sisa 10 jika dibagi 17.

6. Skor 10

Selesaikan 26733x ≡ 133 (mod 54340)

 

Cocokkanlah jawaban Anda dengan Rambu-Rambu atau Kunci Jawaban Tes Formatif 1 yang terdpat di bagian akhir modul ini. Kemudian perkirakan skor jawaban Anda yang menurut Anda benar, dan gunakan kriteria berikut untuk mengetahui tingkat penguasaan Anda terhadap materi Kegiatan Belajar 1.

Skor Jawaban Yang Benar

Tingkat Penguasaan =  ————————————   x   100 %

100

Tingkat Penguasaan Anda dikelompokkan menjadi :

Baik sekali      :    90 % – 100 %

Baik                :     80 % – 89 %

Cukup             :     70 % – 79 %

Kurang            :     < 70 %

 

Apabila Anda mencapai tingkat penguasaan 80 % atau lebih, maka Anda dapat meneruskan ke Kegiatan Belajar 2, Bagus !

Jika tingkat penguasaan Anda kurang dari 80 %, maka seharusnya Anda mengulangi materi Kegiatan Belajar 1, terutama pada bagian-bagian yang belum Anda pahami dan kuasai dengan baik. Selamat Belajar !

 

MODUL 4

KEGIATAN BELAJAR 2

SISTEM KONGRUENSI LINIER

 

Uraian

Pada pembahasan tentang aljabar (biasa), salah satu topik adalah sistem persamaan linier. Dua persamaan linier dua variabel, tiga persamaan linier tiga variabel, atau n per-

samaan linier n variabel membentuk sistem persamaan linier.

Penyelesaian sistem persamaan linier dapat dilakukan dengan cara eliminasi, cara substitusi, cara matriks, atau cara determinan. Masing-masing cara mempunyai langkah- langkah dan aturanp-aturan tertentu dalam memperoleh selesaian.

Serupa dengan pembahasan di aljabar, salah satu topik di teori bilangan adalah sistem kongruensi linier. Sistem kongruensi linier n variabel adalah gabungan dari n kongruensi linier bermodulo sama yang masing-masing-masing memuat paling banyak n variabel.

Penyelesaian system kongruensi linier dapat dilakukan dengan substitusi, eliminasi, atau dengan menggunakan matriks dan determinan.

Marilah kita mulai pembahasan tentang sistem kongruensi linier ini dengan sebuah peragaan, yaitu kita akan mencari semua bilangan bulat x dan y sehingga :

2x + 3y ≡ 7 (mod 11)

3x + 5y ≡ 6 (mod 11)

Jika kita menggunakan cara substitusi, maka 2x + 3y ≡ 7 (mod 11) diubah menjadi kongruensi 2x ≡ 7 – 3y (mod 11) atau 3y ≡ 2x (mod 11), kemudian disubstitusikan ke kongruensi 3x + 5y ≡ 6 (mod 11). Misalkan kita memilih 2x ≡ 7 – 3y (mod 11), maka  kita kalikan kedua ruas kongruensi dengan 6, sehingga diperoleh :

12x ≡ 42 – 18y (mod 11) , atau x ≡ 9 – 7y (mod 11).

Substitusi x ≡ 9 – 7y (mod 11) ke dalam 3x + 5y ≡ 6 (mod 11) diperoleh :

3(9 – 7y) + 5y ≡ 6 (mod 11) , atau  –16 y ≡ – 21 (mod 11), atau 6y ≡ 1 (mod 11),

atau y ≡ 2 (mod 11)

Dengan demikian x ≡ 9 – 7.2 (mod 11) ≡ – 5 (mod 11) ≡ 6 (mod 11)

Jadi sistem kongruensi linier mempunyai selesaian x ≡ 6 (mod 11) dan y ≡ 2 (mod 11)

Selesaian x dan y yang diperoleh dapat diperiksa kebenarannya dengan mensubstitusi kannya ke dalam masing-masing kongruensi linier.

Jika kita menggunakan cara eliminasi, maka kita perlu menetapkan lebih dahulu yang dieliminasi, yaitu x atau y. Misalkan kita tetapkan y dieliminasi, maka kongruensi pertama dikalikan 5 dan kongruensi kedua dikalikan 3, sehingga diperoleh :

10x + 15y ≡ 35 (mod 11)

9x + 15y ≡ 18 (mod 11)

Jika kongruensi pertama dikurangi kongruensi kedua, maka diperoleh :

x ≡ 18 (mod 11) , atau x ≡ 6 (mod 11)

Dengan jalan yang sama, jika x yang dieliminasi, maka kongruensi pertama dikalikan 3 dan kongruensi kedua dikalikan 2, sehingga diperoleh :

6x + 9y   ≡ 21 (mod 11)

6x + 10y ≡ 12 (mod 11)

Jika kongruensi kedua dikurangi kongruensi pertama, maka diperoleh :

y ≡ – 9 (mod 11) , maka y ≡ 2 (mod 11)

Dengan cara substitusi ini kita dapat menyelesaikan sebarang system kongruensi linier dua variabel.

 

Teorema 4.6

Ditentukan a,b,c,d,e,f,m  Z , m > 0 , dan  = ad – bc sehingga (,m) = 1

Sistem kongruensi linier :

ax + by ≡ e (mod m)

cx + dy ≡ f (mod m)

mempunyai suatu selesaian tunggal yaitu :

x ≡ (de – bf) (mod m)

y ≡ (af – ce) (mod m)

dimana  adalah inverse dari  modulo m .

Bukti :

Jika y akan dieliminasi, maka kongruensi pertama dikalikan d  dan  kongruensi  ke-

dua dikalikan b , sehingga diperoleh :

adx + bdy ≡ de (mod m)

bcx + bdy ≡ bf (mod m)

Jika kongruensi pertama dikurangi kongruensi kedua, maka diperoleh :

(ad – bc)x ≡ (de – bf) (mod m) atau  x ≡ (de – bf) (mod m)  sehingga

x ≡  (de – bf) (mod m)

Karena  ≡1 (mod m), maka diperoleh x ≡  (de – bf) (mod m)

Selanjutnya, jika x akan dieliminasi, maka kongruensi pertama dikalikan c dan

kongruensi kedua dikalikan a , sehingga diperoleh :

acx + bcy ≡ ce (mod m)

acx + ady ≡ af (mod m)

Jika kongruensi kedua dikurangi kongruensi pertama, maka diperoleh :

(ad – bc)y ≡ (af – ce) (mod m) atau y ≡ (af – ce) (mod m) sehingga

y ≡  (af – ce) (mod m)

Karena  ≡1 (mod m), maka diperoleh y ≡  (af – ce) (mod m)

 

Contoh 4.14

Selesaikan system kongruensi linier :

4x – 7y ≡ 6 (mod 17)

5x + 2y ≡ 9 (mod 17)

Jawab :

= 4.2 – (-7)(5) = 43 ≡ 9 (mod 17) dan = 2 , sebab = 18 ≡ 1 (mod 17)

Dengan demikian x ≡ (de – bf) (mod m) ≡ 2 (2.6 + 7.9) (mod 17) ≡ 14 (mod 17)

dan y ≡ (af – ce) (mod m) ≡ 2 (4.9 – 5.6) (mod 17) ≡ 12 (mod 17)

Pemeriksaan : jika  x = 14 dan y = 12 disubstitusikan pada masing-masing kongru-

ensi diperoleh 4x – 7y = 56 – 84 =  – 28 ≡ 6 (mod 17) dan

5x + 2y = 5.14 + 2.12 = 70 + 24 = 94 ≡ 9 (mod 17)

 

Untuk menyelesaikan sistem kongruensi linier 3 variabel atau lebih dengan cara elimi-

nasi memerlukan langkah-langkah yang lebih  panjang  karena tahapan  memperoleh x

melalui eliminasi variabel-variabel yang lain.

Cara menyelesaikan sistem kongruensi  linier n variabel  yang  relative  mudah  adalah

dengan menggunakan aljabar linier, yaitu persamaan matriks.

 

 

 

Definisi 4.3

Ditentukan A dan B adalah  matriks-matriks  berukuran p x q  dengan  unsur-unsur

bulat, aij merupakan unsur A pada baris ke i kolom ke j , dan bij merupakan unsur B

pada baris ke i kolom ke j.

A disebut kongruen dengan B modulo m jika aij ≡ bij (mod m) untuk semua pasang-

an (i,j) dengan 1 ≤ i ≤ n dan 1 ≤ j ≤ n , ditulis A ≡ B (mod m)

 

Contoh 4.15

(a)      ≡       (mod 13)

(b)        ≡        (mod 7)

 

Teorema 4.7

Jika A dan B adalah matriks-matriks berukuran p x q , A ≡ B (mod m) , dan C ada-

lah suatu matriks berukuran q x r , D adalah suatu matriks berukuran r x p , semua-

nya dengan unsur-unsur bulat, maka AC ≡ BC (mod m) dan DA ≡ DB (mod m)

Bukti :

Misalkan unsur-unsur A adalah aij , unsur-unsur B adalah bij  dengan 1 ≤ i ≤  p dan

1 ≤  j ≤  q , dan unsur-unsur C adalah cij dengan 1 ≤  j  ≤ q dan 1 ≤  j ≤r.

Unsur AC dan BC pada baris ke i kolom ke j  berturut-turut adalah :

dan  ,  1 ≤  i  ≤  p dan 1 ≤  j  ≤  r

Diketahui bahwa A ≡ B (mod m) , maka sesuai definisi 4.3 , aik ≡ bik (mod m) untuk

semua i dan k, yaitu :

=  ,  1 ≤  i  ≤  p dan 1 ≤  j  ≤  r

Akibatnya, AC ≡ BC (mod m).

Dengan jalan yang sama, buktikan DA ≡ DB (mod m).

 

 

 

 

Contoh 4.16

Diketahui : A dan B keduanya berukuran 3 x 2 , A =      dan B =

 

C berukuran 2 x 4, D berukuran 2 x 3 , C =     dan D =

 

AC =         =       ≡        (mod 8)

BC =         =        ≡      (mod 8)

DA =           =   ≡    (mod 8)

DB =           =   ≡    (mod 8)

Perhatikan bahwa AC ≡ BC (mod 8) dan DA ≡ DB (mod 8)

 

Marilah sekarang kita lihat cara memperoleh selesaian sistem kongruensi linier dengan menggunakan persamaan matriks, suatu cara yang serupa dengan cara memperoleh selesaian sistem persamaan linier di dalam aljabar (linier).

Secara umum, suatu sistem kongruensi linier dapat dinyatakan sebagai :

a11x1  + a12x2 + … + a1nxn ≡ b1 (mod m)

a21x1  + a22x2 + … + a2nxn ≡ b2 (mod m)

.            .        …        .                .

.            .        …        .                .

.            .        …        .                .

an1x1  + an2x2 + … + annxn ≡ bn (mod m)

 

Dalam bentuk persamaan matriks, sistem kongruensi linier ini dapat ditulis dengan :

AX ≡ B (mod m)

dimana :

 

A =                    ,    X =    ,  dan   B =  

 

 

Contoh 4.17

Suatu sistem kongruensi linier :

2x + 3y + 4z ≡ 2 (mod 11)

3x + y + 2z   ≡ 7 (mod 11)

4x + 2y + z   ≡ 3 (mod 11)

dapat dinyatakan sebagai :

=     (mod 11)

 

Selesaian sistem kongruensi linier :

A X ≡ B (mod m)

diperoleh dari :

A-1 A X ≡ A-1 B (mod m) , A-1 adalah inverse A modulo m

       I X ≡ A-1 B (mod m) , I adalah matriks identitas

       X ≡ A-1B (mod m)

dengan A-1 didefinisikan sebagai berikut :

 

 

 

 

Definisi 4.4

Jika A dan A-1 adalah matriks-matriks dengan unsur-unsur bilangan bulat, dan

berukuran n x n , serta A-1A ≡ A A-1 ≡ 1 (mod m), dengan :

I =                   adalah matriks identitas berderajad n ,

       maka A-1 disebut inverse matriks A modulo m .             

 

Teorema 4.8

Diketahui suatu matriks :

A =

dengan unsur-unsur bilangan bulat,  = det A = ad – bc , dan (,m) = 1.

Maka inversi matriks A modulo m adalah :

A-1 = -1

dengan -1  adalah inversi  modulo m

Bukti :

       Untuk membuktikan A-1 adalah inversi A modulo m, kita harus membuktikan  bah-

wa AA-1 ≡ A-1A (mod m)

AA-1 ≡   -1    ≡ -1

-1     ≡     ≡     ≡ 1 (mod m)

Dengan jalan yang sama, buktikan bahwa A-1A ≡ I (mod m)

 

Contoh 4.18

Diketahui A =     , dengan demikian  = 5.8 – 7.3 = 19

Inversi dari = 19  modulo 11 adalah -1 = 7 sebab -1 = 19.7 = 133 ≡ 1 (mod 11)

Jadi inversi A adalah A-1 = 7    =     ≡     (mod 11)

 

Selanjutnya, seperti uraian yang telah kita pelajari  dalam  aljabar linier, terutama  pada

topic matriks dan determinan, kita mengenal dan memahami tentang matriks adjoit dan

dan rumusan mencari inversi matriks dengan menggunakan matriks adjoit dan determinan. Secara rinci Anda dipersilahkan membaca ulang materi-materi itu, termasuk di antaranya minor dan kofaktor.

 

Definisi 4.5

Ditentukan A adalah suatu matriks berukuran n x n

Adjoit dari matriks A, ditulis adj A, adalah suatu matriks berukuran n x n  yang un-

ur-unsurnya adalah   dimana  sama dengan (-1)i+j dikalikan determinan suatu

matriks yang diperoleh dengan menghapus semua unsur A pada baris  ke i  dan  ko-

lom ke j

Teorema 4.9

Jika A adalah suatu matriks berukuran n x n dan A bukan matriks nol , maka

A (adj A) = I

Buktikan (lihat di buku-buku aljabar linier)

 

Teorema 4.10

Jika  A adalah  suatu  matriks  berukuran  n x n dan  semua  unsur-unsurnya  ada-

lah bilangan  bulat, serta m  adalah  bilangan  bulat  positif  sehingga  (,m) = 1,

maka inversi dari A adalah :

A-1 = -1 (adj A)

Bukti :

Karena (,m) = 1 , maka 0, dan sesuai teorema 4.9 , A (adj A) = I

Selanjutnya, dari (,m) = 1 dapat ditentukan bahwa  mempunyai inverse -1

modulo m, sehingga :

A (-1) (adj A) ≡ A (adj A) -1 = (I) -1-1 I  ≡ I (mod m) , dan

-1 (adj A) A ≡ -1 (adj A . A ) ≡ -1  I  ≡ I (mod m)

Jadi -1 (adj A) adalah inversi A, atau A-1 = -1 (adj A)

Contoh 4.19

Diketahui A =       , maka  = 4 , dan -1 ≡ 3 (mod 11)

A-1 = -1 (adj A) = 3        =

≡        (mod 11)

Pemeriksaan :

AA-1 =              =

≡        (mod 11)

 

Sekarang kita dapat menggunakan inverse A modulo m untuk menyelesaikan suatu kongruensi linier :

A X ≡ B (mod m)

dimana (,m) = 1.

Berdasarkan teorema 4.10, karena (,m) = 1, maka A mempunyai invers, misalnya A-1

sehingga  jika kedua ruas A X ≡ B (mod m) dikalikan A-1 diperoleh :

A-1 (A X) = A-1 B (mod m)

(A-1 A) X = A-1 B (mod m)

I X = A-1 B (mod m)

X = A-1 B (mod m)

Dengan demikian selesaian kongruensi linier simultan adalah  X = A-1 B (mod m)

 

Contoh 4.20

Selesaikan system kongruensi linier :

x + 2y + z ≡ 4 (mod 7), x – y + z ≡ 5 (mod 7), 2x + 3y + z ≡ 1 (mod 7)

Jawab :           =

A =         ,  X  =   ,  dan  B  =

= 3 , dan (,7) = (3,7) = 1 , maka -1 ≡ 5 (mod 7)

A-1 = -1 (adj A) = 5        =

X = A-1 B =        =  ≡

 

Tugas Dan Latihan

Tugas

Bacalah suatu buku tentang teori bilangan, misalnya Elementary Number Theory and Its Applications yang ditulis oleh Kenneth H. Rosen, dan diterbitkan oleh Addison-Wesley Publishing Company, carilah topik tentang Metode Monte Carlo.

Jelaskan topik itu terkait dengan masalah teori bilangan yang mana, bagaimana langkah-

langkahnya, dan berilah paling sedikit satu contoh.

Latihan

1. Selesaikan sistem kongruensi linier:

(a) x + 2y  ≡ 1 (mod 5)                (b) x + 3y  ≡ 1 (mod 5)

2x + y  ≡ 1 (mod 5)                     3x + 4y ≡ 1 (mod 5)

2. Carilah inversi matriks A modulo 7 jika :

A =

 

3. Selesaikan sistem kongruensi linier :

x + y ≡ 1 (mod 7)

x + z ≡ 2 (mod 7)

y + z ≡ 3 (mod 7)

4. Selesaikan sistem kongruensi linier :

2x + 5y + 6z ≡ 3 (mod 7)

2y +   z ≡ 4 (mod 7)

x +  2y +  3z ≡ 3 (mod 7)

5. Carilah matriks T jika :

T ≡         (mod 5)

dan semua unsur T adalah bilangan-bilangan bulat tidak negative kurang dari 5

 

Rambu-Rambu Jawaban Tugas dan Latihan

Rambu-Rambu Jawaban Tugas

Metode Monte Carlo adalah suatu metode pemfaktoran yang didasarkan pada kongruensi dan dikembangkan oleh J.M. Pollard pada tahun 1974 (Rosen, 1993:156).

Ditentukan n adalah bilangan komposit yang relative cukup besar dan p adalah faktor prima n yang terkecil. Keinginan kita adalah memilih bilangan-bilangan bulat :

x0 , x1 , … , xs

sedemikian hingga mempunyai residu-residu non-negatif terkecil  modulo n yang berbeda, tetapi tidak untuk kejadian yang sama modulo p.

Misalkan kita sudah temukan xi dan xj , 0 ≤ i < j ≤ s sehingga xi ≡ xj  (mod p) tetapi xi tidak kongruen dengan xj modulo n , maka p │xi – xj  tetapi n tidak membagi xi – xj  sehingga (xi – xj , n) adalah faktor non-trivial dari n, dan dapat dicari dengan mudah menggunakan algoritma Euclides.

Untuk mencari bilangan-bilangan bulat xi dan xj digunakan langkah-langkah :

(a)    mulailah dengan suatu nilai awal (bibit) x0 yang dipilih secara random

(b)   ambil suatu polynomial f(x) dengan koefien-koefisien bulat dan berderajad lebih dari 1.

(c)    Hitunglah suku-suku xk , k = 1,2,3, … dengan menggunakan definisi rekursif :

xk+1 ≡ f(xk) (mod n) , 0 ≤ xk+1 , n

(d) Polinomial f(x) seharusnya mempunyai sifat bahwa barisan x0 , x1 , … , xs mem-

punyai tingkah laku seperti barisan random yang diinginkan.

Sebagai peragaan, ambil n = 8051.

(a)    ambil suatu nilai awal x0 = 2

(b)   ambil suatu polynomial f(x) = x2 + 1

(c)    Hitung xk secara ekursif

x0 = 2

x1 = f(x0) = f(2) = 22 + 1 = 5

x2 = f(x1) = f(5) = 52 + 1 = 26

x3 = f(x2) = f(26) = 262 + 1 = 677

x4 = f(x3) = f(677) = 6772 + 1 ≡ 7474 (mod 8051)

x5 = f(x4) = f(7474) = 74742 + 1 ≡ 2839 (mod 8051)

x6 = f(x5) = f(2839) = 28392 + 1 ≡ 871 (mod 8051)

dan seterusnya.

Berikutnya, berdasarkan definisi rekursif xk , jika d adalah suatu bilangan bulat positif, dan xi ≡ xj (mod d), maka :

xi+1 ≡ f(xi) ≡ f(xj) ≡ xj+1 (mod d)

Hal ini berarti barisan xk besifat periodik dengan periode (j – i) ,  xq ≡ xr (mod j – i ) dengan q ≥ i dan r ≥ j , dan akibatnya, jika s adalah bilangan bulat positif kelipatan j – i , maka xs ≡ x2s (mod d).

Untuk memperoleh suatu faktor dari n , kita cari fpb dari x2k – xk dan n , k = 1,2,3,…

yaitu setelah kita memperoleh k yang mana 1 < x2k – xk < n.

Secara praktis, apabila metode rho Pollard digunakan, polynomial yang sering dipilih adalah f(x) = x2 + 1, dan nilai awal yang dipilih adalah x0 = 2.

Contoh :

Dengan menggunakan metode rho Pollard (atau metode Monte Carlo), dengan x0 = 2 dan polynomial pembangkit f(x) = x2 + 1 untuk memperoleh factor non-trivial dari suatu bilangan komposit n = 8051.

Jawab :

       Dari hasil hitungan x0 , x1 , x2 , x3 , x4 , x5 , dan x6 di atas, dan berdasarkan hitungan

algoritma Euclides, dapat ditentukan bahwa :

(x2 – x1,8051) = (21,8051) = 1

(x4 – x2,8051) = (7448,8051) = 1

(x6 – x3,8051) = (194,8051) = 97

Jadi 97 adalah suatu faktor dari 8051.

Tingkah laku dari periodik dari barisan xi dengan x0 = 2 dan xi+1 = xi2 + 1 (mod 97)

dan i ≥ 1 , dapat terlihat seperti model berikut :

 

 

x2 = 26

 

 

x3 = 677 ≡ 95 (mod 97)

 

x1 = 5

x4 = 7474 ≡ 5 (mod 97)

 

 

 

x0 = 2

 

 

 

 

 

 

 

Rambu-Rambu Jawaban Latihan

1. (a) Ada tiga pilihan cara menyelesaikan : substitusi, eliminasi, atau matriks.

Misalkan digunakan cara substitusi.

x + 2y ≡ 1 (mod 5), atau x ≡ 1 – 2y (mod 5), substitusikan ke 2x + y ≡ 1 (mod 5)

diperoleh 2(1 – 2y) + y ≡ 1 (mod 5), atau  –3y ≡  – 1 (mod 5) , 2y ≡ 4 (mod 5),

sehingga y ≡ 2 (mod 5).

x ≡ 1 – 2.2 (mod 5) ≡ – 3 (mod 5), sehingga x ≡ 2 (mod 5)

(b) Misalkan digunakan cara eliminasi

x akan dieliminasi, maka kongruensi pertama dikalikan dengan 3, dan kongruensi

kedua tetap :

3x + 9y ≡ 3 (mod 5)

3x + 4y ≡ 2 (mod 5)

Jika kongruensi pertama dikurangi kongruensi kedua diperoleh :

5y ≡ 1 (mod 5)

Kongruensi tidak mempunyai selesaian sebab (5,5) = 5 tidak membagi 1

2.  = – 2 ≡ 5 (mod 7) , maka -1 ≡ 3 (mod 7)

A-1 = -1 (adj A) = 3        =        ≡

 

3. Gunakan persamaan matriks untuk menyelesaikan

≡  (mod 7)  atau  A X ≡ B (mod 7)

X ≡ A-1 B (mod 7) ≡        (mod 7) ≡ (mod 7) ≡

4.        ≡ (mod 7) atau A X ≡ B (mod 7)

X ≡ A-1 B (mod 7) ≡        (mod 7) ≡ ≡

5. T ≡         (mod 5) ≡    (mod 5) ≡    (mod 5)

 

Rangkuman

Berdasarkan seluruh paparan pada Kegiatan Belajar 2 ini, maka garis besar bahan yang dibahas meliputi Definisi, Teorema, dan penerapan dalam penyelesaian masalah terkait,

terutama tentang konsep sistem kongruensi linier , cara menyelesaikan system kongruensi linier yang terdiri dari substitusi, eliminasi, dan matriks, dan metode rho Pollard atau metode Monte Carlo untuk mencari factor prima suatu bilangan komposit dengan menggunakan kongruensi.

1. Definisi 4.3 tentang dua matriks A dan B yang kongruen modulo m

2. Definisi 4.4 tentang inversi suatu matriks A modulo m.

3. Definisi 4.5 tentang adjoint suatu matriks A modulo m

4. Teorema 4.6 tentang ketunggalan selesaian sistem kongruensi linier :

ax + by ≡ e (mod m)

cx + dy ≡ f (mod m)

jika (,m) = 1 dengan  = ad – bc

 

 

 

5. Teorema 4.7

Jika A dan B adalah matriks-matriks berukuran p x q , A ≡ B (mod m) , dan C ada-

lah suatu matriks berukuran q x r , D adalah suatu matriks berukuran r x p , semua-

nya dengan unsur-unsur bulat, maka AC ≡ BC (mod m) dan DA ≡ DB (mod m)

6. Teorema 4.8

    Inversi matriks A =    adalah A-1 = -1

7. Teorema 4.9

    Jika A adalah suatu matriks berukuran n x n dan A bukan matriks nol , maka

A (adj A) = I

8. Teorema 4.10

Jika  A adalah  suatu  matriks  berukuran  n x n dan  semua  unsur-unsurnya  ada-

lah bilangan  bulat, serta m  adalah  bilangan  bulat  positif  sehingga  (,m) = 1,

maka inversi dari A adalah :

A-1 = -1 (adj A)

 

Tes Formatif 2

1. Skor 10

Selesaikan system kongruensi linier :

(a) 4x +   y ≡ 2 (mod 5)

2x + 3y ≡ 1 (mod 5)

(b) 2x + 3y ≡ 5 (mod 5)

x + 5y ≡ 6 (mod 5)

2. Skor 20

Carilah inversi dari A modulo 7 jika :

A =

3. Skor 20

Selesaikan sistem kongruensi linier :

x + y + z ≡ 1 (mod 7)

x + y + w ≡ 1 (mod 7)

x + z + w ≡ 1 (mod 7)

y + z + w ≡ 1 (mod 7)

4. Skor 10

Carilah banyaknya selesaian tidak kongruen dari sistem kongruensi linier :

2x  +  3y  +  z   ≡ 3 (mod 5)

x  +  2y  +  3z   ≡ 1 (mod 5)

2x  + z  ≡ 1 (mod 5)

5. Skor 15

Carilah pemfaktoran prima dari 1927  menggunakan metode rho Pollard dengan

x0 = 2 dan f(x) = x2 + 1

6. Skor 15

Carilah pemfaktoran prima dari 1387 menggunakan metode rho Pollard dengan

x0 = 3 dan f(x) = x2 + 1

 

Cocokkanlah jawaban Anda dengan Rambu-Rambu atau Kunci Jawaban Tes Formatif 2 yang terdpat di bagian akhir modul ini. Kemudian perkirakan skor jawaban Anda yang menurut Anda benar, dan gunakan kriteria berikut untuk mengetahui tingkat penguasaan Anda terhadap materi Kegiatan Belajar 2.

Skor Jawaban Yang Benar

Tingkat Penguasaan =  ————————————   x   100 %

100

Tingkat Penguasaan Anda dikelompokkan menjadi :

Baik sekali      :    90 % – 100 %

Baik                :     80 % – 89 %

Cukup             :     70 % – 79 %

Kurang            :     < 70 %

 

Apabila Anda mencapai tingkat penguasaan 80 % atau lebih, maka Anda dapat meneruskan ke Modul 5. Bagus !

Jika tingkat penguasaan Anda kurang dari 80 %, maka seharusnya Anda mengulangi materi Kegiatan Belajar 2, terutama pada bagian-bagian yang belum Anda pahami dan kuasai dengan baik. Selamat Belajar !

 

 

 

 

Rambu-Rambu Jawaban Tes Formatif

Rambu-Rambu Jawaban Tes Formatif 1

1. (a) 23x ≡ 17 (mod 180)

(23,180) = 1│17, maka kongruensi linier mempunyai satu selesaian.

23x  ≡ 17 (mod 180)         x0  =

—————————

180y ≡ -17 (mod 23)

19y   ≡ -17 (mod 23)          y0 =

—————————

23z   ≡  17  (mod 19)

4 z    ≡  17  (mod 19)           z0  =

————————–

19r   ≡  -17   (mod 4)

3r   ≡   3 (mod 4)                 r0 = 1

Penyelesaian : x ≡ 79 (mod 180)

(b) 180 = 4.5.9, maka kongruensi linier dapat dinyatakan dalam sistem kongruensi

linier simultan :

23x ≡ 17 (mod 4) , atau x ≡ 3 (mod 4)

23x ≡ 17 (mod 5) , atau x ≡ 4 (mod 5)

23x ≡ 17 (mod 9) , atau x ≡ 7 (mod 9)

Dengan demikian dapat dicari b1 , b2 , dan b3 :

5.9b1 ≡ 1 (mod 4) , maka b1 = 1

4.9b2 ≡ 1 (mod 5) , maka b2 = 1

4.5b3 ≡ 1 (mod 9) , maka b3 = 5

x = 5.9.1.3 + 4.9.1.4 + 4.5.5.7 = 979

Jadi : x ≡ 79 (mod 180)

2. Permasalahan banyaknya butir berlian dalam kantung dapat dinyatakan dalam suatu

bentuk sistem kongruensi linier simultan. Misalkan banyaknya butir berlian dalam

kantung adalah x, maka keadaan pertama dapat dinyatakan dengan x ≡ 5 (mod 13).

Setelah terjadi 4 orang terbunuh, maka keadaan kedua dapat dinyatakan dengan

x ≡ 6 (mod 9). Demikian seterusnya sehingga diperoleh lagi dua kongruensi linier

yaitu x ≡ 3 (mod 7) dan x ≡ 0 (mod 5).

9.7.5b1  ≡ 1 (mod 13) , b1 = 9

13.7.5b2 ≡ 1 (mod 9) ,   b2 = 2

13.9.5b3 ≡ 1 (mod 7) ,   b3 = 2

13.9.7b4 ≡ 1 (mod 5) ,   b4 = 4

x = 9.7.5.9.5 + 13.7.5.2.6 + 13.9.5.2.3 + 13.9.7.4.0 = 23145 ≡ 2670 (mod 4095)

Banyaknya butir berlian minimal dalam kantung adalah 2670

3. Sistem kongruensi linier simultan dapat dinyatakan dengan x ≡ 5 (mod 6) ,

x ≡ 7 (mod 11) , x ≡ 10 (mod 13) , x ≡ 3 (mod 5) , dan x ≡ 6 (mod 7) , sehingga :

11.13.5.7b1  ≡ 1 (mod 6) ,   b1 = 1

6.13.15.7b2 ≡ 1 (mod 11) , b2 = 6

6.11.5.7b3   ≡ 1 (mod 13) , b3 = 3

6.11.13.7b4 ≡ 1 (mod 5) ,   b4 = 1

6.11.13.5b5 ≡ 1 (mod 7) ,   b5 = 6

x = 11.13.5.7.5.1 + 6.13.15.7.7.6 + 6.11.5.7.10.3 + 6.11.13.7.3.1 + 6.11.13.5.6.6

= 25025 + 114660 + 69300 + 18018 + 154440 = 381443 ≡ 21083 (mod 30030)

4. Dengan cara biasa dapat dibuat barisan-bilangan yang memenuhi masing-masing

kongruensi , kemudian dicari suku atau unsur yang sama.

9x ≡ 4 (mod 14) , maka  x ≡ 2,16,44,58,72,86,100, …,310, … (mod 14)

5x ≡ 17 (mod 21), maka x ≡ 16,37,58,79,100, … ,310, … (mod 21)

7x ≡ 10 (mod 20), maka x ≡ 10,30,50,70, …,310, … (mod 20)

x ≡ 310 (mod 14) , x ≡ 310 (mod 21) , dan x ≡ 310 (mod 30), maka :

x ≡ 310 (mod [14,21,30]) ≡ 310 (mod 420)

Coba kerjakan dengan cara iterasi, untuk memeriksa apakah hasilnya sama.

5. Misalkan bilangan itu adalah x , maka :

x ≡ 0 (mod 13), x ≡ 2 (mod 3), x ≡ 2 (mod 5), x ≡ 2 (mod 7), x ≡ 2 (mod 8),

dan x ≡ 10 (mod 17)

Dari x ≡ 2 (mod 3), x ≡ 2 (mod 5), x ≡ 2 (mod 7), dan x ≡ 2 (mod 8) dapat ditentukan

bahwa x ≡ 2 (mod [3,5,7,8]), atau x ≡ 2 (mod 840).

Dengan demikian terdapat sistem kongruensi linier simultan x ≡ 0 (mod 13),

x ≡ 2 (mod 840), dan x ≡ 10 (mod 17)

840.17b1 ≡ 1 (mod 13) , b1 = 11

13.17b2 ≡ 1 (mod 840) , b2 = 821

13.840b3 ≡ 1 (mod 17) , b3 = 3

x = 840.17.0.11 + 13.17.2.821 + 13.840.10.3 = 690482 ≡ 133562 (mod 185640)

6. Langkah pertama adalah mencari (26733,54340) dengan menggunakan Algoritma

Euclides : 54340 = 2.26733 + 874

26733 = 30.874 + 513

874    = 1.513 + 361

513    = 1.361 + 152

361    = 2.152 + 57

152    = 2.57 + 38

57      = 1.38 + 19

38      = 2.19 + 0

(26733,54340) = 19│133 , maka kongruensi linier mempunyai 19 selesaian.

26733x ≡ 133 (mod 54340)

1407x   ≡ 7 (mod 2860)             x0  =

——————————

2860y  ≡ -7 (mod 1407)

46y      ≡ -7 (mod 1407)            y0  =

——————————

1407z  ≡  7 (mod 46)

27z      ≡  7 (mod 46)                 z0  =

————————–

46r      ≡ -7 (mod 27)

19r      ≡ -7 (mod 27)                 r0  =

————————-

27s     ≡  7 (mod 19)

8  s     ≡  7 (mod 19)                  s0  =

————————

19 t    ≡ -7 (mod 8)

3 t      ≡ -7 (mod 8)                     t0  =

———————–

8 k     ≡  7 (mod 3)

2 k     ≡  1 (mod 3)                       k0 = 2

Penyelesaian : x ≡ 1181,4041,6901, … , 52661 (mod 54340)

Rambu-Rambu Jawaban Tes Formatif 2

1. (a) 4x +   y ≡ 2 (mod 5) , maka y ≡ 2 – 4x (mod 5)

2x + 3y ≡ 1 (mod 5) , maka 2x + 3(2 – 4x) ≡ 1 (mod 5), –10x ≡  – 5 (mod 5)

atau 10x ≡ 5 (mod 5), dengan demikian x ≡ 0,1,2,3,4 (mod 5), sehingga

y ≡ 2,3,4,0,1 (mod 5)

(b) 2x + 3y ≡ 5 (mod 5)

x + 5y ≡ 6 (mod 5)

2. Semua selesaian adalah : (0,4), (1,1), (2,5), (3,2), (4,6), (5,3), dan (6,0)

3.               ≡  (mod 7)

≡               (mod 7) ≡  (mod 7)

4. Jika kongruensi pertama dikurangi kongruensi ketiga, maka diperoleh :

3y ≡ 2 (mod 5) , atau y ≡ 4 (mod 5)

Selanjutnya, jika x = 0,1,2,3,4 , maka  diperoleh z = 1,4,2,0,3

Jadi terdapat lima selesaian tidak kongruen (0,4,1), (1,4,4) , (2,4,2) , (3,4,0) , (4,4,3)

5.  x0 = 2

x1 = f(x0) = f(2) = 22 + 1 = 5

x2 = f(x1) = f(5) = 52 + 1 = 26

x3 = f(x2) = f(26) = 262 + 1 = 677

x4 = f(x3) = f(677) = 6772 + 1 ≡ 1631 (mod 1927)

x5 = f(x4) = f(1631) = 16312 + 1 ≡ 902 (mod 1927)

x6 = f(x5) = f(902) = 9022 + 1 ≡ 411 (mod 1927)

x7 = f(x6) = f(411) = 4112 + 1 = 1273 (mod 1927)

Ternyata, (x7 – x0 , 1927) = (1273 – 2 , 1927) = (1271 , 1927) = 41

Jadi 1927 = 41.47

6.  x0 = 3

x1 = f(x0) = f(3) = 32 + 1 = 10

x2 = f(x1) = f(10) = 102 + 1 = 101

x3 = f(x2) = f(101) = 1012 + 1 = 493 (mod 1387)

x4 = f(x3) = f(493) = 4932 + 1 ≡ 325 (mod 1387)

x5 = f(x4) = f(325) = 3252 + 1 ≡ 214 (mod 1387)

x6 = f(x5) = f(214) = 2142 + 1 ≡ 26 (mod 1387)

x7 = f(x6) = f(26) = 262 + 1 = 677 (mod 1387)

x8 = f(x7) = f(677) = 6772 + 1 = 620 (mod 1387)

x9 = f(x8) = f(620) = 6202 + 1 ≡ 202 (mod 1387)

x10 = f(x9) = f(202) = 2022 + 1 ≡ 582 (mod 1387)

x11 = f(x10) = f(582) = 5822 + 1 ≡ 297 (mod 1387)

x12 = f(x11) = f(297) = 2972 + 1 = 829 (mod 1387)

Ternyata, (x12 – x6 , 1387) = (829 – 26 , 1387) = (803 , 1387) = 73

Jadi 1387 = 73.19

 

Daftar Kepustakaan

Niven, I., Zuckerman, H.S., dan Montgomery, H.L. (1991). An Introduction to The

       Theory of Numbers. New York : John Wiley & Sons.

Redmond, D. (1996). Number Theory. New York : Marcel Dekker.

Rosen, K.H. (1993). Elementary Number Theory And Its Applications.

Massachusetts : Addison-Wesley.

 

 

 

 

 

 

 

Pengunjung datang dari kata kunci:

Leave a Reply