TEORI BILANGAN - WordPress

Darma math@yahoo.comTEORI BILANGANSetelah mempelajari modul ini diharapakan kamu bisa :1Menggunakan algoritma Euclid untuk menyelesaikan masalah.2Menggunakan notasi kekongruenan.3Menggunakan teorema Fermat dan teorema Wilson.4Menggunakan teorema factor.5Menggunakan teorema sisa cinaMasalah :1Tentukan factor persekutuan terbesar dari 247 dan 229.2Tentukan sisa pembagian 22005 ketika dibagi dengan 13.3Tentukan dua digit terakhir dari 319994Tentukan bilangan x dimana ketika dibagi 5 menyisakan 2, ketika dibagidengan 3 menyisakan 2 dan ketika dibagi dengan 11 menyisakan 3.1.KETERBAGIANDedinisi 1 : bilangan bulat b membagi habis bilangan bulat a ditulis b I a, jika danhanya jika ada bilangan bulat q sehingga a b . q, jika b tidak membagi habisbilangan bulat a maka ditulis .Catatan 1 : perlu dipahami bahwa arti membagi habis jika sisanya adalah 0.ataudikatakan tidak memiliki sisa kecuali nol.Contoh 1 : 4 I 36 karena 36 4 . 9.-3I 18 karena 18 -3 . 63 10 karena tidak ada q sedemikian sehingga 3 q 10.Definisi 2 : semua bilangan bulat b habis dibagi oleh 0 atau bisa ditulis 0membagi semua sembarang bilangan bulat b ditulis 0 I b, b sembarang bilanganbulat. Hal ini karena 0 b. 0.Istilah lain yang memiliki arti sama dengan b I a adalah1b adalah factor dari a2b adalah pembagi a3a adalah kelipatan dari bteorema 1teorema 2teorema 3Teorema 4: jika a I b dan b I c maka a I c.: jika a I b dan a I c maka a I (b c): jika a I b maka a I bq untuk q sembarang bilangan bulat.: jika a I b dan a I c maka a I (bm cm), sembarang bilangan bulat m

Darma math@yahoo.comTeorema 5Teorema 6Teorema 7Teorema 8Contoh 2: jika m 0 maka a I b ma I mb.: jika a I b dan b I a maka a b atau a -b.: jika a I b dengan a dan b positif, maka a b.: jika a I b dan b 0 maka : 3x 81y 6z 36 w, dengan x, y, z dan w bilangan bulat, maka 3 Iw karena 3 membagi semua suku diruas kiri. (teorema 4)Tes keterbagian / cirri bilangan yang habis dibagi n digit.Habis dibagiCiri-ciri2Digit terakhirnya genap3Jumlah digitnya habis dibagidengan 34Dua digit terakhirnya habisdibagi dengan 45Digit terkhirnya 0 atau 56Jumlah dari semua digit habisdibagi 3 dan digit satuannyagenap7M habis dibagi 7, dimana Madalah bilangan yang lebih kecilyang berasal dari bilangan Nyang ditambahkan dua kali padadigit terakhir dari bilangan yangdibentuk dari sisa digit.8Tiga digit terakhir habis dibagidengan 89Jumlah digitnya habis dibagidengan 911Selisih digit-digit pada tempatganjil dan tempat genap adalah0.12Bilangan yang dibentuk dua digitterkhir habis dibagi 4 dan jumlahdigitnya habis dibagi 325Bilangan yang dibentuk dengan2 digit terkahir habis dibagi 25125Bilangan yang dibentuk dengan

