Makalah Kelompok 11 - Teorema Sisa China [PDF]

Citation preview

TEORI BILANGAN CHINESE REMAINDER (TEOREMA SISA CHINA)



Dosen Pengampu : Dr. Ni Nyoman Parwati, S.Pd, Mpd.



Disusun Oleh : Kelompok 11 Kelas 2B Pendidikan Matematika



Ni Kadek Ayu Aristha Dewi



(2013011022)



I Gusti Ngurah Restu Pamungkas



(2013011028)



PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS PENDIDIKAN GANESHA SINGARAJA 2021



CHINESE REMAINDER (TEOREMA SISA CHINA)



Teorema 4.17 Ambil bilangan m 1 , m2 ,…, mr dinyatakan sebagai bilangan bulat positif yang relatif prima sepasang-sepasang, dan ambil bilangan bulat a1 , a2 , …, ar. Maka perkongruenan x ≡ ai(mod m i), i = 1,2,3,…,r mempunyai solusi simultan (serentak/bersama) modulo [𝑚 1, 𝑚 2 , …, 𝑚 𝑟]. Cara lain menyatakan teorema ini adalah: Sistem perkongruenan x ≡ 𝑎𝑖 (mod 𝑚 𝑖) dengan (𝑚 1, 𝑚𝑗) = 1 apabila i≠j mempunyai solusi simultan modulo [𝑚 1, 𝑚 2 , …, 𝑚 𝑟]. Bila 𝑚 1, 𝑚 2 , …, 𝑚 𝑟 tidak relatif prima sepasang-sepasang m, maka tidak mempunyai solusi kongruen modulo [𝑚 1, 𝑚 2 ,…, 𝑚 𝑟]. Bukti: Misalkan m = 𝑚 1, 𝑚 2, …, 𝑚 𝑟 maka



𝑚 𝑚𝑗



𝑚



𝑚



𝑗



𝑗



𝑚



= bilangan bulat (𝑚 , 𝑚𝑗 ) = 1. Maka ada bilangan bulat bi 𝑗



sehingga (𝑚 ) 𝑏𝑗 ≡ 1. Jelas bahwa (𝑚 ) 𝑏𝑗 ≡ 0 (mod mi) Didefinisikan 𝑥 0 sebagai berikut: 𝑚 𝑥 0 = ∑𝑟𝑗=1 𝑚 𝑏𝑗 𝑎𝑗 didapat 𝑗



𝑥 0 = ∑𝑟𝑗=1



𝑚 𝑏𝑎 𝑚𝑗 𝑗 𝑗



≡



𝑚 𝑚𝑗



𝑏𝑖 𝑎𝑗 ≡



𝑚 𝑚𝑗



𝑏𝑖 𝑎𝑖 ≡ 𝑎𝑗 (𝑚𝑜𝑑 𝑚 𝑖 )



Karena itu 𝑥 0 adalah solusi simultan dari sistem perkongruenan semula. Jika 𝑥 0 dan 𝑥 1 keduanya solusi simultan dari x ≡ 𝑎𝑖 (mod 𝑚 𝑖 ) dengan i = 1, 2, 3, …, r maka 𝑥 0 ≡ 𝑥 1 (mod [𝑚 1 , 𝑚 2 , … , 𝑚 𝑟 ]). Jika (𝑚 𝑖 , 𝑚𝑗 ) = 1 bila i≠j, maka sistem x ≡ 𝑐1 (𝑚𝑜𝑑 𝑚 1 ) x ≡ 𝑐2 (𝑚𝑜𝑑 𝑚2 ) … … … … … … … … …, x ≡ 𝑐𝑟 (𝑚𝑜𝑑 𝑚 𝑟 ), Memiliki solusi tunggal modulo m dengan m = ∑𝑟𝑖=1 𝑚 𝑖 Bukti: 𝑚



Andaikan 𝑀𝑖 = 𝑚 untuk setiap i. Maka 𝑚 𝑖 |𝑀𝑖 untuk i≠j. (𝑚𝑗 , 𝑀𝑖 ) = 1 karena (𝑚 𝑖 , 𝑚 𝑖 ) = 1 untuk 𝑖



i≠j. Karena (𝑚𝑗 , 𝑀𝑖 ) = 1 perkongruenan 𝑀𝑖 𝑦 ≡ 1 (𝑚𝑜𝑑𝑚 𝑖 ) Memiliki solusi 𝑏𝑖 utnuk setiap i, dengan kata lain untuk setiap i terdapat 𝑏𝑖 sedemikian hingga 𝑀𝑖 𝑏𝑖 ≡ 1 (𝑚𝑜𝑑 𝑚𝑖 ) Asumsikan 𝑥 0 = ∑𝑟𝑖=1 𝑐𝑖 𝑀𝑖 𝑏𝑖 . Kemudian, 𝑥 0 ≡ 𝑐𝑗 (𝑚𝑜𝑑 𝑚 𝑖 ) untuk setiap j karena 𝑐𝑗 𝑀𝑗 𝑏𝑗 ≡ 𝑐𝑗 (𝑚𝑜𝑑 𝑚𝑗 ) dan 𝑀𝑖 ≡ 0(𝑚𝑜𝑑 𝑚𝑗 ) untuk i≠j. Jadi, 𝑥 0 merupakan solusi dari sistem. Andaikan 𝑥 0 dan 𝑥 1 dua solusi dari sistem tersebut, maka 𝑥 0 ≡ 𝑐𝑖 ≡ 𝑥 1 (𝑚𝑜𝑑 𝑚𝑗 )



