Teori Bilangan - Institut Teknologi Bandung

1 1 TeoriBilangan(Bagian2)BahanKuliahIF2120 MatematikaDiskritOleh: Rinaldi MunirProgram StudiTeknik InformatikaSTEI-ITBR inaldi M/IF2120 Matematika Diskrit2 SistemKekongruenanLinier Sistemkekongruenanlinier terdiridarilebihdarisatukekongruenan, yaitu: x a1(mod m1)x a2(mod m2)..x an(mod mn)Contoh: Sebuahbilanganbulatjikadibagidengan3 bersisa2 dan jikaiadibagidengan5 bersisa3. Berapakahbilanganbulattersebut?Rinaldi M/IF2120 Matematika Diskrit3 Penyelesaian:Misalbilanganbulat= xxmod 3 = 2 x 2 (mod 3)xmod 5 = 3 x 3 (mod 5)Jadi, terdapatsistemkekongruenan:x 2 (mod 3)(i)x 3 (mod 5)(ii)Untukkekongruenanpertama:x= 2 + 3k1(iii)Substitusikan(iii) kedalam(ii):2 + 3k1 3 (mod 5) 3k1 1 (mod 5) diperolehk1 2 (mod 5) atauk1= 2 + 5k2 Sebuahbilanganbulatjikadibagidengan3 bersisa2 dan jikaiadibagidengan5 bersisa3. Berapakahbilanganbulattersebut?

2 Rinaldi M/IF2120 Matematika Diskrit4 Substitusikank1= 2 + 5k2 kedalampersamaan(iii):x= 2 + 3k1= 2 + 3 (2 + 5k2)= 2 + 6 + 15k2= 8 + 15k2ataux 8 (mod 15) (periksabahwa8 mod 3 = 2 dan 8 mod 5 = 3)Semuanilaixyang kongruendengan8 (mod 15) juga adalahsolusinya, yaitux= 8, x= 23, x= 38, .., x= -7, dstSebuahbilanganbulatjikadibagidengan3 bersisa2 dan jikaiadibagidengan5 bersisa3. Berapakahbilanganbulattersebut?Rinaldi M/IF2120 Matematika Diskrit5 Chinese Remainder Problem PadaabadpertamaMasehi,seorangmatematikaw anChinayangbernamaSunTsemengajukanpertan yaansebagaiberikut:Tentukansebuahbilanga nbulatyangbiladibagidengan5menyisakan3,b iladibagi7menyisakan5,danbiladibagi11men yisakan7. Misakanbilanganbulattersebut= :x 3(mod5)x 5(mod7)x 7(mod11)Rinaldi M/IF2120 Matematika Diskrit6 Teorema5.(ChineseRemainderTheorem)Misalk anm1,m2,..,mnadalahbilanganbulatpositifs edemikiansehinggaPBB(mi,mj)=1untuki a1(modm1)x a2(modm2) x an(modmn)mempunyaisebuahsolusiunikdalamm odulusm=m1 m2.

3 Mn.(yaitu,terdapatsolusixdengan0 x<mdansemuasolusilainyangkongruendalammo dulusmdengansolusiini) daripertanyaanSun TsetersebutPenyelesaian:x 3 (mod 5) x= 3 + 5k1(i)Sulihkan(i) kedalamkongruenkedua( yaitux 5 (mod 7) ) menjadi:3 + 5k1 5 (mod 7) 5k1 2 (mod 7) k1 6 (mod 7), atauk1= 6 + 7k2(ii)Sulihkan(ii) kedalam(i): x= 3 + 5k1= 3 + 5(6 + 7k2) = 33 + 35k2(iii)Sulihkan(iii) kedalamkongruenketiga(yaitux 7 (mod 11) ) menjadi:33 + 35k2 7 (mod 11) 35k2 26 (mod 11) k2 9 (mod 11) atauk2= 9 + 11k3 Sulihkank2inikedalam(iii) menghasilkan:x= 33 + 35(9 + 11k3) = 348 + 385k3ataux 348 (mod 385). adalahbilanganbulatpositifterkecilyang merupakansolusi sistemkekongruenandi atas. Periksabahwabahwa348 mod 5 = 3, 348 mod 7 = 5, dan 348 mod 11 = 7. Perhatikanjuga bahwa385 = 5 7 3(mod5)x 5(mod7)x 7(mod11)Rinaldi M/IF2120 Matematika Diskrit8 Solusiunikini,yaitux 348(mod385),modulus385merupakanm=m1 m2 m3=5 7 11=385 Secaraumum,solusisistemkekongruenanlinie radalahberbentukx=a1M1y1+a2M2y2+.