Darma math@yahoo.com3 digit terakhir habis dibagi 125.Catatan : digit bisa diartikan banyak angka dasar dalam matematika yaitu 0, 1, 2,3, 4, 5, 6, 7, 8, 9.2.FAKTOR PERSEKUTUAN TERBESAR 1Kita tahu dengan menggunakan pemfaktoran atau mendata factor dari 30dan 105 kita bisa menemukan bahwa factor persekutuan terbesar dari 30 dan 105adalah 15. Dalam modul ini kita buat kesepakatan factor persekutuan terbesardisebut juga dengan Greats Common Divisor (Pembagi Bersama Terbesar) danselanjutnya disingkat gcd. Jadi fpb dari 30 dan 105 bisa kita tulis dengan gcd (30,105 ) 15. Dalam menentukan gcd bilangan 30 dan 105 sangatlah mudah, akantetapi bagaimana menentukan gcd dari masalah 1? Akan kita pelajari bersama.Definisi 2 : diberikan a, b yang keduanya tidak nol, maka gcd dari (a,b)adalah bilangan asli unik d sedemikian sehingga :1)d I a dan d I b2)jika ada c I a dan c I b , maka c I d.Catatan 2: syarat 1) adalah syarat d sebagai factor persekutuan dari a dan b,sedangkan syarat 2) adalah syarat d sebagai factor persekutuan terbesar dari adan b.Pemahaman 2 : factor-faktor dari 30 1, 2, 3, 5, 6, 10, 15 dan 30. Sedangkanfactor-faktor dari 105 adalah 1, 3, 5, 7, 15, 21, 35 dan 105. Kita bisa liahat saratpertama dipenuhi oleh 1, 3, 5, dan 15. Yang masing-masing membagi habis 30 dan105. Maka syarat kedua mengsyaratkan pembagi bersama yang dipilih adalah 15yang habis dibagi oleh c (1,3,5) yang tentu saja mudah dilihat kurang dari 15.Teorema 1 : jika gcd(a,b) d maka gcd (a : d, b :d) 1Teorema 2 : jika a qa r maka gcd (a,b) gcd(b,r)3.PEMBAGIAN BERSISATeorem 3 : untuk setiap pasangan bilangan bulat a dan b dimana b 0, selaluterdapat dengan tunggal pasangan bilangan bulat q dan r sehingga : ,0

Darma math@yahoo.comCatatan 3 :Catatan 1.1. Bilangan bulat a adalah bilangan yang dibagi, b adalah pembagi, qdisebut hasil bagi (quotient) dan r disebut sisa (remainder). Teorema ini dapatdiungkapkan dalam bahasa sehari-hari: bilangan bulat a dibagi oleh bilangan bulatb 0 maka ada bilangan bulat q sebagai hasil baginya dengan sisa r.Contoh 1. ketika 13 2. 6 1. Maka 13 adalah bilangan yang dibagi (a), 2 adalahbilangan pembagi (b), 6 adalah hasil bagi / quotient (q) dan 1 adalah sisa /remainder.4.ALGORITMA PEMBAGIAN (ALGORITMA EUCLID)Diberikan 0 dengan algoritma Euclid, kita dapatkan :a q b r ,0 r jika r 0 maka b I a jadi gcd (a,b) b; if r 0 ambil b and r1 dalampembagian algoritma kita dapatkan :b q r r ,0 r rjika r2 0, stop ; kita dapatkan gcd (a,b) r1 ; jika tidak , lanjutka proses inisampai mendapatkan sisa nol. Misalkan sisa nol diperoleh setelah n 1 langkah,maka :a q b r ,0 r b q r r ,0 r rr q r r ,0 r r.r q rr . r ,0 r q r r 0.Sekarang gcd (a,b) r

Darma math@yahoo.comContoh 4 : tentukan gcd dari (178, 312)Step 1 : 312 1 . 178 134Step 2 : 178 1 . 134 44Step 3 : 134 3. 44 2Step 4 : 44 22. 2 0Kita dapatkan gcd(178, 312) 2.Catatan 4: karena jika x I y maka –x I y. jadi gcd (178, 312) gcd (-178, 312) gcd(178, - 312) gcd ( - 178 , -312 ).Sekarang masalah pertama bisa anda kerjakan.5.KPKDefinisi 5 : jika a,b adalah anggota bilangan bulat maka kpk (a, b) ( , )Dari bahasan 4 kita dapat dengan mudah dapatkan kpk dari (178, 312) yaitu. 27768.6.KEKONGRUENANDefinisi 6.a : misalkan a, b dan m adalah bilangan bulat dengan m 0 makadikatakan bahwa a kongruen dengan b modulo m jika m membagi habis (a – b)dan ditulis a b (mod m).Contoh 6 : 25 1 (mod 4 ) karena (25 -1) habis dibagi 4, sedangkan 31 5(mod 6) karana (31 -5) tidak habis terbagi oleh 6.Catatan 6 : dari definisi a b (mod m) jika a –b habis terbagi oleh m atau kitabisa tulis m I (a-b) dibaca m membagi habis (a- b). berarti ada sembarang bilanganbulat c sehingga (a – b) m.c atau ekuivalen dengan a b m.c dengan csembarang bilangan bulat.

