Pengantar Teori Bilangan I
Bilangan Bulat dan Operasinya Pembekalan dan pemahaman dasar tentang bentuk bilangan pada suatu
kelompok/set/himpunan salah satunya adalah bilangan bulat (yang lazim disebut sebagai integer dalam pemrograman) sudah diberikan pada Teori Himpunan. Pada Teori bilangan, integer akan kembali diulas lebih lanjut berikut dengan beberapa sifat bilangan bulat berikut serta operasinya. Hal fundamental ini perlu dikuasai dengan mantap karena akan terus digunakan pada sebagian besar algoritme yang akan dibahas pada bagian algoritme dan pemrograman. Contoh: Bilangan seperti apa yang masuk kedalam bilangan Bulat?, dan bukan yang termasuk dalam bilangan bulat? Bilangan bulat adalah bilangan yang tidak mempunyai pecahan desimal, misalnya 8, 21, 8765, -34, 0 Berlawanan dengan bilangan bulat adalah bilangan riil yang mempunyai titik desimal, seperti 8.0, 34.25, 0.02.
Penjumlahan Alkisah pada sekitar tahun 1787, seorang guru bertanya kepada kelas anak usia 10 tahun yang diasuhnya, βBerapakah jumlah total dari 100 bilangan bulat pertamaβ. Pertanyaannya itu mungkin dia ajukan secara iseng untuk membuat muridnya sibuk agar ia dapat mengerjakan tugas yang lain. Berapa lamakah waktu yang Anda butuhkan untuk menjawab pertanyaan tersebut? Masalah 1: Berapakah jumlah dari 1 + 2 + 3 + β¦ + 99 + 100? Di kelas itu ada seorang anak yang memiliki bakat luar biasa di bidang matematika.
Anak
itu
hanya
memerlukan
beberapa
menit
untuk
menyelesaikan masalah tersebut dengan mengelompokkan bilangan yang ada ke dalam 50 pasang bilangan dengan jumlah yang sama, 101: 1
(1 + 100) + (2+ 99) + β¦ + (50 + 51) = 101.50 = 5050 Anak tersebut bernama Carl Friedrich Gauss
(1777-1855), seorang
1
matematikawan tersohor sepanjang sejarah. Jika masalah tersebut diubah menjadi berapakah jumlah dari N bilangan bulat pertama, Anak tersebut kemungkinan tetap dapat menjawabnya dengan waktu yang cepat dengan menggunakan formula π
βπ = 1 + 2 + β―+ π β 1 + π = π=1
π(π + 1) 2
Persamaan tersebut dapat disesuaikan untuk menyelesaikan masalah serupa, misalnya: Masalah 2: Berapakah jumlah dari N bilangan genap positif pertama? Masalah 3: Berapakah jumlah dari N bilangan ganjil positif pertama? Masalah 2 dapat diselesaikan dengan mengalikan jumlah N bilangan positif pertama dengan 2 sehingga diperoleh formula π
π
β 2π = 2 β π = 2 (1 + 2 + β― + π β 1 + π) = 2 π=1
π=1
π(π + 1) = π(π + 1) 2
Masalah 3 dapat diselesaikan dengan mengurangi jumlah 2N bilangan bulat pertama dengan jumlah N bilangan genap pertama: π
2π
π
β 2π β 1 = β π β β 2π = π=1
π=1
π=1
2π(2π + 1) β π(π + 1) = π 2 2
Beberapa sifat penjumlahan yang perlu diketahui ialah: ο· Komutatif: urutan operand dapat ditukarkan tanpa mengubah hasil akhir. o A+B=B+A
1
https://en.wikipedia.org/wiki/Carl_Friedrich_Gauss
2
ο· Asosiatif: apabila terdapat tiga atau lebih operand, urutan pengerjaan tidak mengubah hasil akhir. o A + (B + C) = (A + B) + C ο· Identitas: penambahan bilangan bulat apapun dengan 0 tidak akan mengubah nilai bilangan tersebut. o A+0=0+A=A ο· Unit: agar operasi penjumlahan berarti, unit yang digunakan pada operand haruslah sama. Sebagai contoh, 3 meter ditambah 4 gram tidak dapat ditambahkan.
Pengurangan Beberapa sifat pengurangan yang perlu diketahui ialah: ο· Anti-Komutatif: apabila urutan operand ditukarkan, hasilnya menjadi negatif dari hasil asli. o A β B = - (B - A) ο· Non-Asosiatif: o A β (B β C) != (A β B) - C
Perkalian Suku-suku (atau operand) penjumlahan yang dilakukan berulang-ulang dapat ditulis dengan lebih singkat dalam bentuk perkalian. 3 . 4 = 4 + 4 + 4 = 12 Beberapa sifat perkalian yang perlu diketahui ialah: ο· Komutatif: A . B = B . A ο· Asosiatif: (A . B) . C = A . (B . C) ο· Distributif: A . (B + C) = A . B + A . C ο· Identitas: A . 1 = A ο· Unsur 0: A . 0 = 0 ο· Negasi: -1 . A = -A 1
ο· Invers: A . π΄ = 1
3
Pangkat Jika perkalian adalah serangkaian operasi penjumlahan, pemangkatan (atau eksponensiasi) adalah serangkaian operasi perkalian terhadap suku yang nilainya sama. Secara umum, pemangkatan ditulis dalam bentuk:
Bilangan yang lazim digunakan sebagai basis pemangkatan pada bidang ilmu komputer ialah 10 (10n) dan 2 (2n).Pemangkatan tidak bersifat komutatif. Artinya, ab β ba. Pemangkatan juga tidak bersifat asosiatif. Beberapa sifat dan bentuk pemangkatan dasar yang perlu dikuasai: ο· b1 = b ο· bm+n = bm . bn ο· (bm)n = bm.n ο· bn+1 = bn . b ο· b0 = 1 1
ο· b-n = ππ ο· (b . c)n = bn . cn Pemangkatan dapat dilakukan secara cepat dengan menggunakan teknik exponentiation by squaring yang didefinisikan sebagai berikut: xn = {
πβ1 , 2
π₯(π₯ 2 )
ππππ π ππππππππ ππππππ
π 2
(π₯ 2 ) , ππππ π ππππππππ πππππ
Faktorial N faktorial (ditulis sebagai N!) didefinisikan sebagai sebagai hasil perkalian bilangan-bilangan bulat postif yang kurang dari atau sama dengan N. Secara umum, N! dapat ditulis sebagai berikut: N! = N . (N-1) . (N-2) . β¦. 3 . 2 . 1
4
Faktorial juga dapat didefiniskan secara rekursif sebagai berikut: N! = {
1, ππππ π = 0 π. (π β 1)! ππππ π β₯ 1
Nilai dari 0! β 13! Disajikan pada tabel di bawah ini. Berdasarkan tabel tersebut, dapat dilihat bahwa nilai dari N! bisa menjadi sangat besar. Kalkulator standar pada umumnya hanya mampu menghitung hingga 13!. N
N!
N
N!
0
1
7
5040
1
1
8
40320
2
2
9
362880
3
6
10
3628800
4
24
11
39916800
5
120
12
479001600
6
720
13
6227020800
Latihan 1. Berapakah jumlah dari 1 + 2 + 3 + β¦ + 10? 2. Berapakah jumlah dari 1 + 2 + 3 + β¦ + 10000? 3. Berapakah jumlah dari 1 + 3 + 5 + 7 + β¦. + 21? 4. Berapakah jumlah dari 1 + 3 + 5 + 7 + β¦. + 999? 5. Setiap sel bakteri βExpiβ mampu bereplikasi setiap 1 jam sekali. Setiap kali bereplikasi, sel membelah menjadi dua. Dengan demikian, jika pada kondisi awal hanya terdapat 1 sel, satu jam berikutnya jumlah sel menjadi 2, satu jam berikutnya menjadi 4, menjadi 8, dan seterusnya. Apakah rumus untuk menentukan jumlah sel pada jam ke N? 6. Melanjutkan soal nomor 6. Berapakah jumlah sel pada jam ke 10? 5
7. Di dalam ruangan terdapat 20 orang yang saling berjabat tangan. Jika tiap dua orang berjabat tangan tepat 1 kali, berapakah jumlah jabat tangan yang terjadi di ruangan tersebut? 8. Berapakah nilai dari 210 + 25? 22
9. Berapakah hasil dari 22 ? 10. Dengan menggunakan teknik exponentiation by squaring, carilah nilai dari 216. 11. Jumlah dua digit pertama dari bilangan hasil perkalian 530003 Γ 810004 adalah 7!
12. Nilai dari 5!2! adalah? 100!
13. Nilai dari 98!2! adalah? 14. Hitunglah (80! Γ 38!) /(77! Γ 40!) Jawaban 1.
1 + 2 + 3 + β¦ + 10 dapat diselesaikan dengan menggunakan persamaan π(π+1) 2
dengan N bernilai 10 sehingga: 10(10+1) 2
2.
=
10(11) 2
= 55.11 = 155
1 + 2 + 3 + β¦ + 10000. Berdasarkan soal nomor 1, 3, dan 5, kita dapat melihat pola berikut: Jumlah untuk N = 10, jumlah total 55 Jumlah untuk N = 100, jumlah total 5050 Jumlah untuk N = 1000, jumlah total 500500 Berdasarkan pola tersebut, kita dapat menebak bahwa jumlah untuk N = 10000 ialah 50005000.
3.
1 + 3 + 5 + β¦ + 21 dapat diselesaikan dengan menggunakan persamaan N2 dengan N = 21. Berarti jumlahnya menjadi 212 = 441
6
4.
1 + 3 + 5 + β¦ + 99 dapat diselesaikan dengan menggunakan persamaan N2 dengan N = 99. Berarti jumlahnya menjadi 992 = 9801
5.
Untuk mendapatkan pola yang diminta pada soal ini, kita dapat memulainya dengan membuat tabel sederhana untuk nilai N yang kecil Waktu
Jumlah Sel
0
1 = 20
1
2 = 21
2
4 = 22
3
8 = 23
4
16 = 24
5
32 = 25
β¦
β¦
Berdasarkan tabel tersebut, kita dapat melihat bahwa hubungan antara waktu dengan jumlah sel pada waktu tersebut ialah 2N. 6.
Jumlah sel pada jam ke-10 setara dengan 210 yaitu 1024. Jadi, jumlah sel pada jam ke-10 ialah 1024 sel.
7.
Walaupun soal ini dapat diselesaikan dengan kombinasi, dengan pengamatan sederhana, soal ini dapat diselesaikan dengan menggunakan prinsip penjumlahan. Jika ada N orang pada ruangan, maka cara sistematis agar seluruh orang berjabat tangan tepat 1 kali ialah: ο·
Orang pertama akan berjabat tangan dengan N-1 orang lainnya.
ο·
Kemudian, orang kedua akan berjabat tangan dengan N-2 orang lainnya (karena dia sudah berjabat tangan dengan orang pertama.
ο·
Kemudian, orang ketiga akan berjabat tangan dengan N-3 orang (karena dia sudah berjabat tangan dengan orang kedua dan ketiga)
ο·
Orang terakhir tidak perlu lagi berjabat tangan.
7
Berarti jumlah jabat tangan yang terjadi ialah (N-1) + (N-2) + (N-3) + β¦ + 3 + 2 + 1 + 0. Barisan ini setara dengan penjumlahan sebanyak N-1 bilangan bulat pertama dengan rumus umum π β 1(π β 1 + 1) (π β 1)N = 2 2 Jika N=20, maka jumlah jabat tangan yang terjadi ialah sebanyak (20β1)20 2
= 21.10 = 210
8.
210 bernilai 1024 dan 25 bernilai 32. Jumlah keduanya ialah 1049.
9.
22
22
4
= 22 = 28 = 256.
10. 216 = (22)8 = 48 = (42)4 = (162)2 = 2562 = 65536. 11.
12.
13.
7! 5!2!
=
100! 98!2!
7.6.5!
=
5!2!
=
7.6.5! 5!2!
100.99.98! 98!2!
=
=
7.6 2!
=
100.99.98! 98!2!
42 2
=21
=
100.99 2
= 50.99 = 4950
14.
8
II
Keterbagian dan Hasil Bagi
Keterbagian Kita telah mengetahui bahwa 13 dibagi 5 hasil baginya 2 dan sisanya 3 dan ditulis sebagai : 13 5
3
= 2 + 5 atau 13 = 2 x 5 + 3
Secara umum, apabila a bilangan bulat dan b bilangan bulat positif, maka ada tepat satu bilangan bulat q dan r sedemikian hingga : a = qb + r , 0 < r < b, dalam hal ini, q disebut hasil bagi dan r sisa pada pembagian βa dibagi dengan bβ. Jika r = 0 maka dikatakan a habis dibagi b dan ditulis b|a. Untuk a tidak habis dibagi b ditulis b ditulis b Ε a. Lebih lanjut definisi untuk dua buah bilangan bulat A dan B, kita menyebut bahwa A membagi B jika B = A . C untuk sebuah bilangan bulat C. Hal ini kita tuliskan sebagai A|B. Kita juga dapat menyebut bahwa B dapat dibagi oleh A jika B merupakan kelipatan dari A. Karena 0 = A . 0, maka A|0 untuk seluruh bilangan bulat A, A β 0. Berdasarkan definisi tersebut, kita dapat melihat beberapa sifat berikut: ο·
Jika A|B, B β 0, maka |A| β€ |B|;
ο·
Jika A|B dan A|C, maka A|(ο‘B + ο’C) untuk bilangan bulat sembarang ο‘ dan ο’;
ο·
Jika A|B dan A|B Β± C, maka, A|C;
ο·
A|A (refleksivitas)
ο·
Jika A|B dan B|C, maka A|C (transivitas)
ο·
Jika AB|C maka A|C dan B|C
ο·
Jika A|B dan B|A, maka |A| = |B|
Contoh: 4 | 12 karena 12 οΈ 4 = 3 (bilangan bulat) atau 12 = 4 ο΄ 3. Tetapi 4 | 13 karena 13 οΈ 4 = 3.25 (bukan bilangan bulat)
9
Keterbagian oleh 2 Suatu bilangan habis dibagi 2n jika n bilangan terakhir dari bilangan tersebut habis dibagi 2n: A1
Untuk n = 1 berarti suatu bilangan habis dibagi 2 jika angka terakhir dari bilangan tersebut habis dibagi 2.
A2
Untuk n = 2 berarti suatu bilangan habis dibagi 4 jika 2 bilangan terakhir dari bilangan tersebut habis dibagi 4
A3
Untuk n = 3 berarti suatu bilangan habis dibagi 8 jika 3 bilangan terakhir dari bilangan tersebut habis dibagi 8.
Contoh: Tentukan apakah 173332 habis dibagi oleh : a). 2
b). 4
c). 8
Jawab: a). Karena 2|2 maka 2|173332 b). Karena 4|32 maka 4|173332 c). Karena 8 Ε 332 maka 8 Ε 173332
Keterbagian oleh 3 Misalkan bilangan yang akan dibagi adalah a = an an-1 an-2 β¦ a1 a0. B1. Bilangan a habis dibagi 3 jika jumlah angka-angkanya (an + an-1 + β¦ + a1+ a0) habis dibagi 3 Contoh: Tentukan apakah 1815 habis dibagi : a).3
b). 9
Jawab: Jumlah angka-angka 1815 = 1 + 8 + 1 + 5 = 15 a). Karena 3|15 maka 3|1815 b). Karena 9 Ε 15 maka 9 Ε 1815 Contoh: Bilangan berangka enam berikut a1989b habis dibagi 72. Tentukan a dan b Jawab: 72 = 8 x 9. Karena itu 8|a1989b ο b = 6 Juga 9|a + 1 + 9 + 8 + 9 + b = a = 33 ο a = 3
10
Masalah: Berapakah jumlah bilangan bulat positif yang bernilai kurang dari atau sama dengan 100 yang habis dibagi 5. Jawaban: Jumlah bilangan bulat yang bernilai kurang dari atau sama dengan N yang habis dibagi M dapat dihitung dengan menggunakan persamaan ο«N/Mο» (artinya pembulatan ke bawah dari nilai N/M). Berarti jumlah bilangan bulat yang bernilai kurang dari atau sama dengan 100 yang habis dibagi 5 ialah ο«100/5ο» = 20.
Latihan 1.
Jumlah bilangan bulat positif yang kurang dari atau sama dengan 1000 yang habis dibagi dengan 13 ialah?
2.
Jumlah bilangan bulat positif yang kurang dari atau sama dengan 1000 yang habis dibagi dengan 21 ialah?
3.
Berapa banyak bilangan bulat antara 1 sampai dengan 100 yang habis dibagi 3 atau 5?
4.
Jumlah bilangan bulat positif yang kurang dari atau sama dengan 1000 yang habis dibagi dengan 13 atau 21 ialah?
5.
Ada berapa banyak bilangan 3-digit yang habis dibagi dengan 13?
6.
Berapa banyak bilangan bulat antara 1 sampai dengan 100 yang tidak habis dibagi 3 atau tidak habis dibagi 5?
Jawaban: 1.
Jumlah bilangan bulat positif yang kurang dari atau sama dengan 1000 yang habis dibagi dengan 13 sama dengan ο«1000/13ο» = 76
2.
Jumlah bilangan bulat positif yang kurang dari atau sama dengan 1000 yang habis dibagi dengan 21 sama dengan ο«1000/21ο» = 47.
3.
Untuk menghitung banyaknya bilangan [1..100] yang habis dibagi 3 atau 5, kita perlu konsep insklusi-ekslusi: Penggabungan dua buah himpunan menghasilkan himpunan baru yang
elemen-elemennya berasal dari himpunan A dan B. Himpunan A dan B mungkin saja memiliki elemen-elemen yang sama. Banyaknya elemen yang
11
sama adalah jumlah elemen pada irisan A dan B ( |A β© B|). Setiap unsur yang sama telah dihitung dua kali, yaitu pada |A| dan pada |B|. Pada saat penggabungan, elemen tersebut hanya boleh dihitung satu kali. Berdasarkan hal ini, maka prinsip inklusi dan eksklusi berikut berlaku: |A βͺ B| = |A| + |B| - |A β© B| Berdasarkan Contoh Berapakah banyaknya bilangan bulat di antara 1 dan 100 yang habis dibagi 3 atau habis dibagi 5? Solusi Kita misalkan: A
= himpunan bilangan bulat yang habis dibagi 3
B
= himpunan bilangan bulat yang habis dibagi 5
A βͺ B = himpunan bilangan bulat yang habis dibagi 3 atau 5 A β© B = himpunan bilangan bulat yang habis dibagi 3 dan habis dibagi 5 Yang ditanyakan ialah | A βͺ B |, yaitu banyak bilangan bulat yang habis dibagi 3 atau habis dibagi 5. Jumlah bilangan bulat dari 1 hingga N yang habis dibagi oleh M sama dengan ο«N/Mο». Dengan demikian: Banyaknya bilangan bulat antara 1 sampai dengan 100 yang habis dibagi 3: |A| = ο«100/3ο» = 33 Banyaknya bilangan bulat antara 1 sampai dengan 100 yang habis dibagi 5: |B| = ο«100/5ο» = 20 Banyaknya bilangan bulat antara 1 sampai dengan 100 yang habis dibagi 3 dan 5: |A β© B| = ο«100/ (3 . 5)ο» = 6 Maka banyaknya bilangan bulat dari 1 sampai 100 yang habis dibagi 3 atau 5 yaitu: |A βͺ B| = |A| + |B| - |A β© B| = 33+20-6=47
12
4.
Jumlah bilangan bulat positif yang kurang dari atau sama dengan 1000 yang habis dibagi dengan 13 atau 21 ialah ο«1000/13ο» + ο«1000/21ο» ο«1000/(21.13)ο» = 76 + 47 - 3 = 120.
5.
Bilangan tiga digit berbeda yaitu seluruh bilangan bulat di antara 100 dan 999 inklusif. Sehingga, kita tinggal mencari banyaknya kelipatan 13 di antara 100 hingga 999. Banyaknya kelipatan 13 dalam range [100,999] dengan cara berikut: Banyak kelipatan 13 dalam range [1,999] - Banyak kelipatan 13 dalam range [1,99] = ο«999/13ο» - ο«99/13ο» = 76 β 7 = 69
6.
Menggunakan komplemennya, kita dapat menghitung banyaknya bilangan bulat dari 1 sampai 100 yang habis dibagi 3 dan habis dibagi 5: ο«100/6ο» = 6 Maka banyaknya bilangan bulat dari 1 sampai 100 yang tidak habis dibagi 3 atau tidak habis dibagi 5 yaitu: 100 - 6 = 94
III
Bilangan Prima, FPB, KPK dan Faktorisasi Prima
Bilangan Prima Bilangan prima memiliki banyak peranan dalam bidang ilmu komputer, terutama di bidang keamanan informasi. Bilangan prima adalah bilangan bulat positif p > 1 sedemikian sehingga pembagi bilangan tersebut hanya ada tepat 2, yaitu 1 dan p. Jika suatu bilangan yang lebih besar dari satu bukan bilangan prima, bilangan itu disebut bilangan komposit. Dengan kata lain bilangan prima adalah bilangan asli yang hanya dapat dibagi oleh bilangan itu sendiri dan satu dan hanya mempunyai dua faktor. Misalnya 2, 3, 5, 7, 11, β¦ Bilangan asli yang mempunyai lebih dari dua faktor disebut bilangan komposit (majemuk). Misal 4, 6, 8, 9, β¦ Teorema : (Topik Erotosthenes): Untuk setiap bilangan komposit n ada bilangan prima p sehingga p|n dan p . Teorema di atas mempunyai makna yang
13
sama dengan βjika tidak ada bilangan prima p yang dapat membagi n dengan p maka n adalah bilagan primaβ. Cara paling sederhana untuk mengecek keprimaan sebuah bilangan bulat n ialah dengan membagi n dengan seluruh bilangan bulat positif dari 1 hingga n. Apabila hanya terdapat dua buah pembagi dari n, maka n adalah sebuah bilangan prima. Jumlah pembagian yang dilakukan untuk melakukan pengecekan dapat dikurangi dengan membagi n dengan seluruh bilangan bulat yang lebih kecil daripada akar n. Jumlah tersebut masih dapat dikurangi kembali dengan membagi n dengan seluruh bilangan prima yang lebih kecil daripada akar n. Salah satu teknik yang paling efisien saat ini untuk mengecek keprimaan sebuah bilangan bulat ialah pengecekan keprimaan AgrawalKayal-Saxena (AKS) yang dipublikasikan pada taun 2002. Selain pengecekan keprimaan, hal yang dibutuhkan ialah membangitkan seluruh bilangan prima yang lebih kecil daripada sebuah bilangan bulat n. Cara paling sederhana untuk menentukan bilangan prima yang lebih kecil dari bilangan tertentu adalah dengan menggunakan teknik Sieve of Eratosthenes yang dapat dilakukan dengan langkah-langkah berikut: 1. Buatlah tabel yang berisi bilangan bulat positif berurutan dari 2 hingga n. 2. Misal p adalah sebuah bilangan bulat yang nilai awalnya ialah 2, yaitu bilangan prima pertama. 3. Mulai dari p tandai bilangan bulat kelipatan dari p (2p, 3p, β¦) selain p yang ada pada tabel. 4. Kemudian, carilah ganti nilai p dengan nilai terkecil pertama yang lebih besar dari p yang tidak ditandai pada tabel. Jika tidak ada bilangan demikian, maka langkah dihentikan. Jika ada, maka kembali ke langkah ketiga. 5. Bilangan prima yang diperoleh adalah nilai yang tidak ditandai pada tabel. Cara lain untuk menguji apakah n merupakan bilangan prima atau komposit, kita cukup membagi n dengan sejumlah bilangan prima, mulai dari 2, 3, β¦ , bilangan prima ο£ οn. Jika n habis dibagi dengan salah satu dari bilangan 14
prima tersebut, maka n adalah bilangan komposit, tetapi jika n tidak habis dibagi oleh semua bilangan prima tersebut, maka n adalah bilangan prima. Contoh: Tunjukkan apakah (i)
171, dan
(ii)
199 merupakan bilangan prima atau komposit.
Jawab: (i)
ο171 = 13.077. Bilangan prima yang ο£ ο171 adalah 2, 3, 5, 7, 11, 13. Karena 171 habis dibagi 3, maka 171 adalah bilangan komposit.
(ii)
(ii) ο199 = 14.107. Bilangan prima yang ο£ ο199 adalah 2, 3, 5, 7, 11, 13. Karena 199 tidak habis dibagi 2, 3, 5, 7, 11, dan 13, maka 199 adalah bilangan prima.
Faktor Persekutuan Terbesar (FPB) FPB dari dua buah bilangan a dan b ialah bilangan d terbesar sedemikian sehingga d merupakan pembagi dari a sekaligus pembagi dari b ( d | a dan d | b ). Apabila untuk dua bilagan bulat sembarang a dan b sedemikian sehingga FPB(a, b) = 1, kedua bilangan tersebut dikatakan saling prima. Sebagai contoh, 7 dan 8 adalah dua bilangan yang saling prima karena FPB(7, 8) = 1. Contoh: Berapa FPB dari 45 dan 36 Jawaban: Faktor pembagi 45: 1, 3, 5, 9, 15, 45; Faktor pembagi 36: 1, 2, 3, 4, 9, 12, 18, 36; Faktor pembagi bersama dari 45 dan 36 adalah 1, 3, 9 FPB(45, 36) = 9. Pencarian FPB untuk bilangan kecil masih dapat dilakukan dengan menebak nilai d sedemikian mulai dari 1. Akan tetapi, FPB dapat lebih mudah dicari dengan menggunakan metode Euclid. Diberikan dua buah bilangan bulat tak-negatif m dan n (m ο³ n). Metode Euclid (Algoritma Euclidean) dapat FPB dari m dan n sebagai berikut: FPB(m, n) = {
π, ππππ π = 0 πΉππ΅(π, π), ππππ π β 0 ; πππ π = π πππ π
15
Metode Euclid (Algoritme Euclidian): 1. Jika n = 0 maka m adalah PBB(m, n); stop. tetapi jika n οΉ 0, lanjutkan ke langkah 2. 2. Bagilah m dengan n dan misalkan r adalah sisanya. 3. Ganti nilai m dengan nilai n dan nilai n dengan nilai r, lalu ulang kembali ke langkah 1. Contoh: m = 80, n = 12 dan dipenuhi syarat m ο³ n Jawaban:
80 ο½ 6 ο12 ο« 8
12 ο½ 1 ο 8 ο« 4
8 ο½ 2ο4 ο« 0
Sisa pembagian terakhir sebelum 0 adalah 4, maka PBB(80, 12) = 4. Contoh: FPB dari 74 dan 333 dapat dicari dengan menggunakan langkahlangkah berikut: FPB(74, 333) = FPB(333, 74) = FPB(74, 333 mod 74) = FPB(74, 37) = FPB(37, 74 mod 37) = FPB(37, 0) = 37 Bezoutβs Theorem Jika d = gcd(a,b) maka ada x dan y bulat s.r.s, z=ax+by, jika dan hanya jika gcd(a,b) | z Contoh: Jika 3 adalah FPB dari 21 dan 12 (FPB(21,12)=3), s.r.s, 3=21x +12y;
16
Dari 3 = FPB(21,12), didapatkan hasilnya adalah: 3 = 21*(3) + 12*(-5) sehingga untuk x= 3 dan y= -5.
Relatif Prima Dua buah bilangan bulat a dan b dikatakan relatif prima jika FPB(a, b) = 1. Contoh: 20 dan 3 relatif prima sebab FPB(20, 3) = 1. Begitu juga 7 dan 11 relatif prima karena PBB(7, 11) = 1. Tetapi 20 dan 5 tidak relatif prima sebab PBB(20, 5) = 5 οΉ 1. Jika a dan b relatif prima, maka terdapat bilangan bulat m dan n sedemikian sehingga ma + nb = 1 Contoh: Bilangan 20 dan 3 adalah relatif prima karena PBB(20, 3) =1, atau dapat ditulis: 2 . 20 + (β13) . 3 = 1, dengan m = 2 dan n = β13. Tetapi 20 dan 5 tidak relatif prima karena PBB(20, 5) = 5 οΉ 1 sehingga 20 dan 5 tidak dapat dinyatakan dalam m . 20 + n . 5 = 1.
Kelipatan Persekutuan Terkecil (KPK) KPK(A, B) adalah sebuah bilangan bulat terkecil M sedemikian sehingga A merupakan pembagi dari M dan B merupakan pembagi dari M ( A|M dan B|M). KPK dapat dicari dengan menggunakan formula berikut: KPK(A, B) =
π¨π© ππ·π©(π¨,π©)
Faktorisasi Prima Setiap bilangan bulat positif n > 1 dapat dinyatakan secara unik sebagai: πΌ
πΌ
πΌ
n = π1 1 π2 2 β¦ ππ π Dengan ππ adalah bilangan prima ke-i dan ππ adalah bilangan prima terbesar yang membagi n. Nilai πΌ1 β₯ 0. Sebagai contoh: 1000 = 233053
17
3528 = 23325072
Latihan 1.
Tentukan bilangan-bilangan berikut merupakan bilangan prima atau majemuk:
a). 157
b). 221
2.
Tentukanlah faktorisasi prima dari 20!
3.
Berapa banyakkah angka 0 di belakang representasi desimal dari 100!
4.
Apakah 123 merupakan kelipatan dari 3?
5.
Apakah 1234 merupakan kelipatan dari 4?
6.
Apakah 123456789 merupakan kelipatan dari 9?
7.
Apakah 12345 merupakan kelipatan dari 5?
8.
Agripinna memiliki dua buah kain. Kain pertama memiliki lebar 72 cm dan kain kedua memiliki lebar 90 cm. Ia ingin memotong kain menjadi kain-kain yang lebih kecil dengan lebar yang sama. Lebar tersebut harus selebar mungkin. Berapakah lebar potongan kain tersebut?
9.
Berapakah FPB dari 30, 200, dan 120?
10.
Dengan menggunakan Teorema Bezeout, tentukan x dan y dalam FPB (710, 310)?
11. Tentukan x dan y dalam gcd(178, 312)? 12.
Ali Berenang 10 hari sekali, Budi berenang 15 hari sekali, sedangkan Coki berenang 10 hari sekali. Ketiganya sama-sama berenang pertama kali pada tanggal 20
februari 2012, kapan ketiganya bersama-sama
berenang untuk kedua kalinya? 13.
Carilah KPK dari 8, 12 dan 30!
14.
Carilah seluruh pasangan bilangan yang mempunyai FPB 4 dan KPK 120!
15.
Arwan bermain futsal setiap 4 hari sekali, Rudi bermain futsal setiap 6 hari sekali dan Doni bermain futsal setiap 9 hari sekali. Apabila mereka bermain futsal bersama-sama pada hari Sabtu. Pada hari apa mereka akan bermain futsal bersama-sama untuk ke-2 kalinya ?
16.
Bu Dengklek adalah seorang guru. Minggu depan, Bu Dengklek ingin membagikan permen kepada 7 orang muridnya, namun belum tentu semua muridnya datang ke sekolah pada minggu depan. Sebagai
18
tambahan, Bu Dengklek ingin membagikan permen kepada muridmuridnya sama rata dan tidak bersisa. Berapakah jumlah permen minimal yang harus Bu Dengklek bawa minggu depan? Jawaban 1.
Bilangan a). 157 a).
b). 221
Bilangan-bilangan prima yang adalah 2, 3, 5, 7, 11. Karena tidak ada dari bilangan-bilangan prima 2, 3, 5, 7, 11 yang dapat dibagi 157, maka 157 merupakan bilangan prima.
b).
Bilangan-bilangan prima yang adalah 2, 3, 5, 7, 11, 13. Karena 13|221 maka 221 merupakan bilangan komposit.
2.
20! = 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20 = 218.38.54.72.111.131.171.191
3.
100! Cukup besar dan memakan waktu jika faktorisasi prima harus dihitup terlebih dahulu. Untuk menyelesaikannya kita dapat menghitung jumlah bilangan di antara 1-100 yang habis dibagi 5 dan jumlah bilangan di antara 1-100 yang habis dibagi 25: ο«100/5ο» + ο«100/25ο» =20 + 4 = 24 Dengan demikian, terdapat 24 angka 0 di belakang 100!.
4.
Ya, karena jumlah digit-digitnya habis dibagi 3.
5.
Tidak. Bilangan yang habis dibagi 4 dua digit terakhir pasti habis dibagi oleh 4.
6.
Ya, karena jumlah digit-digitnya habis dibagi 9.
7.
Ya, karena digit terakhir dari 12345, yaitu 5, dapat dibagi oleh 5.
8.
Masalah ini dapat diselesaikan dengan FPB karena kita ingin membagi kain menjadi kain yang lebih kecil. Lebar potongan kain tersebut sama dengan FPB(72, 90) = 18.
9.
FPB dari tiga buah bilangan dapat dicari dengan menghitung FPB kedua bilangan pertama. Setelah itu, FPB antara hasil FPB kedua bilangan pertama dengan bilangan ketiga dihitung. Dengan kata lain, FPB(A, B, C)
19
= FPB(FPB(A, B), C). Dengan demikian, FPB(30, 200, dan 120) = FPB(FPB(30,200), 120) = FPB(10, 120) = 10. 10.
Pertama Kita perlu mencari FPB(710, 310) 710= 2*(310) + 90β¦β¦β¦β¦β¦β¦β¦.1 310 = 3*(90) + 40β¦β¦β¦β¦β¦β¦β¦...2 90 = 2*(40)+ 10β¦β¦β¦β¦β¦β¦β¦β¦.3 40 = 4*(10) + 0β¦β¦β¦β¦β¦β¦β¦β¦β¦.4 Sehingga FPB (710, 310) adalah: 10, berdasarkan teorema Bezout didapatkan persamaan: 10 = x (710) + y (310) Berdasarkan dari (3) kita bisa dapatkan persamaan berikut: 10 = 90 β 2*40, disederhanakan menjadi 10 = (1)*90 +(-2)*40. Berdasarkan persamaan 2 kita bisa dapatkan: 10 = (1) *90 +(-2)* [310 β 3* 90]. Disederhanakan menjadi 10 = (1) * (90) + (-2)*310 + (6)*90 10 = (7)*(90) + (-2) * 310. Berdasarkan persamaan 1 kita dapatkan 10 = (7)*[710 β 2*310]+ (-2)*310. Disederhamakan menjadi 10 = (7)*710 + (-14)*310 + (-2)*310 10 = (7)*710 + (-16)*310 Sehingga nilai x = 7, dan y = -16
11.
FPB (312, 178)= 2 ; x=4, dan y= -7
12.
Faktorisasi prima dari 10 = 2 x 5 Faktorisasi prima dadri 15 = 3 x 5 Faktorisasi prima dari 20 = 22 x 5. KPK dari 10, 15 dan 20 = 22 x 3 x 5 = 60 (kalikan semua faktor, faktor yang sama ambil yang terbesar). Jadi, mereka sama-sama berenang setiap 60 hari sekali. Mereka sama-sama berenang untuk yang keduakalinya adalah 20 februari + 60 hari = 20 April Ingat: bulan februari untuk tahun kabisat adalah 29 hari, untuk tahun bukan kabisat = 28 hari (2012 adalah tahun kabisat karena habis dibagi dengan 4)
13.
KPK(8, 12, 30) = 120.
20
14.
FPB 4 berarti bersama yang tekecil dari kedua bilangan adalah22. KPK 120 berarti faktor-faktor terbesar dari kedua bilangan adalah 23, 3 , 5, Maka pasangan bilangannya adalah 22 dengan 23.3 . 5 = 4 dengan 120 22 .3 dengan 23.5 = 12 dengan 40 22.5 dengan 23. 3 = 20 dengan 24 22.3.5 dengan 23 = 60 dengan 8
15.
KPK(4, 6, 9) = 36 36 hari setelah hari Sabtu adalah hari Minggu. Maka mereka akan bermain futsal bersama-sama lagi untuk ke-2 kalinya yaitu pada hari Minggu.
16. Perhatikan bahwa terdapat potongan kalimat berikut: "... belum tentu semua muridnya datang ...". Dengan kata lain, Bu Dengklek harus memperhitungkan seluruh kemungkinan pembagian permen, yaitu jika murid-muridnya yang datang sebanyak 0, 1, 2, 3, 4, 5, 6, atau 7. Banyak permen yang harus dibawa oleh Bu Dengklek minggu depan harus dapat dibagi kepada 0, 1, 2, 3, 4, 5, 6, atau 7 murid. Atau secara matematis, banyaknya permen harus dapat dibagi 1, 2, 3, 4, 5, 6, dan 7. Sehingga, permen yang harus dibawa oleh Bu Dengklek adalah minimal sebanyak KPK(1,2,3,4,5,6,7) = 420 buah.
IV
Modulo Aritmatika
Modulo atau modulus adalam sebuah operasi yang menghasilkan sisa pembagian dari suatu bilangan terhadap bilangan lainnya. A mod B (atau ditulis sebagai A % B) menghasilkan bilangan bulat yang merupakan sisa pembagian a oleh b. Untuk setiap bilangan bulat positif a dan b, terdapat bilangan bulat q dan r sedemikian rupa sehingga a = bq + r. Nilai q merupakan hasil pembagian a dengan b, r adalah sisa pembagian a dengan b. Sebagai contoh, 1000 mod 3 = 1 dan 1000 mod 7 = 6. Jika a mod b = 0, hal ini berarti b merupakan pembagi dari a. Contoh: Beberapa hasil operasi dengan operator modulo: (i) 23 mod 5 = 3
(23 = 5 ο 4 + 3) 21
(ii) 27 mod 3 = 0
(27 = 3 ο 9 + 0)
(iii) 6 mod 8 = 6
(6 = 8 ο 0 + 6)
(iv) 0 mod 12 = 0
(0 = 12 ο 0 + 0)
(v) β 41 mod 9 = 4
(β41 = 9 (β5) + 4)
(vi) β 39 mod 13 = 0
(β39 = 13(β3) + 0)
Penjelasan untuk (v): Karena a negatif, bagi |a| dengan m mendapatkan sisa rβ. Maka a mod m = m β
β 41| mod 9 = 5, sehingga β41
mod 9 = 9 β 5 = 4.
Kongruen Misalnya 38 mod 5 = 3 dan 13 mod 5 = 3, maka kita katakan 38 οΊ 13 (mod 5) (baca: 38 kongruen dengan 13 dalam modulo 5). Misalkan a dan b adalah bilangan bulat dan m adalah bilangan > 0, maka a οΊ b (mod m) jika m habis membagi a β b. Jika a tidak kongruen dengan b dalam modulus m, maka ditulis a οΊ/ b (mod m) . Contoh: 17 οΊ 2 (mod 3)
( 3 habis membagi 17 β 2 = 15)
β7 οΊ 15 (mod 11)
(11 habis membagi β7 β 15 = β22)
12 οΊ/ 2 (mod 7)
(7 tidak habis membagi 12 β 2 = 10 )
β7 οΊ/ 15 (mod 3)
(3 tidak habis membagi β7 β 15 = β22)
Kekongruenan a οΊ b (mod m) dapat pula dituliskan dalam hubungan a = b + km, yang dalam hal ini k adalah bilangan bulat. Contoh: 17 οΊ 2 (mod 3)
dapat ditulis sebagai 17 = 2 + 5 ο 3
β7 οΊ 15 (mod 11) dapat ditulis sebagai β7 = 15 + (β2)11 Berdasarkan definisi aritmetika modulo, kita dapat menuliskan a mod m = r sebagai ο a οΊ r (mod m) Contoh: Beberapa hasil operasi dengan operator modulo berikut: (i) 23 mod 5 = 3 (ii) 27 mod 3 = 0 (iii) 6 mod 8 = 6
dapat ditulis sebagai 23 οΊ 3 (mod 5) dapat ditulis sebagai 27 οΊ 0 (mod 3) dapat
ditulis sebagai 6 οΊ 6 (mod 8) 22
(iv) 0 mod 12 = 0
dapat ditulis sebagai 0 οΊ 0 (mod 12)
(v) β 41 mod 9 = 4
dapat ditulis sebagai β41 οΊ 4 (mod 9)
(vi) β 39 mod 13 = 0 dapat ditulis sebagai β 39 οΊ 0 (mod 13) Teorema. Misalkan m adalah bilangan bulat positif. 1. Jika a οΊ b (mod m) dan c adalah sembarang bilangan bulat maka (i) (a + c) οΊ (b + c) (mod m) (ii) ac οΊ bc (mod m) (iii) ap οΊ bp (mod m) untuk suatu bilangan bulat tak negatif p. 2. Jika a οΊ b (mod m) dan c οΊ d (mod m), maka (i) (a + c) οΊ (b + d) (mod m) (ii) ac οΊ bd (mod m) Contoh: Misalkan 17 οΊ 2 (mod 3) dan 10 οΊ 4 (mod 3), maka menurut Teorema: 17 + 5 = 2 + 5 (mod 3)
ο
22 = 7 (mod 3)
17 . 5 = 5 ο 2 (mod 3)
ο
85 = 10 (mod 3)
17 + 10 = 2 + 4 (mod 3)
ο
27 = 6 (mod 3)
17 . 10 = 2 ο 4 (mod 3)
ο
170 = 8 (mod 3)
Perhatikanlah bahwa Teorema 2 tidak memasukkan operasi pembagian pada aritmetika modulo karena jika kedua ruas dibagi dengan bilangan bulat, maka kekongruenan tidak selalu dipenuhi. Misalnya: (i)
10 οΊ 4 (mod 3) dapat dibagi dengan 2 karena 10/2 = 5 dan 4/2 = 2, dan 5 οΊ 2 (mod 3)
(ii)
14 οΊ 8 (mod 6) tidak dapat dibagi dengan 2, karena 14/2 = 7 dan 8/2 = 4, tetapi 7 οΊ/ 4 (mod 6).
Balikan Modulo (modulo invers) Jika a dan m relatif prima dan m > 1, maka kita dapat menemukan balikan (invers) dari a modulo m. Balikan dari a modulo m adalah bilangan bulat
a
sedemikian sehingga a a οΊ 1 (mod m) 23
Dari definisi relatif prima diketahui bahwa PBB(a, m) = 1, dan menurut relatif prima terdapat bilangan bulat p dan q sedemikian sehingga pa + qm = 1 yang mengimplikasikan bahwa pa + qm οΊ 1 (mod m), Karena qm οΊ 0 (mod m), maka pa οΊ 1 (mod m) disebut sebagai ekongruenan yang terakhir ini berarti bahwa p adalah balikan dari a modulo m. Untuk mencari balikan dari a modulo m, kita harus membuat kombinasi linear dari a dan m sama dengan 1. Koefisien a dari kombinasi linear tersebut merupakan balikan dari a modulo m. Contoh: Tentukan balikan dari 4 (mod 9) Jawab: Karena PBB(4, 9) = 1, maka balikan dari 4 (mod 9) ada. Dari algoritma Euclidean diperoleh bahwa :9 = 2 ο 4 + 1 Susun persamaan di atas menjadi β2 ο 4 + 1 ο 9 = 1 Dari persamaan terakhir ini kita peroleh β2 adalah balikan dari 4 modulo 9. Periksalah bahwa : β2 ο 4 οΊ 1 (mod 9)
(9 habis membagi β2 ο 4 β 1 = β9)
Kekongruenan Lanjar (Linear) Kekongruenan lanjar adalah kongruen yang berbentuk ax οΊ b (mod m) dengan m adalah bilangan bulat positif, a dan b sembarang bilangan bulat, dan x adalah peubah bilangan bulat. Nilai-nilai x dicari sebagai berikut: ax = b + km yang dapat disusun menjadi:
xο½
b ο« km a
24
dengan k adalah sembarang bilangan bulat. Cobakan untuk k = 0, 1, 2, β¦ dan k = β1, β2, β¦ yang menghasilkan x sebagai bilangan bulat. Contoh: Tentukan solusi: 4x οΊ 3 (mod 9) Jawab: 4x οΊ 3 (mod 9)
xο½
3ο« k ο9 4
k = 0 ο x = (3 + 0 ο 9)/4 = 3/4
(bukan solusi)
k = 1 ο x = (3 + 1 ο 9)/4 = 3 k = 2 ο x = (3 + 2 ο 9)/4 = 21/4
(bukan solusi)
k = 3, k = 4 tidak menghasilkan solusi k = 5 ο x = (3 + 5 ο 9)/4 = 12 β¦ k = β1 ο x = (3 β 1 ο 9)/4 = β6/4
(bukan solusi)
k = β2 ο x = (3 β 2 ο 9)/4 = β15/4 (bukan solusi) k = β3 ο x = (3 β 3 ο 9)/4 = β6 β¦ k = β6 ο x = (3 β 6 ο 9)/4 = β15 β¦ Nilai-nilai x yang memenuhi: 3, 12, β¦ dan β6, β15, β¦
Chinese Remainder Problem Pada abad pertama, seorang matematikawan China yang bernama Sun Tse mengajukan pertanyaan sebagai berikut: βTentukan sebuah bilangan bulat yang bila dibagi dengan 5 menyisakan 3, bila dibagi 7 menyisakan 5, dan bila dibagi 11 menyisakan 7β Pertanyaan Sun Tse dapat dirumuskan kedalam sistem kongruen lanjar: x οΊ 3 (mod 5) x οΊ 5 (mod 7) x οΊ 7 (mod 11)
25
Teorema. (Chinese Remainder Theorem) Misalkan m1, m2, β¦, mn adalah bilangan bulat positif sedemikian sehingga PBB(mi, mj) = 1 untuk i οΉ j. Maka sistem kongruen lanjar : x οΊ ak (mod mk) mempunyai sebuah solusi unik modulo m = m1 ο m2 ο β¦ ο mn. Pemangkatan Modulo Pangkat modular bersifat periodik karena hanya ada π buah nilai mod π.
Jika n terlalu besar, maka untuk menghitung pemangkatan, lebih efisien untuk mencari periodisitas-nya Jika
Maka:
Prinsip ini dapat digunakan untuk menghitung ππ (mod m) untuk n yang besar dengan lebih cepat Contoh: 34 οΊ 1 (mod 5), sehingga untuk menghitung 32010 mod 5, kita hitung bahwa 2010 οΊ 2 (mod 4), sehingg 32010 = 32 οΊ 4 (mod 5)
Fermatβs Little Theorem Terdapat metode lain yang dapat digunakan untuk menguji keprimaan suatu bilangan bulat, yang terkenal dengan Teorema Fermat. Fermat (dibaca βFair-maβ) adalah seorang matematikawan Perancis pada tahun 1640. Jika π adalah bilanngan bulat, dan π adalah bilangan prima, maka ππ οΊ π (mod p) 26
Jika FPB(a,p)=1 maka apβ1 οΊ 1 (mod p) Contoh: Kita akan menguji apakah 17 dan 21 bilangan prima atau bukan. Di sini kita mengambil nilai a = 2 karena PBB(17, 2) = 1 dan PBB(21, 2) = 1. Untuk 17, 217β1 = 65536 οΊ 1 (mod 17) karena 17 tidak membagi 65536 β 1 = 65535 (65535 οΈ 17 = 3855). Untuk 21, 221β1 =1048576 οΊ\ 1 (mod 21) karena 21 tidak habis membagi 1048576 β 1 = 1048575. Lebih lanjut untuk kepangkatan modular berdasarkan femat toerema: Contoh: 31000 mod 7? 3 dan 7 adalah bilangan prima. Menurut relative prima didapatkan nilai FPB(3,7) =1 ο π=3; π=7 π6 οΊ 1 (mod 7) ο dan 1000 οΊ 4 (mod 6), sehingga 31000 = 34 οΊ 4 (mod 7)
Latihan 1. Lengkapilah tabel berikut: A
B
A modulo B
17
43
43
17
192
24
119
513
512
16
259
4
777
11
14
5
27
2. Berapakah nilai dari 123456789 mod 9? 3. Berapakah nilai dari 987654321 mod 9? 4. Tentukan balikan dari 17 (mod 7), dan 18 (mod 10) 5. Tentukan solusi: 2x οΊ 3 (mod 4) dengan kongruen lanjar 6. Tentukan solusi dari pertanyaan Sun Tse di atas. 7. Periksalah bahwa (i)
316 οΊ 1 (mod 17), dan
(ii)
186 οΊ 1 (mod 49).
Jawaban 1. Tabel yang telah terisi ialah: A
B
A modulo B
17
43
17
43
17
9
192
24
0
119
513
119
512
16
0
259
4
3
777
11
7
14
5
4
2. Bilangan yang habis dibagi dengan 9 memiliki ciri jumlah seluruh digitnya juga haggis dibagi 9. Sebagai contoh, jumlah digit dari 123456789 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45. Karena 45 habis dibagi 9, maka 123456789 juga habis dibagi 9 sehingga 123456789 mod 9 = 0. 3. 987654321 mod 9 = 0 dengan alas an yang sama dengan pada nomor 20. 4. Karena PBB(17, 7) = 1, maka balikan dari 17 (mod 7) ada. Dari algoritma Euclidean diperoleh rangkaian pembagian berikut: 17 = 2 ο 7 + 3 (i) 7 = 2 ο 3 + 1 (ii) 3 = 3 ο 1 + 0 (iii)
(yang berarti: PBB(17, 7) = 1) )
Susun (ii) menjadi:
28
1=7β2ο3
(iv)
Susun (i) menjadi 3 = 17 β 2 ο 7 (v) Sulihkan (v) ke dalam (iv): 1 = 7 β 2 ο (17 β 2 ο 7) = 1 ο 7 β 2 ο 17 + 4 ο 7 = 5 ο 7 β 2 ο 17 atau β2 ο 17 + 5 ο 7 = 1 Dari persamaan terakhir ini kita peroleh β2 adalah balikan dari 17 modulo 7. β2 ο 17 οΊ 1 (mod 7)
(7 habis membagi β2 ο 17 β 1 = β35)
Karena PBB(18, 10) = 2 οΉ 1, maka balikan dari 18 (mod 10) tidak ada. 5. 2x οΊ 3 (mod 4) xο½
3ο« k ο4 2
Karena 4k genap dan 3 ganjil maka penjumlahannya menghasilkan ganjil, sehingga hasil penjumlahan tersebut jika dibagi dengan 2 tidak menghasilkan bilangan bulat. Dengan kata lain, tidak ada nilai-nilai x yang memenuhi 2x οΊ 3 (mod 5). 6. Menurut persamaan Teorema Chinese Remainder, kongruen pertama, x οΊ 3 (mod 5), memberikan x = 3 + 5k1 untuk beberapa nilai k. Sulihkan ini ke dalam kongruen kedua menjadi 3 + 5k1 οΊ 5 (mod 7), dari sini kita peroleh k1 οΊ 6 (mod 7), atau k1 = 6 + 7k2 untuk beberapa nilai k2. Jadi kita mendapatkan x = 3 + 5k1 = 3 + 5(6 + 7k2) = 33 + 35k2 yang mana memenuhi dua kongruen pertama. Jika x memenuhi kongruen yang ketiga, kita harus mempunyai 33 + 35k2 οΊ 7 (mod 11), yang mengakibatkan k2 οΊ 9 (mod 11) atau k2 = 9 + 11k3. Sulihkan k2 ini ke dalam kongruen yang ketiga menghasilkan x = 33 + 35(9 + 11k3) οΊ 348 + 385k3 (mod 11). Dengan demikian, x οΊ 348 (mod 385) yang memenuhi ketiga konruen tersebut. Dengan kata lain, 348 adalah solusi unik modulo 385. Catatlah bahwa 385 = 5 ο 7 ο 11.
29
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 adalah x οΊ 3 ο 77 ο 3 + 5 ο 55 ο 6 + 7 ο 35 ο 6 (mod 385) οΊ 3813 (mod 385) οΊ 348 (mod 385) 7. Penyelesaian (i)
Dengan mengetahui bahwa kongruen 33 οΊ 10 (mod 17), kuadratkan kongruen tersebut menghasilkan 36 οΊ 100 οΊ β2 (mod 17) Kuadratkan lagi untuk menghasilkan 312 οΊ 4 (mod 17) Dengan demikian, 316 οΊ 312 ο 33 ο 3 οΊ 4 ο 10 ο 3 οΊ 120 οΊ 1 (mod 17)
(ii) Caranya sama seperti penyelesaian (i) di atas: 182 οΊ 324 οΊ 30 (mod 49) 184 οΊ 900 οΊ 18 (mod 49) 186 οΊ 184 ο 182 οΊ 18 ο 30 οΊ 540 οΊ 1 (mod 49)
30