Dan 𝑚 𝑖 |(𝑥1 − 𝑥 0 ) utnuk setiap i. Kemudian, karena (𝑚 𝑖 , 𝑚𝑗 ) = 1 untuk i≠j, maka 𝑚|(𝑥 1 − 𝑥 0 ) atau 𝑥 1 ≡ 𝑥 0 (𝑚𝑜𝑑 𝑚) karena itu, solusinya tunggal modulo m. Contoh 4.23 Selesaikan sistem perkongruenan x ≡ 2 (mod 3) x ≡ 4 (mod 5) x ≡ 6 (mod 7) Penyelesaian 𝑚 1 , 𝑚 2 , dan 𝑚 3 relatif prima sepasang-sepasang, dengan 𝑚 1 = 3, 𝑚 2 = 5, 𝑚 3 = 7, dan 𝑚 = 3.5.7 = 105 𝑎1 = 2, 𝑎2 = 4, 𝑎3 = 6 𝑚 𝑏 ≡ 1 (𝑚𝑜𝑑 𝑚𝑖 ) (𝑚 ) 𝑖 𝑖



105 (3)



𝑏1 ≡ 1 (𝑚𝑜𝑑 3) ,



105 (5)



𝑏2 ≡ 1 (𝑚𝑜𝑑 5),



105 (7)



𝑏3 ≡ 1 (𝑚𝑜𝑑 7)



35𝑏1 ≡ 1 (𝑚𝑜𝑑 3), 21𝑏2 ≡ 1 (𝑚𝑜𝑑 5), 15𝑏3 ≡ 1 (𝑚𝑜𝑑 7) 2𝑏1 ≡ 1 (𝑚𝑜𝑑 3), 𝑏2 ≡ 1 (𝑚𝑜𝑑 5), 𝑏3 ≡ 1 (𝑚𝑜𝑑 7) 𝑏1 ≡ 2 (𝑚𝑜𝑑 3) 105 105 105 𝑥 0 ≡ 3 . 2.2 + 5 . 1.4 + 7 . 1.6 (𝑚𝑜𝑑 105) ≡ 35.4 + 21.4 + 15.6 (𝑚𝑜𝑑 105) ≡ 314 (𝑚𝑜𝑑 105) ≡ 104(𝑚𝑜𝑑 105)



5. Mereduksi Perkongruenan ax ≡ b (mod m) menjadi Sistem Perkongruenan ax ≡ b (mod 𝒎𝒊 ) Menyelesaikan perkongruenan ax ≡ b (mod m) untuk m bilangan besar dapat dengan cara mereduksi ax ≡ b (mod m) menjadi sistem perkongruenan ax ≡ b (mod 𝑚 𝑖 ) dimana 𝑚 1 , 𝑚 2 , … , 𝑚 𝑛 adalah faktor-faktor prima berpangkat dari m. kemudian diselesaikan dengan menggunakan teorema sisa. Contoh 4.24 Selesaikan 8377𝑥 ≡ 4213 (mod 900) Penyelesaian 900 = 4.9.25 sehingga 8377𝑥 ≡ 4213 (mod 900) direduksi menjadi 8377𝑥 ≡ 4213 (mod 4) 8377𝑥 ≡ 4213 (mod 9) 8377𝑥 ≡ 4213 (mod 25) Penyelesaian selanjutnya 8377𝑥 ≡ 4213 (mod 4) 8377 = 2049,4+1 4213 = 1052,4+1 𝑥 ≡ 1 (mod 4) 900 𝑏1 ≡ 1 (mod 4) 4 225 𝑏1 ≡ 1 (mod 4) 𝑥 ≡ 1 (mod 4) 𝑏1 ≡ 1 (mod 4)



8377𝑥 ≡ 4213 (mod 9) 7𝑥 ≡ 1 (mod 9) 𝑥 ≡ 4 (mod 9) 900 𝑏2 ≡ 1 (mod 9) 9 100 𝑏2 ≡ 1 (mod 9) 𝑏2 ≡ 1 (mod 9) 8377𝑥 2𝑥 𝑥 900 𝑏 25 3



8377 = 930,9+7



≡ 4213 (mod 25) 8377 = 335,25+2 ≡ 13 (mod 25) ≡ 19 (mod 25) ≡ 1 (mod 25)



36 𝑏3 ≡ 1 (mod 25) 11 𝑏3 ≡ 1 (mod 25) 𝑏3 ≡ 16 (mod 25) 900



900



900



𝑥 0 = 4 . 1.1 + 9 . 4.1 + 25 . 19.16 ≡ 1 (mod 900) 𝑥 0 ≡ 225 + 100.4 + 36.19.16 (mod 900) ≡ 225 + 400 + 10944 (mod 900) ≡ 11569 (mod 900) ≡ 769 (mod 900)



4213 = 468,9+1



4213 = 168,25+13