Darma math@yahoo.comPemahaman 6: n 7 (mod 8) ini bisa kita artikan 8 membagi habis n – 7 kitatulis 8 I n – 7. Dapat diartikan bahwa n – 7 8.c dimana c sembarang bilanganbulat atau dapat kita tulis n 7 8c. dengan c sembarang bilangan bulat.Teorema 1 : Jika a b (mod m) maka untuk sembarang bilangan x 1234berlaku(a x) (b x)(mod m)(a x) (b x)(mod m)(ax) (bx)(mod m)(a ) (b )(mod m), n N.Teorema 2 : jika a b (mod m)and c d(mod m). makaa c (b c)(mod m)2a c (b d)(mod m)3ac bd (mod m)contoh 6:Tentukanlah sisa , jika 20 dibagi 7?Pembahasan20 1 (7)20 ( 1) (7)20 1 (7)Jadi 20 7 bersisa 1.Catatan: usahakanlah untuk sisa adalah 1 atau – 1 karena akan mudah untukdi cari hasil perpangkatanya.1Masalah 3 : hitung dua digit terakhir dari 32002. Kita tentu tak cukup kertas danjuga umur kita terbatas jika menghitung dengan mengenumerasi. Kita gunakannotasi kekongruenan. Kita gunakan modulo 100.3 81 (mod 100)dan 3 9(mod 100)3 729 (mod 100) 29 (mod 100)Dan 3 261 (mod 100)atau 3 61 (mod 100), kita lanjutkan perhitungan,3 61 x 9 (mod 100) 49 (mod 100)Dan3 49 (mod 100)

Darma math@yahoo.com 2401 (mod 100) 1 (mod 100)Akhirnya diperoleh 3 (3 ) . 3 1. 3 (mod 100) 9 (mod 100)Jadi dua digit terakhir adalah 9.Catatan : untuk menghitung n digit terakhir gunakan 10n.7.TEOREMA FERMATTeorema 7 : jika a adalah bilangan prima dan n adalah relative prima dengan aatau gcd (n,p) 1. Maka n 1 (mod p) dan juga n n (mod p)Catatan 7: ini artinya n 1 dan juga np-n adalah kelipatan dari p.Contoh 7 : missal kita ingin menghitung berapa sisa 542 ketika dibagai dengan41 menrut teorema fermat karena 5 dan 41 saling prima atau gcd (5, 41 ) 1 makakita dapatkan 5 1 (mod 41) sehingga 5 1 (mod 41) selanjutnya 540.52 1. 52(mod 41 ) sehingga didapat sisanya adalah 25.8.TEOREMA WILSONTeorema 8 : jika p adalah bilangan prima, maka (p -1)! 1 0 (mod p).Catatan 8 : ini berarti bahwa (p-1)! 1 adalah sebuah kelipatan dari p.9.TEOREMA FAKTORTeorema: sembarang bilangan asli N dapat ditulis dalam suatu bentuk .dimanaadalah bilangan prima dan, , ., . . Dan , , ., adalah suatu bilangan bulat positif.Contoh: N adalah bilangan asli sehingga N/5 adalah sebuah bilangan kuadraddan N/2 adalah bilangan pangakat tiga, nilai terkecil dari N yang memenuhi N/ 33adalahSolusi: misalkan N 10. TEOREMA SISA CINA.Masalah: Pada abad pertama, seorang matematikawan China yang bernamaSun Tse mengajukan pertanyaan sebagai berikut: Tentukan sebuah bilangan bulat