4 + TinjaukembalipersoalanChineseremainderpr oblem: Hitung:m=5 7 11=385M1=7 11=77,M2=5 11=55,M3=5 7=35y1=3karena77 3 1(mod5)y2=6karena55 6 1(mod7)y3=6karena35 6 1(mod11)makasolusiunikdarisistemkekongru enantersebutadalahx=a1M1y1+a2M2y2+a3M3y3 =3 77 3+5 55 6+7 35 6=3813 348(mod385)x 3(mod5)x 5(mod7)x 7(mod11)Rinaldi M/IF2120 Matematika Diskrit10 Bilangan Prima Bilanganbulatpositifp(p>1)disebutbilanga nprimajikapembaginyahanya1danp. M/IF2120 Matematika Diskrit11 Karenabilanganprimaharuslebihbesardari1, makabarisanbilanganprimadimulaidari2,yai tu2,3,5,7,11,13,.. Seluruhbilanganprimaadalahbilanganganjil ,kecuali2yangmerupakanbilangangenap. Bilanganselainprimadisebutbilangankompos it(composite).Misalnya20adalahbilanganko mpositkarena20dapatdibagioleh2,4,5,dan10 , M/IF2120 Matematika Diskrit12 Teorema6.(TheFundamentalTheoremofArithme tic).

5 3100=2 2 5 513=13(atau1 13)Rinaldi M/IF2120 Matematika Diskrit13 Tesapakahnbilanganprimaataukomposit:(i)b agindengansejumlahbilanganprima,mulaidar i2,3,..,bilanganprima n.(ii)Jikanhabisdibagidengansalahsatudar ibilanganprimatersebut,makanadalahbilang ankomposit,(ii)tetapijikantidakhabisdiba giolehsemuabilanganprimatersebut, M/IF2120 Matematika Diskrit14 (i)171dan(ii) :(i) 171= 171adalah2,3,5,7,11, ,maka171adalahbilangankomposit.(ii) 199 = Bilanganprima yang 199 adalah2, 3, 5, 7, 11, 199 tidakhabisdibagi2, 3, 5, 7, 11, dan 13, maka199 M/IF2120 Matematika Diskrit15 Teorema6(TeoremaFermat).Jikapadalahbilan ganprimadanaadalahbilanganbulatyangtidak habisdibagidenganp,yaituPBB(a,p)=1,maka: ap 1 1(modp) MenurutteoremaFermatdiatas,jikapadalahbi langanprima,makaap 1 1(modp) Tetapi,jikapbukanbilanganprima,makaap 1 1(modp)FermatdibacaFairmaRinaldi M/IF2120 Matematika (17,2)=1danPBB(21,2)=1.

6 (i)217 1=65536 1(mod17)karena17habismembagi65536 1=65535 Jadi,17prima.(ii)221 1=1048576 1(mod21)karena21tidakhabismembagi1048576 1= ,21bukanprimaap 1 1 (mod p)Rinaldi M/IF2120 Matematika Diskrit17 KelemahanTeoremaFermat:terdapatbilangank ompositnsedemikiansehingga2n 1 1(modn).Bilanganbulatsepertiitudisebutbi langanprimasemu(pseudoprimes). Contoh:341adalahkomposit(karena341=11 31)sekaligusbilanganprimasemu,karenamenu rutteoremaFermat,2340 1(mod341) Untunglahbilanganprimasemurelatifjarangt erdapat. , : Hitunglahsisapembagian22020 dibagidengan73 Penyelesaian: DenganmenggunakanteoremaFermat kitadapatmengetahuibahwa273 1 = 272 1 (mod 73).22020 (272 28 + 4) (mod 73) (272)28. 24(mod 73) (1)28. 24(mod 73) 24(mod 73) 16 (mod 73) = 16 Jadi sisa pembagiannya adalah 16 Rinaldi M/IF2120 Matematika Diskrit18 Contoh20: TigakemunculanterakhirkometHalley adalahpada tahun1835, 1910, dan 1986.

7 Kemunculanberikutnyadiprediksiakanterjad ipada tahun2061. DenganbantuanTeoremaFermat buktikanbahwa18351910+ 19862061 0 (mod 7)Jawaban: Karena PBB(7, 1835) = 1 dan PBB(7, 1986) = 1, makamemenuhisyaratTeoremaFermat. Selanjutnya, berdasarkanTeoremaFermat,18357 1 = 18356 1 (mod 7)18351910 (mod 7) 18356 318 + 2 (18356)318 18352(mod 7) (1)318 18352(mod 7) 18352(mod 7) 12(mod 7) 1 (mod 7)19867 1 = 19866 1 (mod 7)19862061 (mod 7) 19866 343 + 3 (19866)343 19863(mod 7) (1)343 19863(mod 7) 19863(mod 7) 53( mod 7) 125 (mod 7) 6 (mod 7)Jadi, 18351910+ 19862061(mod 7) 1(mod 7) + 6 (mod 7) 0 (mod 7)19ap 1 1 (mod p)Latihansoal(diambildarisoalkuisdan UAS) memilikibanyakpermen. Diaakanmembagipermenkepadateman-temannya . Jikadiamembagikepada7 orang temannyasecaramerata, makaakantersisa5permen. Jikadiamembagiseluruhnyasecarameratakepa da8 teman, tersisa3.

8 Jikaiamembagiseluruhnyasecarameratakepad a9 orang, akantersisa7 permen. Berapapaling sedikitjumlahpermenyang dimilikiHartono? mod 7 dan 52017mod 11 (a) GunakanTeoremaFermat untukmenghitung3302mod 5, 3302 mod 7, dan 3302 mod 11(b) Gunakanhasildari(a) dan Chinese Remainder Theorem untukmenghitungnilai3302 mod 385 (Petunjuk: 385 = 5 7 11)