Darma math@yahoo.comyang bila dibagi dengan 5 menyisakan 3, bila dibagi 7 menyisakan 5, dan biladibagi 11 menyisakan 7.Pertanyaan Sun Tse dapat dirumuskan kedalam system perkongruenan linier :x 3 (mod 5)kongruen linierx 5 (mod 7)x 7 (mod 11)teorema 9 : misalkan Misalkan m1, m2, , mn adalah bilangan bulatpositif sedemikian sehingga gcd(mi, mj) 1 untuk i j. Maka sistemx ak (mod mk)mempunyai sebuah solusi unik modulo m m1 m2 mn.Contoh 9.:Tentukan solusi dari pertanyaan Sun Tse di atas.Penyelesaian 9.1 :Menurut persamaan (5.6), kongruen pertama, x 3 (mod 5), memberikan x 3 5k1 untuk beberapa nilai k. Subtitusikan ini ke dalam kongruen kedua menjadi 3 5k1 5 (mod 7), dari sini kita peroleh k1 6 (mod 7), atau k1 6 7k2 untukbeberapa nilai k2. Jadi kita mendapatkan x 3 5k1 3 5(6 7k2) 33 35k2yang mana memenuhi dua kongruen pertama. Jika x memenuhi kongruen yangketiga, kita harus mempunyai 33 35k2 7 (mod 11), yang mengakibatkan k2 9(mod 11) atau k2 9 11k3. Subtitusikan k2 ini ke dalam kongruen yang ketigamenghasilkan x 33 35(9 11k3) 348 385k3 (mod 11). Dengan demikian, x 348 (mod 385) yang memenuhi ketiga konruen tersebut. Dengan kata lain, 348adalah solusi unik modulo 385. Catatlah bahwa 385 5 7 11.Solusi unik ini mudah dibuktikan sebagai berikut. Solusi tersebut modulo m m1 m2 m3 5 7 11 5 77 11 35. Karena 77 3 1 (mod 5), 55 6 1 (mod 7),dan 35 6 1 (mod 11), solusi unik dari sistem kongruen tersebut adalahx 3 77 3 5 55 6 7 35 6 (mod 385) 3813 (mod 385) 348 (mod 385)Penyelesaian 9.2Sebenarnya kita bisa pikirkan bahwa sebenarnya ini juga bisa kita tulis dengan

Darma math@yahoo.com3, 8, 13, 18, ., 3 5p5, 12, 19, ., 5 7q7, 18, 29, ., 7 11rDengan menyelesaiakan persamaan kita bisa peroleh kelipatan persekutuanterkecil yaitu 348. Tetapi penyelesaian ini kurang praktis dan hanya digunakanuntuk bilangan yang kecil dan persamaan yang sedikit. Maka kita butuhpersamaan yang lebih umum, selain denngan 2 cara diatas.Penyelesaian 9.3Teorema: misalkan kita ingin menemukan sebuah angka x yang menghasilkan :Sisa ketika dibagi dengan d1Sisa r2 ketika dibagi dengan d2 . .Dan bersisa rn ketika dibagi dengan dnDimana tidak ada dua pembagi d1, d2, ,dn memiliki sembarang factor bersama.Misalkan D d1 d2 dn dan y1 . sekarang jika kita ingin menemukan bilangansedemikian sehingga :), 1 1(Maka solusinya adalah 5.7.11 385 , dan dari y1 Dari soal diatas kita peroleh D , kitaperoleh385385385 77, 55, 355711Ini menyisakan mencari ai sehingga 77a1 -1 habis dibagi 5 kemudian a2 sehingga55a2-1 habis dibagi dengan 7, kemudian a3 sehingga 35a3 -1 habis dibagi dengan11. Sehingga mudah diperoleh bahwa 3, 6, (3)(77)(3) (6)(55)(5) (6)(35)(7) 693 1650 1470 3813.Sekarang sembarang bilangan dengan bentuk 3813 385k adalah sebuahpenyelesaian, tetapi untuk mendapatkan penyelesaian terkecil yang mungkin kita