![008 Materi (D) [PDF]](https://pdfs.asia/img/200x200/008-materi-d.jpg)
14 0 1 MB
BAB II KETERBAGIAN 2.1
Pendahuluan
Pada pertemuan minggu ke-3 , dan 4 ini dibahas konsep keterbagian, algo-ritma pembagian dan bilangan prima pada bilangan bulat. Relasi keterbagian pada himpunan semua bilangan bulat memunculkan banyak sifat menarik. Dari relasi ini dapat didefinisikan pengertian hasil bagi dan sisa pembagian, sehingga dapat membangkitkan operasi pembagian bilangan bulat dan konsep modulo. Dengan mempelajari bab ini, diharapkan: 1. Mahasiswa bisa memahami pengertian keterbagian. 2. Mahasiswa bisa mengidentifikasi bilangan prima 3. Mahasiswa bisa menjelaskan pengertian algoritma pembagian 4. Mahasiswa bisa menerapkan sifat-sifat keterbagian dan algoritma pemba-gian pada masalah bilangan bulat 2.2
Keterbagian
Sejak di sekolah dasar telah dikenal beberapa operasi pada bilangan bulat, diantaranya penjumlahan(+), pengurangan(−), perkalian(× atau ·) dan pembagian(: atau /). Untuk sebarang dua bilangan bulat berlaku jumlah, selisih dan hasil kalinya masingmasing merupakan bilangan bulat, tetapi pembagian bilangan yang satu dengan yang lain belum tentu merupakan bilangan bulat. Definisi 2.2.1. Diberikan bilangan bulatmdann(n ≠ 0). Bilanganmdikatakanhabis dibagi oleh n atau n membagi m, ditulis n|m, jika terdapat bilangan bulat k dengan sifat m = kn. Jika m habis dibagi oleh n, maka m disebut kelipatan dari n dan n disebut pembagi atau faktor dari m. Jika m tidak habis dibagi oleh n, dituliskan n̸m|. Karena 0 = 0.n, diperoleh bahwa
n|0
untuk
setiap
bilangan
PENDIDIKAN MATEMATIKA B 2017
bulat
n.
Sebaliknya,
0
̸
|muntuk
91
setiapbilanganbulattak nol m, sebab m ≠ 0 = k.0 untuk setiap bilangan bulat k. Dari definisi keterbagian diperoleh beberapa sifat dasar sebagai berikut. mTeorema 2.2.2. Diberikan bilangan bulatx, ydanz. a. x|x; b. Jika x|y dan y|z, maka x|z; c. Jika x|y dan y ≠ 0, maka |x| ≤ |y|; d. Jika x|y dan x|z, maka x|αy + βz untuk setiap bilangan bulat α dan β; e. Jika x|y dan x|y ± z, maka x|z; f. Jika x|y dan y|x, maka |x| = |y|; g. Jika x|y dan y ≠ 0, maka xy|y; h. Untuk z ≠ 0 berlaku x|y jika dan hanya jika xz|yz. Diperhatikan bahwa untuk sebarang bilangan bulat tak nol n, faktor positif dari n ada sebanyak ganjil jika dan hanya jika n merupakan kuadrat sempurna, yaitu n = m2 untuk suatu bilangan bulat m. (Jika suatu bilangan bulat tidak habis dibagi oleh sebarang bilangan kuadrat, maka bilangan terse-but disebut square free.) Hal ini dikarenakan jika n bukan kuadrat sempurna, maka semua faktor positif dari n dapat dinyatakan ke dalam pasangan-pasangan berbentuk (x,nx ). n + 20 Contoh 2.2.3. Tentukan semua bilangan bulatnsehingga
merupakan n − 13
bilangan bulat. Penyelesaian. Diperhatikan bahwa n − 13 + 33
n + 20 =
33 =1+
.
n − 13 n – 13 n − 13 n + 20 33 Jika n−13 bulat, maka n−13 bulat. Artinya n− 13|33 atau n− 13 faktor dari 33. Karena faktor dari 33 adalah −33,−11,−3,−1, 1, 3, 11 dan 33, maka diperoleh nilai n yang mungkin adalah −20, 2, 10, 12, 14, 16, 24 atau 46. Dapat
PENDIDIKAN MATEMATIKA B 2017
92
dicek bahwa semua nilai n tersebut memenuhi kondisi yang diberikan. Jadi, nilai n yang memenuhi adalah −20, 2, 10, 12, 14, 16, 24 dan 46.
Contoh 2.2.4. Tentukan semua pasangan bilangan bulat positif (m, n) dengansifat 2 3 m +n = 1. Penyelesaian. Misalkan bilangan bulat positif n dan m memenuhi berlaku 2n + 3m
⇔ (m− 2)(n− 3)
2 m
+
n
3
= 1, maka
= mn = 6.
Diperoleh bahwa m− 2 dan n− 3 merupakan faktor dari 6. Karena m bilangan bulat positif, maka m− 2 >−2. Diperoleh nilai m− 2 yang mungkin adalah 1, 2, 3 atau 6, sehingga nilai m yang mungkin adalah 3, 4, 5 atau 8. Akibatnya diperoleh pasangan (m, n) yang memenuhi adalah (3, 9), (4, 6), (5, 5) dan (8, 4).
Contoh 2.2.5. Pada suatu ruangan terdapat 20 kotak kosong, bernomor 1 sam-pai 20. Sebanyak 20 anak secara bergiliran melakukan ekperimen terhadap kotak-kotak tersebut. Anak pertama memasukkan satu bola ke masing-masing 20 kotak tersebut. Anak kedua mengambil bola yang ada pada kotak bernomor 2, 4, . . . , 20. Anak ketiga melakukan eksperimen terhadap kotak-kotak bernomor 3, 6, . . . , 18: jika pada kotak tidak terdapat bola, maka dia memasukkkan satu bola ke kotak tersebut dan jika pada kotak terdapat bola, maka dia mengambil bola pada kotak tersebut. Anak ke i melakukan eksperimen terhadap kotak-kotak bernomor keli-patan i: jika pada kotak tidak terdapat bola, maka dia memasukkkan satu bola ke kotak tersebut dan jika pada kotak terdapat bola, maka dia mengambil bola pada kotak tersebut. Tentukan banyak kotak yang berisi bola setelah semua anak menyelesaikan eksperimennya? Penyelesaian. Diperhatikan bahwa anak ke i melakukan eksperimen terhadap kotak bernomor j jika dan hanya jika i|j. Berdasarkan sifat g. pada Teorema 2.2.2, hal ini terjadi jika dan hanya jika anak ke ji melakukan eksperimen ter-hadap kotak tersebut. Akibatnya, hanya kotak bernomor 1, 4, 9 dan 16 yang
PENDIDIKAN MATEMATIKA B 2017
93
dikenai eksperimen sebanyak bilangan ganjil, sehingga hanya kotak-kotak terse-but yang berisi bola setelah semua anak menyelesaikan eksperimennya. Jadi, jawabannya adalah 4.
Berikut diberikan suatu karakteristik terkait keterbagian dari hasil kali bilangan bulat berurutan. Teorema 2.2.6. Hasil kalin≥ 1 bilangan bulat berurutan selalu habis dibagioleh n!. (n! = 1 × 2 × . . . × n) Bukti. Pertama-tama, akan ditunjukkan perkalian n bilangan bulat positif beru-rutan habis dibagi oleh n!. Akan digunakan induksi matematika untuk membuk-tikannya. Basis induksi. Untuk n = 1, cukup jelas bahwa perkalian 1 bilangan bulat positif pasti habis dibagi oleh 1. Jadi, pernyataan benar untuk kasus n = 1. Langkah induksi. Diasumsikan pernyataan benar untuk n = k, yaitu perkalian k bilangan bulat positif berurutan habis dibagi oleh k!. Akan ditunjukkan perny-ataan benar untuk kasus n = k + 1, yaitu perkalian k + 1 bilangan bulat positif berurutan habis dibagi oleh (k +1)!. Misalkan k +1 bilangan berurutan dimaksud adalah m, m + 1, m + 2, . . . , m + k untuk suatu bilangan bulat positif m. Akan di-tunjukkan dengan induksi matematika bahwa untuk setiap bilangan bulat positif m berlaku m(m + 1)(m + 2) . . . (m + k) habis dibagi oleh (k + 1)! . Basis induksi. Untuk m = 1, diperoleh 1(1 + 1)(1 + 2) . . . (1 + k) = (k + 1)! = 1.(k + 1)!. Artinya, 1(1 + 1)(1 + 2) . . . (1 + k) habis dibagi oleh (k + 1)!. Jadi, pernyataan benar untuk m = 1. Langkah induksi. Diasumsikan pernyataan benar untuk m = p, yaitu p(p + 1) (p + 2) . . . (p + k) habis dibagi oleh (k + 1)!. Akan ditunjukkanpernyataan benar untuk kasus m = p + 1, yaitu (p + 1)(p + 2)(p + 3) . . . (p + k + 1) habis dibagi oleh (k + 1)!. Diperhatikan bahwa (p + 1)(p + 2)(p + 3) . . . (p + k + 1)
=
(p + 1)(p + 2) . . . (p + k)p +(p + 1)(p + 2) . . . (p + k)(k + 1)
= p(p + 1)(p + 2) . . . (p + k) +(k + 1)(p + 1)(p + 2)(p + 3) . . . (p + k).
PENDIDIKAN MATEMATIKA B 2017
94
Berdasarkan asumsi induksi, diperoleh p(p+1)(p+2) . . . (p+k) habis dibagi (k + 1)!. Karena (p + 1)(p + 2)(p + 3) . . . (p + k) merupakan perkalian k bilangan bulat positif berurutan, maka (p + 1)(p + 2)(p + 3) . . . (p + k) habis dibagi k!, sehingga diperoleh (k + 1) (p + 1)(p + 2)(p + 3) . . . (p + k) habis dibagi (k + 1)!. Jadi, (p+ 1)(p+ 2)(p+ 3) . . . (p+ k + 1) habis dibagi (k + 1)!. Terbukti pernyataan benar untuk m = p + 1. Jadi, terbukti bahwa perkalian n bilangan bulat positif berurutan habis dibagi oleh n!. Selanjutnya, jika diantara n bilangan bulat berurutan terdapat 0, maka hasil kalinya sama dengan 0, sehingga pasti habis dibagi oleh n!. Untuk kasus, jika n bilangan berurutan tersebut semua merupakan bilangan negatif, dapat dibuk-tikan dengan cara yang sama seperti bagian pertama dengan mengalikan hasil kalinya dengan (−1)n.
Contoh 2.2.7. Tunjukkan bahwan6−n2selalu habis dibagi oleh 60 untuk semuabilangan bulat positif n. Penyelesaian. Diberikan sebarang bilangan bulat positif n. Diperhatikan bahwa n6 − n2
= n2(n4 − 1) = (n − 1)n2(n + 1)(n2+ 1) = (n− 1)n2(n + 1)(n2− 4) + 5(n− 1)n2(n + 1) = (n− 2)(n− 1)n(n + 1)(n + 2)n + 5(n− 1)(n2− 2n)(n + 1) +10(n− 1)n(n + 1) = (n− 2)(n− 1)n(n + 1)(n + 2)n + 5(n− 2)(n− 1)n(n + 1) +10(n− 1)n(n + 1).
Diperhatikan bahwa 5!|(n−2)(n−1)n(n + 1)(n + 2), 4!|(n−2)(n−1)n(n + 1) dan 3!|(n−1)n(n+1). Karena 5! = 120, 4! = 24 dan 3! = 6, maka diperoleh 120|(n−2) (n− 1)n(n + 1)(n + 2)n, 120|5(n− 2)(n− 1)n(n + 1) dan 60|10(n− 1)n(n + 1). Karena 60|120, maka 60|(n−2)(n−1)n(n + 1)(n + 2)n, 60|5(n−2)(n−1)n(n + 1) dan 60|10(n− 1)n(n + 1), sehingga diperoleh 60|n6−n2. Berdasarkan konsep keterbagian terkait bilangan 2, himpunan bilangan
PENDIDIKAN MATEMATIKA B 2017
95
bulat yang dinotasikan Z dapat dipartisi menjadi dua himpunan bagian, him-punan bilangan ganjil dan himpunan bilangan genap: {±1, ±3, ±5, . . .} dan {0, ±2, ±4, . . .}. Beberapa konsep dasar yang dimiliki oleh bilangan ganjil dan genap sebagai berikut:
a. Bilangan ganjil berbentuk 2k + 1 untuk suatu bilangan bulat k; b. Bilangan genap berbentuk 2k untuk suatu bilangan bulay k; c. Jumlahan dua bilangan ganjil adalah bilangan genap; d. Jumlahan dua bilangan genap adalah bilangan genap; e. Jumlahan bilangan ganjil dan bilangan genap adalah bilangan genap; f. Perkalian dua bilangan ganjil adalah bilangan ganjil; g. Perkalian dua bilangan bulat merupakan bilangan genap jika dan hanya jika salah satunya merupakan bilangan genap. Konsep ini sangat bermanfaat dalam menyelesaikan beberapa masalah teori bilangan. Contoh 2.2.8. Diberikan bilangan bulat positifn≥ 1. Tunjukkan bahwa a. 2ndapat dinyatakan sebagai jumlahan dua bilangan ganjil berurutan. b. 3ndapat dinyatakan sebagai jumlahan tiga bilangan bulat berurutan. Penyelesaian. Untuk a., persamaan 2n = (2k−1) + (2k + 1) memberikan penye-lesaian k = 2n−2, sehingga diperoleh 2n = (2n−1− 1) + (2n−1 + 1). Untuk b., persamaan 3n = (s−1)+s+(s+1) memberikan penyelesaian s = 3n−2, sehingga diperoleh 3n = (3n−1− 1) + 3n−1 + (3n−1 + 1).
Contoh 2.2.9. Diberikan bilangan ganjila, bdanc. Tunjukkan bahwa akarakarpersamaan kuadrat ax2+ bx + c = 0 bukan bilangan bulat.
PENDIDIKAN MATEMATIKA B 2017
96
Penyelesaian. Diandaikan bilangan bulat n merupakan akar persamaan ax2 + bx+ c = 0. Diperoleh an2+ bn+ c = 0. Akan ditinjau dua kasus, yaitu n bilangangenap dan n bilangan ganjil. Kasus n bilangan genap. Karena a dan b bilangan ganjil, maka an2 dan bn merupakan bilangan ganjil, sehingga diperoleh an2 + bn bilangan genap. Karena c bilangan ganjil, maka an2+bn+c bilangan ganjil, sehingga diperoleh an2+bn+c ≠ 0 (0 genap), suatu kontradiksi. Kasus n bilangan ganjil. Karena a dan b bilangan ganjil, maka an2 dan bn merupakan bilangan genap, sehingga diperoleh an2 + bn bilangan genap. Karena c bilangan ganjil, maka an2+bn+c bilangan ganjil, sehingga diperoleh an2+bn+c ≠ 0 (0 genap), suatu kontradiksi. Jadi, akar-akar persamaan kuadrat ax2 + bx + c = 0 bukan bilangan bulat. Contoh 2.2.Diberikan10. kbilangan genap. Tunjukkan bahwa tidak ada bilan-gan ganjil n1, n2, . . . , nk dengan sifat 1 1 1 1= + +...+ . n1 n2 nk Penyelesaian. Diandaikan terdapat bilangan ganjil n1, n2, . . . , nkdengan sifat 1 1 1 1= + +...+ . n n n 1 2 k Dengan menyamakan penyebut pada ruas kanan, diperoleh n1n2. . . nk = s1 + s2+ . . . + skdengan s1, s2, . . . , skbilangan ganjil. Diperhatikan bahwa ruas kirimerupakan bilangan ganjil, sedangkan ruas kanan merupakan bilangan genap, suatu kontradiksi.
2.3
Algoritma Pembagian
Berikut diberikan salah satu konsep yang disebut Algoritma Pembagian yang memiliki peranan penting dalam teori bilangan. Teorema 2.3.1 (Algoritma Pembagian). Untuk setiap bilangan bulat positifadan b terdapat dengan tunggal pasangan bilangan bulat non-negatif (q, r) dengan sifat b = aq + r dan r < a. Lebih lanjut, q disebut hasil bagi dan r disebut sisa ketika b dibagi oleh a.
PENDIDIKAN MATEMATIKA B 2017
97
Bukti. Diberikan sebarang bilangan bulat positif a dan b. Pertama-tama, di-tunjukkan eksistensi dari pasangan (q, r). Diperhatikan bahwa ada 3 kasus yang mungkin yaitu a < b, a = b atau a > b. 1. Kasus a > b. Dipilih q = 0 dan r = b < a, diperoleh (q, r) = (0, b) memenuhi kondisi b = aq + r dan r < a. 2. Kasus a = b. Dipilih q = 1 dan r = 0 < a, diperoleh (q, r) = (1, 0) memenuhi kondisi b = aq + r dan r < a. 3. Kasus a < b. Diperhatikan bahwa terdapat bilangan bulat positif n se-hingga na > b. Dipilih q bilangan bulat positif terkecil dengan sifat (q + 1)a > b, maka berlaku qa≤b. Dipilih r = b−aq. Diperoleh (q, r) memenuhi kondisi b = aq + r dan 0 ≤r < a. Selanjutnya, akan ditunjukkan ketunggalan pasangan (q, r) tersebut. Diandaikan (q′, r′) memenuhi kondisi b = aq′ + r′ dan 0 ≤r′< a. Diperoleh aq + r = aq′ + r′, ekuivalen dengan a(q−q′) = r′−r, yang berarti a|r′−r. Akibatnya |r′−r| ≥a atau |r′−r| = 0. Karena 0 ≤r, r′≤a, maka |r′−r|< a. Diperoleh |r′−r| = 0, artinya r′ = r, sehingga berakibat q = q′.
Contoh 2.3.2. Diketahui bilangan 1059, 1417 dan 2312 memiliki sisa yang samaketika dibagi oleh d >1. Tentukan nilai d. Penyelesaian. Misalkan sisanya adalah r. Berdasarkan Algoritma Pembagian, diperoleh 1059 = 1417 = 2312 =
q1d + r q2d + r q3d + r,
untuk suatu bilangan bulat q1, q2 dan q3. Diperoleh (q2−q1)d
= 1417 − 1059 = 358 = 2.179
(q3−q1)d
= 2312 − 1059 = 1253 = 7.179
(q3−q2)d
= 2312 − 1417 = 895 = 5.179,
PENDIDIKAN MATEMATIKA B 2017
98
yang berarti d merupakan faktor dari 2.179, 7.179 dan 5.179. Karena d > 1, maka diperoleh d = 179.
Contoh 2.3Diberikan.3. bilangan bulat positifn. Tunjukkan bahwa 32n +1 habisdibagi oleh 2 tetapi tidak habis dibagi oleh 4. 2n
Penyelesaian. merupakan bilangan ganjil, sehingga Diperhatikan bahwa 3 2n 2n = diperoleh 3 + 1 bilangan genap, yang berarti habis dibagi oleh 2. Karena 3 2n 21 2n 1 2n 1 =9 (3 ) = (8 + 1) , maka berdasarkan teorema Binomial Newton: m M m ) ( ) m−2 2 (x + y)m = xm + ( y + . . . +(m−1)xym−1+ ym, 1 xm−1y+ 2 x dengan mengambil m = 2n−1, x = 8 dan y = 1 diperoleh n n n n 1 1 2 1 1 n 1 2n 1 ( − ) (8 + 1)2 = 82 + (1− ) 82 −1+ (2 2− )8m−2+. . .+ 2n−1 1 8 + 1. − 2 n n 2 1 + 1 = (8K + 1) + 1 = 4(2K) + 2 untuk suatu Akibatnya 3 + 1 = (8 + 1) bilangan bulat positif K. Jadi, 32n +1 habis dibagi oleh2 tetapi tidak habis dibagi oleh 4.
Algoritma Pembagian tidak hanya berlaku untuk bilangan bulat positif saja, tetapi dapat diperluas untuk bilangan bulat. Bukti diserahkan sebagai latihan.
Teorema 2.3.4. Untuk setiap bilangan bulatadanb(a ≠ 0), terdapat dengantunggal pasangan bilangan bulat non-negatif (q, r) dengan sifat b = aq + r dan 0 ≤r 1 dikatakanprimajika untuk setiap bilanganbulat d dengan d >1, d ≠ p berlaku d ̸ p|. Bilangan bulat n >1 yang tidak prima dikatakan komposit.
PENDIDIKAN MATEMATIKA B 2017
99
Diperhatikan bahwa setiap bilangan bulat n > 1 mempunyai setidaknya satu faktor prima. Untuk n prima, faktor primanya adalah n sendiri. Untuk n bukan prima, misalkan a adalah faktor positif terkecil dari n. Diperoleh a merupakan bilangan prima, sebab jika a bukan prima, maka a = a1a2 untuk suatu 1 ≤a1, a2< a dan a1|n, kontradiksi dengan fakta bahwa a faktor positif terkecil dari n. Berikut diberikan suatu sifat yang bermanfaat dalam menentukan suatu bilangan adalah prima atau tidak. Teorema 2.4.2. Diberikan bilangan bulatn > 1. Jikankomposit, makan √ memiliki faktor prima yang kurang dari atau sama dengan n. Bukti. Diketahui n komposit. Misalkan n = 1 < a≤b dan a faktor positif terkecil dari n. √ hingga diperoleh a≤
ab untuk suatu a, b dengan Diperoleh n = ab≥a2, se-
n.
Diperhatikan bahwa 2 merupakan bilangan prima genap dan semua bilangan genap lebih dari dua merupakan bilangan komposit. Bilangan prima yang lain merupakan bilangan ganjil. Bilangan-bilangan prima yang kurang dari 50 adalah 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. Contoh 2.4.3. Diketahuipdanqbilangan prima yang memenuhip + q = 2013 dan p > q. Tentukan nilai dari p − q. Penyelesaian. Diperhatikan bahwa salah satu diantara p dan q bilangan genap sebab jika keduanya ganjil atau keduanya genap, maka p + q genap, kontradiksi dengan fakta bahwa p + q = 2013 bilangan ganjil. Karena bilangan prima genap hanya 2 dan p > q, maka diperoleh q = 2, sehingga didapat p = 2011. Diperhatikan bahwa 2011 tidak habis dibagi oleh sebarang bilangan prima yang kurang √ dari 2011, yaitu 2,3,5,7,11,13,17,19,23,29,31,37,41 atau 43. Jadi, 2011 merupakan bilangan prima. Akibatnya diperoleh p−q = 2011 − 2 = 2009.
Contoh 2.4.4. Tentukan semua bilangan bulat positifndengan sifat 3n−4, 4n−5 dan 5n − 3 merupakan bilangan prima. Penyelesaian. Diperhatikan bahwa jumlah ketiga bilangan tersebut adalah bilangan genap, maka setidaknya salah satu diantaranya merupakan bilangan
PENDIDIKAN MATEMATIKA B 2017
100
genap. Satu-satunya bilangan prima genap adalah 2. Dari ketiga bilangan terse-but, hanya 3n−4 dan 5n−3 yang mungkin bernilai genap. Untuk kasus 3n−4 = 2, diperoleh n = 2. Untuk kasus 5n− 3 = 2, diperoleh n = 1. Dapat dicek bahwa hanya n = 2 yang memenuhi kondisi ketiga bilangan tersebut merupakan bilangan prima.
Contoh 2.4.5. Tunjukkan bahwan4 + 4 merupakan bilangan prima jika danhanya jika n = 1. Penyelesaian. Diperhatikan bahwa n4+ 4 = n4+ 4n2+ 4 − 4n2= (n2+ 2)2 − (2n)2 = (n2− 2n + 2)(n2 + 2n + 2) = ((n− 1)2 + 1)((n + 1)2 + 1). Diperhatikan bahwa untuk n > 1 berlaku (n− 1)2 + 1 > 1 dan (n + 1)2 + 1 > 1. Akibatnya, n4 + 4 bukan bilangan prima untuk n > 1.
Contoh 2.4.6. Carilah 20 bilangan bilangan bulat berurutan yang masingmasingmerupakan bilangan komposit. Penyelesaian. Diperhatikan 20 bilangan berurutan berikut 21!+2, 21!+3, . . . , 21!+ 21. Untuk setiap i = 2, . . . , 21, 21! + i merupakan bilangan komposit sebab i|(20! + i).
Lebih dari 2000 tahun yang lalu, Euclid telah menunjukkan bahwa ada tak hingga banyak bilangan bulat positif yang merupakan bilangan prima. Teorema 2.4.7. Ada tak hingga banyaknya bilangan prima. Bukti. Diandaikan bilangan prima hanya berhingga banyak, katakan p1< p2< . . . < pm. Diperhatikan bilangan P = p1p2. . . pm + 1. Jika P prima, maka P > pm, kontradiksi dengan fakta bahwa pmbilangan prima terbesar. Akibatnya P haruslah komposit. Artinya P memiliki faktor prima, katakan p > 1. Diperhatikan bahwa p = pk untuk suatu k∈{1, 2, . . . , m}. Diperoleh bahwa pk|p1p2 . . . pk . . . pm+ 1. Artinya pk|1, suatu kontradiksi. Jadi, ada tak hingga
PENDIDIKAN MATEMATIKA B 2017
101
banyaknya bilangan prima.
Walaupun telah diketahui bahwa banyaknya bilangan prima ada tak berhingga, namun sampai saat ini masih belum ditemukan suatu formula untuk menentukan semua bilangan prima yang ada.
PENDIDIKAN MATEMATIKA B 2017
102
BAB III FAKTORISASI PRIMA 3.1
Pendahuluan
Sebagai kelanjutan dari konsep bilangan prima dan keterbagian, pada bagian ini dibahas mengenai faktorisasi prima pada bilangan bulat dan aplikasinya un-tuk menentukan banyak faktor dan jumlah faktor suatu bilangan bulat. Materi ini disampaikan pada Minggu ke-5 dan 6. Dengan mempelajari bab ini, diharapkan: 1. Mahasiswa bisa melakukan faktorisasi prima sebarang bilangan bulat. 2. Mahasiswa bisa menentukan banyak faktor bilangan bulat 3. Mahasiswa bisa menentukan jumlah faktor-faktor bilangan bulat 4. Mahasiswa bisa menerapkan sifat-sifat faktorisasi prima masalah bilangan bulat 3.2
Teorema Fundamental Aritmatik
Salah satu sifat dasar dari teori bilangan terkait dengan faktor prima diberikan sebagai berikut. Teorema 3.2.1 (Teorema Fundamental Aritmatik). Setiap bilangan bulatn > 1 dapat dinyatakan sebagai perkalian bilangan-bilangan prima secara tunggal. Bukti. Diberikan bilangan bulat n >1. Pertama-tama, akan ditunjukkan eksistensinya. Misalkan p1 faktor prima dari n. Jika p1 = n, maka n = p1 merupakan faktorisasi prima dari n. Jika p1< n, maka n = p1r1 dengan r1> 1. Jika r1 prima, maka n = p1p2 dengan p2 = r1 merupakan faktorisasi yang dimaksud. Jika r1komposit, maka r1= p2r2dengan p2prima dan r2>1, sehingga n = p1p2r2.Jika r2 prima, maka n = p1p2p3 dengan p3 = r3 merupakan faktorisasi yang di-maksud. Jika r2 komposit, maka secara rekursif diperoleh barisan bilangan bulat
PENDIDIKAN MATEMATIKA B 2017
103
r1> r2> . . . ≥ 1. Setelah sejumlah langkah, diperoleh pk+1= 1, sehingga dida-pat n = p1p2. . . pn merupakan faktorisasi yang dimaksud. Selanjutnya, akan ditunjukkan ketunggalannya. Diasumsikan n memiliki dua faktorisasi prima berbeda, yaitu: n = p1p2 . . . pk= q1q2 . . . qh dimana p1, p2, . . . , pk, q1, q2, . . . , qh bilangan prima dengan p1≤p2≤. . .≤pk dan q1≤q2≤. . .≤qh sehingga k-tupel (p1, p2, . . .) tidak sama dengan h-tupel (q1, q2, . . . , qh. Jelas bahwa k, h≥ 2. Misalkan n merupakan bilangan terkecil yang memiliki dua faktorisasi prima. Akan ditunjukkan terjadi suatu kontradiksi dengan menemukan bilangan yang lebih kecil dari n yang memiliki dua faktorisasi prima. Diperhatikan bahwa pi ≠qj untuk setiap i = 1, 2, . . . , k, j = 1, 2, . . . , h sebab jika ada yang sama, misalkan pk = qh = p, maka n′ = n/p = p1p2. . . pk−1 = q1q2 . . . qh−1dan 1< n′< n, kontradiksi dengan fakta bahwa n bilangan terkecilyang memiliki dua faktorisasi prima berbeda. Tanpa mengurangi keumuman, misalkan p1≤q1. Berdasarkan Algoritma Pembagian diperoleh: q1 = p1c1 + r1 q2 = p1c2 + r2 . . . qh = p1ch + rh dengan 1 ≤ri< p1, i = 1, . . . , h. Diperoleh bahwa n = q1q2 . . . qh= (p1c1+ r1)(p1c2+ r2) . . . (p1ch+ rh) Dengan menjabarkan bentuk pada ruas kanan persamaan tersebut diperoleh n = mp1 + r1r2. . . rh untuk suatu bilangan bulat m. Dengan mengambil n′ = r1r2 . . . rh, maka diperoleh n = p1p2 . . . pk= p1m + n′. Diperoleh bahwa p1|n′,yang artinya n′ = p1s untuk suatu bilangan bulat s. Berdasarkan pembuktian ek-sistensi faktorisasi prima diperoleh s dapat dituliskan sebagai perkalian bilangan-bilangan prima, katakan s = s1s2. . . si dengan s1, s2, . . . , si bilangan prima. Di lain pihak, dengan menggunakan faktorisasi r1, r2. . . , rh sebagai perkalian bilangan-bilangan prima, diperoleh n′ = t1t2. . . tj dengan t1, t2, . . . , tj bilangan
PENDIDIKAN MATEMATIKA B 2017
104
prima. Diperhatikan bahwa tu< p1 untuk setiap u = 1, 2 . . . , j, sehingga fak-torisasi n′ = t1t2. . . tj berbeda dengan n′ = p1s1s2. . . si. Akan tetapi n′< n, kontradiksi dengan fakta bahwa n bilangan terkecil yang memiliki dua faktorisasi prima berbeda.
Berdasarkan Teorema 3.2.1, diperoleh bahwa setiap bilangan bulat n > 1 dapat dituliskan secara tunggal dalam bentuk n = pα11 pα22 . . . pαkk dengan p1, p2, . . . , pk bilangan prima berbeda dan α1, α2, . . . , αk. Representasi ini dinamakan faktorisasi prima (faktorisasi kanonik ) dari n. Contoh 3.2.2. Tunjukkan bahwam5 + 3m4− 5m3− 15m2 + 4m + 12 ≠ 33 untuksetiap bilangan bulat positif m dan n. Penyelesaian. Diperhatikan bahwa m5+ 3m4 − 5m3 − 15m2+ 4m + 12 = (m − 2)(m − 1)(m + 1)(m + 2)(m + 3). Di lain pihak, 33 dapat dinyatakan sebagai perkalian maksimal sebanyak empat bilangan bulat berbeda, yaitu 33 = (−11)(−3)1(−1). Berdasarkan Teorema Fundamental Aritmatik, m5 + 3m4− 5m3− 15m2 + 4m + 12 ≠ 33 sebab 33 dapat dinyatakan sebagai perkalian maksimal sebanyak empat bilangan bulat berbeda, sedangkan m5 + 3m4−5m3−15m2 + 4m + 12 dapat dinyatakan sebagai perkalian lima bilangan bulat berbeda.
Contoh 3.2.3. Tentukan semua bilangan bulat positifnsehingga 28 + 211 + 2nmerupakan bilangan kuadrat sempurna. Penyelesaian. Misalkan 28 + 211 + 2n bilangan kuadrat sempurna. Artinya, k2= 28+211+2n= 2304+2n= 482+2n. Diperoleh 2n= k2−482= (k−48)(k+48).Berdasarkan ketunggalan dari faktorisasi prima, diperoleh k− 48 = 2s dan k + 48 = 2tuntuk suatu bilangan bulat positif s, t dengan s+t = n. Diperhatikanbahwa 2t−2s = 96 = 3.25 atau 2s(2t−s−1) = 3.25. Berdasarkan ketunggalan dari faktorisasi prima, diperoleh s = 5, s−t = 2, sehingga diperoleh n = s+ t = 12.
PENDIDIKAN MATEMATIKA B 2017
105
Dapat dicek bahwa faktorisasi prima dari perkalian dua bilangan bulat sama dengan perkalian dari faktorisasi prima dua bilangan tersebut. Hal ini memberikan suatu karakteristik lain terkait bilangan prima. Teorema 3.2.4. Diberikan bilangan bulatadanb. Jika bilangan primapmem-bagi ab, maka p membagi a atau p membagi b. Bukti. Karena p|ab, maka p harus muncul pada faktorisasi prima dari ab. Karena faktorisasi prima dari a, b dan ab tunggal dan faktorisasi prima dari ab merupakan perkalian faktorisasi prima dari a dan b, maka p harus muncul setidaknya pada salah satu faktorisasi prima dari a atau b, yang berarti p|a atau p|b.
De nisi 3.2.5. Diberikan bilangan bulatn > 1 dan bilangan primap. Bilanganpk dikatakan membagi penuh n, ditulis pk∥n, jika k adalah bilangan bulat positif terbesar sehingga pk|n. Contoh 3.2.6. Tentukan faktor terbesar dari 1001001001 yang kurang dari 10000. Penyelesaian. Diperhatikan bahwa 1001001001 = 1001 · 106 + 1001 = 1001(106 + 1) = 7 · 11 · 13 · (106 + 1). Karena x6+1 = (x2)3+1 = (x2+1)(x4−x2+1), maka diperoleh 106+1 = 101·9901. Jadi, 1001001001 = 7 · 11 · 13 · 101 · 9901. Dapat dicek bahwa faktor terbesar dari 1001001001 yang kurang dari 10000 adalah 9901.
Contoh 3.2.7. Tentukan bilangan bulat positifnyang memenuhi 2n∥31024− 1. Penyelesaian. Diperhatikan bahwa 210 = 1024 dan x2−y2 = (x + y)(x−y), sehingga diperoleh 210
3
29
29
29 28 28 = (3 + 1)(3 − 1) = (3 + 1)(3 + 1)(3 − 1) 29 28 27 21 20 = . . . = (3 + 1)(3 + 1)(3 + 1) . . . (3 + 1)(3 + 1)(3 − 1).
Berdasarkan Contoh 2.3.3, 2∥32k untuk setiap bilangan bulat positif k. jawabannya adalah 9 + 2 + 1 = 12.
PENDIDIKAN MATEMATIKA B 2017
Jadi,
106
Berdasarkan Teorema 3.2.1, diperoleh bahwa setiap bilangan bulat diban-gun oleh bilangan-bilangan prima. Karena pentingnya konsep bilangan prima, banyak peneliti telah memcoba menemukan rumus eksplisit dari bilangan-bilangan prima. Namun, sejauh ini usaha tersebut belum berhasil. Salah satu hasil yang diperoleh Goldbach dalam penelitiannya terkait bilangan prima diberikan sebagai berikut.
Teorema 3.2.8. Untuk setiap bilangan bulatntidak ada polinomialp(x) dengankoe sien bulat dengan sifat p(n) merupakan bilangan prima untuk setiap bilangan bilat n ≥ m. Bukti. Diberikan bilangan bulat m. Diandaikan terdapat polinomial yang memenuhi kondisi tersebut, katakan P (x) = akxk+ ak−1xk−1+ . . . + a1x + a0 dengan ak, ak−1, . . . , a0 bilangan bulat dan ak ≠ 0. Diperoleh p(m) = p bilangan prima. Diperhatikan bahwa p(m + pi) = ak(m + pi)k+ ak−1(m + pi)k−1+ . . . + a1(m + pi) + a0 dan untuk setiap bilangan bulat positif i berlaku J j
(m + pi)
() =mj + i mj−1(pi) +
j (2 )mj−2(pi)2
+ . . . + (jj1)m(pi)j−1 + (pi)j − untuksetiapj = 1, 2, . . . , k. Diperoleh bahwa (m + pi)j−mj kelipatan dari p, sehingga berlaku p(m+pi)−p(m) merupakan kelipatan dari p. Karena p(m) = p, maka diperoleh p(m + pi) merupakan kelipatan dari p untuk setiap bilangan bu-lat positif i. Berdasarkan asumsi diperoleh bahwa p(m + pi) prima untuk setiap bilangan bulat positif i. Akibatnya nilai yang mungkin untuk p(m + pi) adalah 0, p atau −p. Diperhatikan bahwa total akar persamaan p(x) = 0, p(x) = p dan p(x) = −p paling banyak 3k. Akibatnya terdapat tak hingga banyaknya i dengan sifat m + pi bukan solusi dari ketiga persamaan tersebut. Terjadi su-atu kontradiksi. Jadi, untuk setiap bilangan bulat n, tidak ada polinomial p(x) dengan koefisien bulat dengan sifat p(n) merupakan bilangan prima untuk setiap
PENDIDIKAN MATEMATIKA B 2017
107
bilanganbilatn≥m.
Walaupun belum ada rumus eksplisit dari bilangan prima, rata-rata banyaknya bilangan prima diantara bilangan bulat telah diketahui 100 tahun yang lalu. Fakta ini diberikan oleh Hadamard dan de la Vall´ee Poussin pada tahun 1896, yaitu: π(n)
lim
=1
dengan π(n) merupakan banyaknya bilangan prima yang kurang dari atau sama dengan n. 3.3
Banyak Faktor
Untuk setiap bilangan bulat positif n, banyaknya faktor positif dari n dinotasikan dengan τ(n). Jelas bahwa ∑ τ (n) =1. d|n Teorema 3.3.1. Jika n = pα11 pα22 . . . pαkk faktorisasi prima dari n, maka τ (n) = (α1 + 1)(α2 + 1) . . . (αk + 1). Bukti. Diperhatikan bahwa berdasarkan faktorisasi prima dari n, setiap fak-tor positif dari n berbentuk pb11pb22. . . pbkk , dengan 0 ≤bi≤αi, i = 1, 2, . . . , k. Diperoleh banyaknya faktor positif dari n sama dengan banyaknya kemungkinan nilai dari b1, b2, . . . , bn. Karena untuk setiap i, ada (αi +1) kemungkinan untuk bi, maka diperoleh banyaknya faktor positif dari n adalah (α1 +1)(α2 +1) . . . (αk +1).
Teorema 3.3Untuk.2. setiap bilangan bulat positifnberlaku ∏ (n) d=n2 .
PENDIDIKAN MATEMATIKA B 2017
d|n
108
Bukti. Diperhatikan bahwa ∏
∏
2
d|n
∏| =
∏|
∏n d
d=
d dn dn ∏| n
d d|n d|n ∏ n = nτ(n). d|n
= d n ( d. d ) = Jadi,
∏
| (n) d=n 2 .
dn
Contoh 3.3.3. Tentukan peluang sebarang bilangan dipilih dari faktor positif 1020merupakan kelipatan 1013. Penyelesaian. Diperhatikan bahwa setiap faktor positif dari 1020 berbentuk 2a5b dengan 0 ≤a, b≤ 20, sedangkan 1013 = 213513. Diperoleh faktor posi-tif dari faktor positif 1020 yang merupakan kelipatan 1013 berbentuk 2a5b den-gan 13 ≤a, b≤ 20, sehingga didapat banyaknya faktor yang memenuhi kondisi tersebut ada 8 × 8 = 64. Di lain pihak, banyak faktor positif dari 1020 adalah 21 × 21 = 441. Jadi, peluang sebarang bilangan dipilih dari faktor positif 1020 64 merupakan kelipatan 1013 adalah
441 . √
Teorema 3.3.4. Untuk setiap bilangan bulat positifnberlakuτ(n) ≤ 2
n.
Bukti. Misalkan d1 n + n. Bukti. Diberikan sebarang bilangan komposit n. Karena n komposit, maka √ berdasarkan Teorema 2.4.2 terdapat a faktor positif dari n dengan 1 < a≤ n
n
n. n
√
Karena a faktor dari n, maka a merupakan faktor dari n dengan a ≥ √ n = n. n Diperoleh 1, a, a, n merupakan faktor positif dari n, sehingga didapat σ(n) ≥ 1 + a + na + n > n + √n.
PENDIDIKAN MATEMATIKA B 2017
112
BAB IV FAKTOR PERSEKUTUAN DAN KELIPATAN PERSEKUTUAN 4.1
Pendahuluan Pada bagian ini dibahas konsep mengenai faktor persekutuan terbesar dan
kelipatan persekutuan terkecil bilangan-bilangan bulat. Faktorisasi prima yang telah dibahas pada Bab 2, pada pertemuan Minggu ke-8 dan 9 memunculkan konsep faktor persekutuan dan kelipatan persekutuan antara lebih dari satu bi-langan bulat. Dengan mempelajari bab ini, diharapkan: 1. Mahasiswa bisa menjelaskan pengertian faktor persekutuan dan faktor persekutuan terbesar. 2. Mahasiswa bisa menentukan FPB dua atau lebih bilangan bulat 3. Mahasiswa bisa menjelaskan pengertian kelipatan persekutuan dan keli-patan persekutuan terkecil 4. Mahasiswa bisa menentukan kelipatan persekutuan terkecil 5. Mahasiswa bisa menerapkan sifat-sifat FPB dan KPK pada masalah bilan-gan bulat 4.2
Faktor Persekutuan Terbesar
Untuk setiap bilangan bulat positif k, didefinisikan Dk sebagai himpunan semua faktor positif dari k. Jelas bahwa Dk merupakan himpunan berhingga. Definisi 4.2.1. Diberikan bilangan bulat positifmdann. Anggota terbesar darihimpunan Dm ∩ Dn disebut faktor persekutuan terbesar (greatest com-mon divisor) dari m dan n, dinotasikan dengan gcd(m, n). Bilangan m dan n dikatakan relatif prima jika gcd(m, n) = 1.
PENDIDIKAN MATEMATIKA B 2017
113
Beberapa sifat dasar dari faktor persekutuan terbesar diberikan sebagai berikut. Teorema 4.2.2. Diberikan bilangan bulat positifm, ndanp. a. Jika p prima, maka gcd(p, m) = p atau gcd(p, m) = 1. b. Jika d = gcd(m, n), m = dm′, n = dn′, maka gcd(m′, n′) = 1. c. Jika d = gcd(m, n), m = d′m”, n = d′n”, gcd(m”, n”) = 1, maka d′= d. d. Jika d′ faktor persekutuan dari m dan n, maka d′ membagi gcd(m, n). e. Jika px∥m dan py∥n, maka pmin(x,y)∥gcd(m, n). Lebih lanjut, jika m = pα11 . . . pαkk dan n = pβ11 . . . pβkk , αi, βi ≥ 0, i = 1, 2, . . . , k, maka min( α ,β ) min( α ,β ) gcd(m, n) =p 1 1 1 ...p k k k. f. Jika m = nq + r, maka gcd(m, n) = gcd(n, r). Contoh 4.2.3. Diberikand = gcd(7n + 5, 5n + 4), dimananadalah bilanganbulat positif. a. Buktikan bahwa untuk setiap bilangan bulat positif n berlaku d = 1 atau d = 3. b. Buktikan bahwa d = 3 jika dan hanya jika n = 3k + 1 untuk suatu bilangan bulat positif k. Penyelesaian. Diambil sebarang bilangan bulat positif n. a. Diperhatikan bahwa d|7n + 5 dan d|5n + 4, maka d|5(7n + 5) dan d|7(5n + 4). Akibatnya d|5(7n + 5) − 7(5n + 4) atau d|3. Artinya, d faktor positif dari 3. Jadi, d = 1 atau d = 3. b. Diperhatikan bahwa n dapat dinyatakan dalam salah satu bentuk berikut: 3k, 3k + 1 atau 3k + 1, untuk suatu bilangan bulat positif k. Jika n = 3k, maka 7n + 5 = 21k + 5 = 3(7k + 1) + 2 dan 5n + 4 = 15k + 4 = 3(5k + 1) + 1. Jika n = 3k + 1, maka 7n + 5 = 21k + 12 = 3(7k + 4) dan 5n + 4 = 15k + 9 =3(5k + 3). Jika n = 3k + 2, maka 7n + 5 = 21k + 19 = 3(7k + 6) + 1 dan
PENDIDIKAN MATEMATIKA B 2017
114
5n + 4 = 15k + 14 = 3(5k + 4) + 2. Diperoleh 3|7n + 5 dan 3|5n + 4 jika dan hanya jika n = 3k + 1 untuk suatu bilangan bulat positif k. Diperhatikan bahwa 3|7n + 5 dan 3|5n + 4 berakibat 3| gcd(7n + 5, 5n + 4) atau 3|d. Karena d|3 dan 3|d, maka d = 3. Jadi, d = 3 jika dan hanya jika n = 3k + 1 untuksuatu bilangan bulat positif k.
Contoh 4.2.4. Tunjukkan bahwa untuk setiap bilangan bulat positifn, pecahan 21n+ 4 tidak dapat disederhanakan. 14n + 3 Penyelesaian. Diambil sebarang bilangan bulat positif n. Diperhatikan bahwa 3(14n + 3) − 2(21 + 4) = 1. Akibatnya diperoleh gcd(21n + 4, 14n + 3)|1, yang 21n + 4 berarti gcd(21n + 4, 14n + 3) = 1. Dengan kata lain, pecahan sudah 14n + 3 dalam bentuk yang sederhana. Definisi dari faktor persekutuan terbesar dapat diperluas untuk lebih dari dua bilangan. Untuk sebarang bilangan bulat positif a1, a2, . . . , an, gcd(a1, a2, . . . , an) didefinisikan sebagai faktor persekutuan terbesar dari semua bilangan a1, a2, . . . , an. Berikut beberapa sifat terkait dengan faktor persekutuan terbesar dari beberapa bilangan bulat.
Teorema 4.2.5. Diberikana1, a2, . . . , as, m, n, p, dbilangan bulat positif. a. gcd(gcd(m, n), p) = gcd(m, gcd(n, p)). b. Jika d|ai, i = 1, 2 . . . , s, maka d| gcd(a1, a2, . . . , as). c. Jika ai= pα11i . . . pαkki , i = 1, . . . , s, maka min( α ,...,α ) 1s . . . pmin(kαk1,...,αks). gcd(a1, . . . , as) =p 1 11 Bilangan a1, a2, . . . , an dikatakan relatif prima jika gcd(a1, a2, . . . , an) = 1. Diperhatikan bahwa gcd(a1, a2, . . . , an) = 1 belum tentu berakibat gcd(ai, aj ) = 1 untuk 1 ≤i < j≤n. Jika a1, a2, . . . , an memenuhi gcd(ai, aj ) = 1 untuk 1 ≤ i < j ≤ n, maka a1, a2, . . . , andikatakan sepasang-sepasang relatif prima.
PENDIDIKAN MATEMATIKA B 2017
115
Contoh 4.2.6. Tentukan gcd(26− 22, 36− 32, 46− 42, 56− 52, 66− 62, 76− 72). Penyelesaian. Misalkan d = gcd(26−22, 36−32, 46−42, 56−52, 66−62, 76−72). Berdasarkan Contoh 2.2.7, untuk setiap bilangan bulat positif n berlaku 60|n6− n2. Akibatnya diperoleh 60|d. Diperhatikan bahwa karena 26 − 22= 60, maka diperoleh d|60. Jadi, d = 60.
4.3
Algoritma Euclid
Faktorisasi prima dapat membantu menentukan faktor persekutuan terbe-sar dari bilangan-bilangan bulat positif. Akan tetapi, untuk bilangan yang cukup besar faktorisasi prima tidak mudah dilakukan. Berikut dijelaskan salah satu algoritma yang bermanfaat dalam menentukan faktor persekutuan terbesar dari dua bilangan bulat positif m dan n, yaitu Algoritma Euclid . Algoritma ini menggunakan algoritma pembagian yang dilakukan berulang-ulang: m n
= nq1 + r1, = r1q2 + r2, . . .
1 ≤r1< n, 1 ≤r2< r1,
k−2 = rk−1qk + rk, 1 ≤rk< rk−1,
r
k−1 = rkqk+1 + rk+1, rk+1 = 0. Persamaan-persamaan tersebut ada sebanyak berhingga sebab n > r1> r2> . . . > rk. Berdasarkan sifat f. pada Teorema 4.2.2, diperoleh r
gcd(m, n) = gcd(n, r1) = gcd(r1, r2) = . . . = gcd(rk−1, rk) = rk. Contoh 4.3.1. Jika sebuah bilangan bulat positif kelipatan 305 dipilih secara acak, dengan setiap kelipatan mempunyai peluang yang sama untuk dipilih, ten-tukan peluang bilangan tersebuthabisdibagi 2013?
PENDIDIKAN MATEMATIKA B 2017
116
Penyelesaian. Berdasarkan Algoritma Euclid: 2013 =
6.305 + 183
305 = 1.183 + 122 183 = 1.122 + 61 122 = 2.61 + 0, diperoleh gcd(2013, 305) = gcd(305, 183) = gcd(183, 122) = gcd(122, 61) = 61. Diperoleh 2013 = 61.33 dan 305 = 61.5. Akibatnya, peluang yang dimaksud sama dengan peluang suatu bilangan kelipatan 5 habis dibagi 33, yaitu 331. Contoh 4.3Tentukan.2. nilai dari gcd(2014 + 2, 20142 + 2, 20143 + 2, . . .). Penyelesaian. Misalkan d = gcd(2014+2, 20142+2, 20143+2, . . .). Diperhatikanbahwa 20142 + 2 = 20142− 4 + 6 = (2014 − 2)(2014 + 2) + 6 = 2012(2014 + 2) + 6. Berdasarkan Algoritma Euclid diperoleh gcd(2014 + 2, 20142 + 2) = gcd(2016, 6) = 6. Akibatnya d|6. Di lain pihak, setiap bilangan pada barisan 2014 + 2, 20142 + 2, 20143 + 2, . . . habis dibagi 2. Lebih lanjut, karena 2014 = 2013 + 1 = 671.3 + 1, maka untuk setiap bilangan bulat positif k berlaku 2014k = 3ak + 1 untuk suatu bilangan bulat positif ak. Diperoleh 3|2014k + 2 untuk setiap bilangan bulat posi-tif k. Karena 2 dan 3 relatif prima, maka setiap bilangan pada barisan tersebut habis dibagi oleh 6, sehingga diperoleh 6|d. Karena d|6 dan 6|d, maka d = 6.
4.4
Identitas Bezout
Algoritma Euclid memberikan karakteristik penting terkait eksistensi penyelesaian persamaan linear dua variabel sebagai berikut. Teorema 4.4.1 (Identitas B´ezout). Untuk setiap bilangan bulat positifmdann,terdapat bilangan bulat x dan y dengan sifat mx + ny = gcd(m, n).
PENDIDIKAN MATEMATIKA B 2017
117
Bukti. Berdasarkan Algoritma Euclid diperoleh bahwa r1= m − nq1, r2= −mq2+ n(1 + q1q2), . . . . Karena ri+1 = ri−1 + riqi+1, maka secara umum diperoleh ri = mαi + nβi untuk i = 1, 2, . . . , k dengan α
i+1
i−1+qi+1αi
=α
β
i+1 =βi−1+qi+1βi untuk i = 2, 3, . . . , k− 1. Akibatnya diperoleh gcd(m, n) = rk = αkm + βkn. Identitas B´ezout memberikan karakteristik terkait penyelesaian persamaan berbentuk ax + by = c. Akibat 4.4.2. Diberikan bilangan bulata, b, c. Persamaanax + by = cmemilikipenyelesaian bulat (x, y) jika dan hanya jika gcd(a, b) membagi c. Identitas B´ezout juga memberikan karakteristik lain terkait konsep keterbagian. Teorema 4.4.3. Diberikan bilangan bulat positifa, bdan bilangan bulatc. Jikaa|bc dan gcd(a, b) = 1, maka a|c. Bukti. Kasus c = 0 cukup jelas. Diasumsikan c ≠ 0. Karena gcd(a, b) = 1, maka berdasarkan Identitas B´eout , ax + by = 1 untuk suatu bilangan bulat x dan y. Akibatnya diperoleh acx = bcy = c. Karena a|acx dan a|bcy, maka a|c. Teorema 4.4.4. Diberikan bilangan bulat positifa, byang relatif prima. Jikacbilangan bulat dengan sifat a|c dan b|c, maka ab|c . Bukti. Karena a|c, maka c = ax untuk suatu bilangan bulat x. Akibatnya b|ax. Karena gcd(a, b) = 1 dan b|ax, maka b|x. Diperoleh x = by untuk suatu bilangan bulat y, sehingga didapat c = aby atau ab|c.
Contoh 4.4.5. Tunjukkan bahwa untuk setiap bilangan primapdan bilangan ( ) bulat k dengan sifat 1 ≤ k < p berlaku p| kp .
PENDIDIKAN MATEMATIKA B 2017
118
Penyelesaian. Diambil sebarang bilangan prima p dan bilangan bulat k dengan sifat 1 ≤k < p. Diperhatikan bahwa k(k) = p (k − 1) . p p 1 − (
Diperoleh bahwa p membagi k p p membagi( k 4.5
p k
)
. Karena gcd(p, k) = 1, maka diperoleh bahwa
).
Kelipatan Persekutuan Terkecil
Untuk setiap bilangan bulat positif k, didefinisikan Mk sebagai himpunan semua kelipatan dari k. Berbeda dengan himpunan Dk yang didefinisikan sebelumnya, Mk merupakan himpunan tak hingga. Definisi 4.5.1. Diberikan bilangan bulat positifsdant. Anggota terkecil darihimpunan Ms ∩ Mt disebut kelipatan persekutuan terkecil (least common multiple) dari s dan t, dinotasikan dengan lcm(m, n). Teorema 4.5.2.
Diberikan bilangan bulat positif s dan t.
a. Jika lcm(s, t) = m, m = ss′= tt′, maka gcd(s′, t′) = 1. b. Jika m′ kelipatan persekutuan dari s dan t dan m′= ss′= tt′, gcd(s′, t′) =1, makam′ = lcm(s, t). c. Jika m; kelipatan persekutuan dari s dan t, maka lcm(s, t)|m′. d. Jika m|s dan n|s, maka lcm(m, n)|s. e. Untuk setiap bilangan bulat n berlaku n.lcm(s, t) = lcm(ns, nt). f. Jika s = pα11 . . . pαkk dan t = pβ11 . . . pβkk , αi, βi ≥ 0, i = 1, 2, . . . , k, maka lcm(s, t) =p
max( α ,β ) max( α ,β ) 1 1 1 ...p k k k.
Sifat berikut memberikan hubungan antara faktor persekutuan terbesar dengan kelipatan persekutuan terkecil.
PENDIDIKAN MATEMATIKA B 2017
119
Teorema 4.5.3. Untuk sebarang bilangan bulat positifmdannberlaku mn = gcd(m, n).lcm(m, n). Bukti. Misalkan m = pα11. . . pαkk dan n = pβ11. . . pβkk , αi, βi≥ 0, i = 1, 2, . . . , k. Berdasarkan Teorema 4.2.2 bagian e. dan Teorema 4.5.2 bagian f. diperoleh 1 1 1 1 . . . pkmax(αk,βk)+min(αk,βk) pα1+β α +β = 1 . . . p k k = mn. 1 k
gcd(m, n).lcm(m, n) =
p1
max(α ,β )+min(α ,β )
Contoh 4.5.4. Diketahuiadanbbilangan bulat positif dengana + b = 52 danlcm(a, b) = 168. Tentukan nilai dari ab. Penyelesaian. Misalkan d = gcd(a, b). Diperoleh d|52 dan d|168, sehingga d| gcd(52, 168). Karena 168 = 3.52+12, 52 = 4.12+4, 12 = 3.4, maka berdasarkanAlgoritma Euclid diperoleh gcd(168, 52) = 4, sehingga d|4. Diperhatikan bahwa 4|lcm(a, b), maka 4|a atau 4|b. Karena 4|a+b, maka 4|a dan |b, sehingga diperoleh 4|d. Jadi, d = 4. Berdasarkan Teorema 4.5.3, diperoleh ab = 4.168 = 724. Lebih lanjut, untuk setiap bilangan bulat positif a1, a2, . . . , an, keli-patan persekutuan terkecil dari a1, a2, . . . , an adalah bilangan bulat positif terkecil yang merupakan kelipatan dari masing-masing a1, a2, . . . , an, dinotasikan dengan lcm(a1, a2, . . . , an).
PENDIDIKAN MATEMATIKA B 2017
120
BAB V KEKONGRUENEN 5.1
Pendahuluan
Pada bagian ini dibahas konsep kekongruenan dan kelas residu. Topik ini menjadi bahan bahasan untuk Minggu ke-11 . Beberapa teorema terkenal dalam Teori Bilangan yang berkaitan dengan kekongruenan, seperti Teorema Euler dan Teorema Kecil Fermat, diberikan pada bagian ini. Setelah mempelajari topik bahasan pada bab ini yang meliputi modulo, kelas residu: 1. Mahasiswa mampu menjelaskan konsep kekongruenan, kelas residu 2. Mahasiswa mampu membuktikan Teorema Euler dan Teorema Wilson 3. Mahasiswa mampu menerapkan konsep kongruensi beserta sifat-sifat untuk memecahkan masalah yang berkaitan 5.2
Kekongruenan
Konsep kekogruenan pada bilangan bulat dikembangkan berdasarkan kon-sep Algoritma Pembagian. Definisi 5.2.1. Diberikan bilangan bulata, bdanmdenganm ≠ 0. Bilanganadan b dikatakan kongruen modulo m jika m membagi a−b, dinotasikan dengan a ≡ b (mod m). Jika m tidak membagi a − b, maka bilangan a dan b dikatakan tidak kongruen modulo m dan dinotasikan a ̸≡b (mod m). Relasi ”≡” pada definisi tersebut dinamakan relasi kongruensi. Beber-apa karakteristik dasar terkait dengan kekongruenan diberikan sebagai berikut. Teorema 5.2.2.
Diberikan bilangan bulat a, b, c, d dan m.
a. a ≡ a (mod m). b. Jika a ≡ b (mod m) dan b ≡ c (mod m), maka a ≡ c (mod m).
PENDIDIKAN MATEMATIKA B 2017
121
c. a ≡ b (mod m), maka b ≡ a (mod m). d. Jika a ≡ b (mod m) dan c ≡ d (mod m), maka a + c ≡ b + d (mod m) dan a − c ≡ b − d (mod m). e. Jika a ≡ b (mod m), maka untuk setiap bilangan bulat k berlaku ka ≡ kb (mod m). f. Jika a ≡ b (mod m) dan c ≡ d (mod m), maka ac ≡ bd (mod m). Secara umum, jika ai ≡ bi(mod m), i = 1, . . . , k, maka a1 . . . ak ≡ b1 . . . bk(mod m). Lebih lanjut, jika a ≡ b (mod m), maka untuk setiap bilangan bulat positif k berlaku ak ≡ bk(mod m). g. a ≡ b (mod mi), i = 1, . . . , k jika dan hanya jika a ≡ b (mod lcm(m1, . . . , mk)). Secara khusus, jika m1, . . . , mk sepasang-sepasang relatif prima, maka a ≡ b (mod mi), i = 1, . . . , k jika dan hanya jika a ≡ b (mod m1 . . . mk). Contoh 5.2.3. Tentukan sisa pembagian 62013oleh 37. Penyelesaian. Diperhatikan bahwa 36 =≡ −1 (mod 7), maka diperoleh 62013≡ 6.62012≡ 6.(62)1006≡ 6.(−1)1006≡ 1
(mod 37).
Jadi, sisa pembagian 62013 oleh 37 adalah 6. Contoh 5.2.4. Tentukan dua digit terakhir dari 32013. Penyelesaian. Diperhatikan bahwa 32013 = (35)40233 = (243)40227 ≡ 4340227 ≡ ≡ ≡ ≡
(1849)20127 (49)20127 (2401)10049.27 (1)1001323
≡
23 (mod 100).
PENDIDIKAN MATEMATIKA B 2017
122
Jadi, dua digit terakhir dari 32013 adalah 23.
Contoh 5.2.5. Tunjukkan bahwa 7 habis membagi 32n+1 + 2n+2untuk setiapbilangan bulat positif n. Penyelesaian. Diambil sebarang bilangan bulat positif n. Diperhatikan bahwa 32n+1≡ 3.9n≡ 3.2n (mod 7) dan 2n+2≡ 4.2n (mod 7). Akibatnya 32n+1 + 2n+2≡ 7.2n≡ 0
(mod 7).
Teorema 5.2.6. Diberikan bilangan bulata, bdann, n ≠ 0 dengan sifata = nq1+ r1, b = nq2+ r2, 0 ≤ r1, r2< |n|. a ≡ b (mod n) jika dan hanya jika r1 = r2 . Bukti. Diperhatikan bahwa a−b = n(q1−q2)+(r1−r2), maka diperoleh n|(a−b) jika dan hanya jika n|(r1−r2). Karena |r1−r2| 5. (mod 240).
Tunjukkan bahwa p8 ≡ 1
Penyelesaian. Diperhatikan bahwa 240 = 24.3.5.
Berdasarkan Teorema Ke-
cil Fermat, p2≡ 1 (mod 3) dan p4 ≡ 1 (mod 5). Karena gcd(p, 24) = 1 dan φ(24) = 8, maka berdasarkan Teorema Euler diperoleh p8 ≡ 1 (mod 16). Jadi, p8 ≡ 1 (mod m) untuk m = 3, 5 dan 16. Akibatnya p8 ≡ 1 (mod 240). Berdasarkan Teorema Euler diperoleh jika a dan m bilangan bulat posi-tif yang relatif prima, maka terdapat bilangan bulat positif x dengan sifat ax≡ 1 (mod m). De nisi 5.4.11. Diberikan bilangan bulat positifm. Bilangan bulat positifadikatakan memiliki order d modulo m, dinotasikan ordm(a) = d, jika d adalah bilangan bulat positif terkecil dengan sifat ad ≡ 1 (mod m).
PENDIDIKAN MATEMATIKA B 2017
132
Berdasarkan Teorema Euler, ordm(a) = d≤φ(m). Jika bilangan bulat positif x memenuhi ax≡ 1 (mod m), maka berdasarkan Teorema 5.2.11, agcd(x,d) ≡ 1
(mod m).
Karena gcd(x, d) ≤d dan d bilangan bulat positif terkecil dengan sifat ad≡ 1 (mod m), maka diperoleh gcd(x, d) = d. Artinya, d membagi x, sehingga diperoleh Teorema sebagai berikut. Teorema 5.4.12. Bilangan bulat positifxmemenuhiax≡ 1 (mod m) jika danhanya jika x kelipatan dari order a modulo m. Contoh 5.4.13. Tentukan order dari 8 modulo 11. Penyelesaian. Berdasarkan Teorema Kecil Fermat, diperoleh 810≡ 1 (mod 11). Akibatnya, ord11(8)|10. Diperhatikan bahwa 82≡ −2 (mod 11)dan 85≡ −1 (mod 11). Jadi, ord11(8) = 10.
PENDIDIKAN MATEMATIKA B 2017
133
BAB VI PERSAMAAN LINEAR DIOPHANTINE 6.1
Pendahuluan
Pada bagian ini dibahas konsep persamaan linear Diophantine dan eksis-tensi solusi bulat dari persamaan tersebut. Topik ini merupakan pokok bahasan pada Minggu ke-11 dan 12 . Lebih lanjut, diberikan karakteristik solusi bulat non-negatif persamaan linear Diophantine dua variabel. Setelah mempelajari bab ini diharapkan mahasiswa memiliki learning out-comes berupa: 1. Mahasiswa mampu menjelaskan pengertian Diophantine Linear 2. Mahasiswa mampu menyelesaikan soal-soal yang berkaitan dengan Diophantine Linear 6.2
Persamaan Linear Diophantine
Definisi 6.2.1. Diberikan bilangan bulat positifndana1, a2, . . . , an, bbilanganbulat dengan ai≠ 0, i = 1, 2, . . . , n. Persamaan a1x1+ a2x2+ · · · + anxn= b,
(6.1)
disebut persamaan linear Diophantine. Berikut diberikan syarat cukup dan perlu agar persamaan (6.1) memiliki solusi bulat. Teorema 6.2.2.
Persamaan (6.1) memiliki solusi bulat jika dan hanya jika gcd(a1, a2, . . . , an)|b.
Lebih lanjut, jika persamaan (6.1) memiliki solusi bulat, maka semua solusi bulat dari persamaan (6.1) dapat dinyatakan ke dalam n − 1 parameter.
PENDIDIKAN MATEMATIKA B 2017
134
Bukti. Misalkan d = gcd(a1, a2, . . . , an). Jika b tidak habis dibagi oleh d,maka persamaan (6.1) tidak memiliki solusi bulat sebab untuk setiap bilangan bulat x1, x2, . . . , xn, ruas kiri dari persamaan (6.1) habis dibagi oleh d sedangkan ruas kanannya tidak. Jika d|b, maka diperoleh persamaan (6.1) ekuivalen dengan a1′x1+ a2′x2+ · · · + an′xn= b′, (6.2) ′ ′ ′ ′ dengan a i = ai/d, ı = 1, 2, . . . , n dan b = b/d. Jelas bahwa gcd(a 1, a 2, . . . , a n) = ′
1. Akan digunakan induksi matematika untuk membuktikan persamaan (6.2) memiliki solusi bulat. Kasus n = 1. Persamaan (6.2) menjadi x1 = b atau −x1 = b. Diperoleh x1= b atau x1= −b merupakan solusi, dan solusi ini tidak berisi parameter. Diasumsikan persamaan (6.2) dengan n−1 variabel memiliki solusi bulat(n≥ 2). Akan dibuktikan bahwa persamaan (6.1) dengan n variabel memiliki solusi bulat. Misalkan dn−1 = gcd(a′1, a′2, . . . , a′n−1). Diperoleh bahwa setiap solusi bulat dari persamaan (6.2) memenuhi a1′x1+ a2′x2+ · · · + an′xn ≡ b′ yang ekuivalen dengan
(mod dn−1),
an′xn ≡ b′ (mod dn−1). Dengan mengalikan kedua ruas pada persamaan (6.2) dengan a′φ(dn
(6.3) )−1
1
dan
n menggunakan fakta bahwa an′φ(dn1)≡ 1 (mod dn−1), diperoleh xn ≡ c b . Artinya, x
(mod dn−1), dengan c = a =c+d t untuk suatu bilangan bulat n− n− n 1 1 n tn−1. Dengan mensubstitusi xnke persamaan (6.2), diperoleh a′1x1+ · · · + a′n−1xn−1= b − a′nc − a′ndn−1tn−1. ′φ(dn
1)−1 ′
Diperhatikan bahwa dn−1|(b′−a′nc−a′n−1dn−1tn−1) atau yang ekuivalen dengan a′nc ≡ b′(mod dn−1), sebab c = a′nφ(dn1)−1b′. Akibatnya, dengan membagi keduaruas persamaan terakhir dengan dn−1 diperoleh a”1x1+ a”2x2+ · · · + a”n−1xn−1= b”
PENDIDIKAN MATEMATIKA B 2017
(6.4)
135
dengan a”i = a′i/dn−1 untuk i = 1, 2, . . . , n dan b” = (b′−a′nc)/dn−1 + a′ntn−1. Karena gcd(a”1, a”2, . . . , a”n−1) = 1 maka sesuai asumsi induksi, persamaan (6.4) memiliki solusi bulat dan solusinya dapat ditulis ke dalam n− 2 parameter. Jika pada solusi tersebut ditambahkan xn = c + dn−1tn−1 maka diperoleh persamaan (6.2) memiliki solusi bulat dan solusinya dapat ditulis ke dalam n− 1 parameter.
Contoh 6.2.3. Tentukan bilangan bulatxdanyyang memenuhi persamaan a. 96x + 54y = 20. b. 96x + 54y = 12.
96 = 1.54 + 42 54 = 1.42 + 12 42 = 3.12 + 6 12 = 2.6 + 0. Diperoleh gcd(96, 54) = 6. a. Karena 6 ̸20,| maka berdasarkan Teorema 6.2.2 persamaan 96x + 54y = 20 tidak memiliki solusi bulat. b. Karena 6|12, maka berdasarkan Teorema 6.2.2 persamaan 96x + 54y = 20 memiliki solusi bulat. Akan dicari salah satu solusinya menggunakan Algo-ritma Euclid. Diperhatikan bahwa 6 = 42 − 3.12 12 = 54 − 42 42 = 96 − 54. Diperoleh 6 = 42 − 3(54 − 42) = 4.42 − 3.54 = 4(96 − 54) − 3.54 = 4.96 − 7.54,
PENDIDIKAN MATEMATIKA B 2017
136
sehingga didapat 12 = 8.96 + (−14)54. Jadi, x = 8 dan y = −14 memenuhi persamaan 96x + 54y = 12.
Teorema 6.2.2 memberikan suatu karakteristik dari setiap solusi bulat persamaan berbentuk ax + by = c. Teorema 6.2.4. Diberikana, bdancbilangan bulat dengan gcd(a, b)|c. Jika (x0, y0) merupakan solusi bulat dari persamaan ax + by = c, maka setiap solusi bulat dari persamaan tersebut dinyatakan dalam bentuk B a x = x0+
gcd(a, b) t, y = y0 − gcd(a, b) t
untuk suatu bilangan bulat t. Penyelesaian. Misalkan a = gcd(a, b)a′ dan b = gcd(a, b)b′. Diperoleh gcd(a′, b′) = 1. Diketahui (x0, y0) merupakan solusi bulat dari persamaan ax + by = c. Diper-oleh ax0 + by0 = c. Diambil sebarang (x, y) solusi bulat persamaan ax + by = c. Diperoleh ax + by = c = ax0+ by0 a(x − x0) = b(y0 − y). Dengan membagi kedua ruas persamaan tersebut dengan gcd(a, b) diperoleh a′(x − x0) = b′(y0 − y). Diperhatikan bahwa a′|a′(x−x0), maka a′|b′(y0−y). Karena gcd(a′, b′) = 1, maka a′|y0−y. Artinya, terdapat bilangan bulat s dengan sifat y0−y = a′s atau y = y0−a′s. Dengan cara yang sama, terdapat bilangan bulat t dengan sifat x = x0+ b′t. Dengan mensubstitusi x dan y ke persamaan terakhir diperoleh s = t. Jadi, B a x = x0+
gcd(a, b) t, y = y0 − gcd(a, b) t.
PENDIDIKAN MATEMATIKA B 2017
137
Contoh 6.2.5. Tentukan semua solusi bulat persamaan 96x + 54y = 12. Penyelesaian. Diperhatikan bahwa x = 8 dan y = −14 merupakan salah satu solusi persaman 96x + 54y = 12. Akibatnya diperoleh setiap solusi persamaan 96x + 54y = 12 berbentuk x = 8 + 9t, y = −14 − 16t untuk suatu bilangan bulat t.
Contoh 6.2.6. Tentukan semua triple(x, y, z) yang memenuhi persamaan 3x + 4y + 5z = 2013. Penyelesaian. Dari persamaan tersebut diperoleh 3x + 4y≡ 3 mod 5 ,artinya 3x + 4y = 3 + 5s untuk suatu bilangan bulat s .Salah satu solusi dari persamaan tersebut adalah : x = 1 + 3s ,y = −s. Berdasarkan Teorema 6.2.4, diperoleh x = 1 + 3s + 4t ,y = −s− 3t untuk suatu bilangan bulat t. Dengan mensubstitusi x dan y ke persamaan awal, didapat z = 402 −s. Jadi, semua solusinya adalah (x, y, z) = (1 + 3s + 4t,−s− 3t, 402 −s) untuk setiap pasangan bilangan bulat s, t.
Contoh 6.2.7. Diberikan bilangan bulat positifn. Diasumsikan terdapat 666triple berurutan bilangan bulat positif (x, y, z) yang memenuhi persamaan x + 2010y + 2010z = n. Tentukan nilai maksimum dan minimum dari n. Penyelesaian. Jawabannya maksimum 76379 dan minimum 74370. Misalkan n = 2010a + b dengan a dan b bilangan bulat dan 0 ≤b < 2010. Karena x ≡ n ≡ b (mod 2010), maka nilai yang mungkin untuk x adalah b, 2010 + b, . . . ,
PENDIDIKAN MATEMATIKA B 2017
138
2010(a− 1) + b. Untuk x = b + 2010i, 0 ≤i≤a− 1, diperoleh 2010(y + z) = 2010(a−i) atau y + z = a−i. Persamaan y + z = a−i memiliki a−i− 1 solusi bilangan bulat positif (y, z), yaitu (1, a−i− 1), . . . , (a−i− 1, 1). Akibatnya terdapat ∑ a−1
∑i a−1 a(a − 1)
(a
i 1) = − −
i= 2
i=0 =0 triple berurutan yang memenuhi kondisi yang ditentukan. Dari persamaan a(a−1) = 2 666, diperoleh a = 37. Jadi, nilai maksimum dari n sama dengan 37·2010+2009 = 76379 (diperoleh dengan mengambil b = 2009 ) dan nilai minimum dari n sama dengan 37 · 2010 = 74370 (diperoleh dengan mengambil b = 0).
6.3
Teorema Frobenius
Diperhatikan bahwa jika a dan b bilangan bulat positif dengan gcd(a, b) = 1, maka untuk setiap bilangan bulat n persamaan ax + by = n selalu memiliki solusi bulat. Berikut diberikan karakteristik yang menjamin eksistensi solusi bulat nonnegatif dari persamaan ax + by = n. Teorema 6.3.1 (Teorema Frobenius). Diberikan bilangan bulat positifadanb.Jika gcd(a, b) = 1, maka banyaknya bilangan bulat positif m yang tidak dapat dinyatakan ke dalam bentuk ar + bs = m untuk suatu bilangan bulat non-negatif r dan s sama dengan (a−1)(b−1). 2 Bukti. Misalkan bilangan bulat positif n dikatakan ”baik” jika terdapat bilanganbulat non-negatif r dan s dengan sifat ar+bs = n. Diperhatikan susunan berikut: 0 a
1 2 ... k. . . a − 1 . . . a + k . . . 2a − 1 a+1 a+2 2a + k . . . 3a− 1 2a 2a + 1 2a + 2 . . . ... ... ... ... ... ... ...
Setiap kolom membentuk barisan artimatik dengan beda a. Diperhatikan bahwa jika n baik, maka n + ka baik untuk setiap bilangan bulat positif k. Jelas bahwa setiap kelipatan dari b baik. Diperhatikan bahwa tidak ada dua kelipatan dari b, vb dan wb dengan 0 ≤ v, w ≤ a − 1, berada pada kolom yang sama sebab
PENDIDIKAN MATEMATIKA B 2017
139
jika tidak, maka vb≡wb (mod a). Akibatnya b(v−w) ≡ 0 (mod a). Karena gcd(a, b) = 1, maka v−w≡ 0 (mod a). Karena 0 ≤v, w≤a− 1, maka v = w. Selanjutnya, akan ditunjukkan setiap bilangan yang berada tepat di atas salah satu kelipatan vb, 0 ≤v≤a− 1, tidak baik. Sebarang bilangan yang berada tepat di atas vb berbentuk vb−ka untuk suatu bilangan bulat positif k. Jika bv − ka baik, maka ax + by = bv − ka untuk suatu bilangan bulat non-negatif x dan y. Diperoleh by ≤ ax + by = bv − ka ≤ bv, yang berarti 0 ≤ y < v < a.Akibatnya y̸≡v (mod a). Di sisi lain, dua bilangan yang terletak pada kolom yang sama kongruen modulo a. Diperoleh vb≡vb−ka≡ax + by (mod a), yang berarti bv≡by (mod a). Karena gcd(a, b) = 1, maka v≡y (mod a), suatu kontradiksi. Diperoleh banyaknya bilangan yang tidak baik sama dengan banyaknya bilangan yang berada tepat di atas bilangan berbentuk vb, 0 ≤v≤a− 1. Diperhatikan bahwa pada kolom ke j, terdapat (vb−j)/a bilangan yang berada di atas vb. Akibatnya diperoleh banyaknya bilangan yang tidak baik adalah a− 1 a−1 vb − j =(a − 1)(b − 1). ∑ ∑j a 2 v= 0 =0
Diperhatikan bahwa bilangan bulat positif terbesar yang tidak baik be-rada tepat di atas bilangan (a− 1)b, sehingga diperoleh bilangan terbesar yang tidak baik adalah (a− 1)b−a. Teorema 6.3.2. Diberikan bilangan bulat positifadanbyang saling prima.Persamaan ax + by = n tidak memiliki solusi bulat non-negatif x dan y untuk n = ab − a − b. Jika n > ab − a − b, maka persamaan tersebut memiliki solusi bulat non-negatif x dan y. Contoh 6.3.3. Diketahuinbilangan bulat positif dengan gcd(n, 1991) = 1. Tunn jukkan abhwa 1991 dapat ditulis sebagai jumlahan dua bilangan rasional positif dengan penyebut kurang dari 1991 jika dan hanya jika terdapat bilangan bulat positif m, a, b dengan m ≤ 10 dan mn = 11a + 181b.
PENDIDIKAN MATEMATIKA B 2017
140
Penyelesaian. (⇐ ) Diketahui m, a, b bilangan bulat positif dengan m≤ 10 dan mn = 11a + 181b. Diperoleh n = a + b , 1991 181m 11m dengan 181m, 11m < 1991. (⇒)Diketahui 1991n = ar + rb untuk suatu bilangan bulat positif a, b dengan gcd(a, r) = gcd(b, s) = 1 dan r, s < 1991. Tanpa mengurangi keumuman misalkan r = 181r1 dan s = 11s1 (1991 = 11.181). Diperoleh nr1s1 = 11as1 + 181br1. Akibatnya r1|11as1dan s1|181br1. Karena r1 k, diperoleh n≥bh≥ bk+1. Akan tetapi, n = a0 + a1b + · · · + akbk≤ (b− 1)(1 + b + · · · + bk = bk+1− 1 < bk+1, suatu kontradiksi. Kasus h = k. Diperhatikan bahwa a0+ a1b + · · · + akbk= c0+ c1b + · · · + ckbk, sehingga diperoleh b|(a0−c0). Di lain pihak, |a0−c0|< b, maka diperoleh a0 = c0. Akibatnya, didapat a1+ a2b + · · · + akbk= c1+ c2b + · · · + ckbk. Dengan mengulangi prosedur di atas, diperoleh a1 = c1, a2 = b2, . . . , ak = ck.
De nisi 7.2.2. Diberikan bilangan bulat positifndanb > 1. Penyajiannkedalam bentuk seperti pada (7.5) disebut representasi dari n dalam basis b, dinotasikan dengan n=a a k k−1. . . a0(b).
PENDIDIKAN MATEMATIKA B 2017
143
Khusus untuk b = 10, penyajian tersebut dinamakan representasi desimal dan cukup dituliskan dalam bentuk n = akak−1. . . a1a0. (Contoh: 2010 = 2010(10)). Contoh 7.2.3. Diberikanxydanyxbilangan bulat positif dua digit. Buktikanbahwa jumlahan keduanya merupakan bilangan komposit. Penyelesaian. Karena xy = 10x + y dan yx = 10y + x, maka jumlahan ked-uanya sama dengan 11x+11y = 11(x+y), yang merupakan bilangan komposit.
Contoh 7.2.4. Tentukan bilangan bulat yang terdiri dari 6 digit dengan angkaterakhir 7 dan menjadi 5 kali bilangan semula jika digit terakhir dipindahkan menjadi digit pertama. Penyelesaian. Misalkan bilangan tersebut abcde7. Diperoleh 7abcde = 5 ×abcde7. Dengan menjabarkan ke dalam representasi desimal diperoleh 7.105 + 104a + 103b + 102c + 10d + e
= 5(105a + 104b + 103c + 102d + 10e + 7)
⇔ 490000a + 49000b + 4900c + 490d + 49e = 699965 10000a + 1000b + 100c + 10d + e
= 14285.
Berdasarkan ketunggalan sistem desimal diperoleh a = 1, b = 4, c = 2, d = 8 dan e = 5. Jadi, bilangan yang dimaksud adalah 142857.
Contoh 7.2.5. Pada persamaan dibawah ini, masing-masing huruf merepresentasikan secara tunggal suatu digit dalam basis 10: (Y E) · (M E) = T T T. Tentukan nilai dari E + M + T + Y . Penyelesaian. Karena T T T = T·111 = T·3 ·37, maka salah satu dari Y E atau M E adalah 37, yang berakibat E = 37. Karena 0 ≤ T ≤ 9 dan T ·3 bilangan duadigit dengan digit terakhir 7, maka diperoleh T = 9, dan T T T = 999 = 27 · 37. Jadi, E + M + T + Y = 2 + 3 + 7 + 9 = 21.
PENDIDIKAN MATEMATIKA B 2017
144
Contoh 7.2.6. Tuliskan 1111011(2)ke dalam basis 10 dan tuliskan 2010 ke dalambasis 7. Penyelesaian. Diperhatikan bahwa
1111011(2) = 1 · 26 + 1 · 25 + 1 · 24 + 1 · 23 + 0 · 22 + 1 · 21 + 1 · 20 = 64 + 32 + 16 + 8 + 2 + 1 = 123. Diperolehrepresentasidesimaldari 1111011(2) adalah 123. Dengan membagi 2010 dengan 7 secara berulang-ulang, sisanya memberikan digit-digit dari representasi pada basis 7, dimulai dari yang terakhir. Digit per-tama adalah hasil bagi terakhir yang tak nol. Susunan perhitungannya diberikan sebagai berikut. 2010 7 2009 287 7 1
287 41 7 0 35 5 6
Jadi, 2010 = 5601(7).
Contoh 7.2.7. Beberapa himpunan yang terdiri dari bilangan-bilangan primaseperti {7, 83, 421, 659}, menggunakan setiap digit dari 9 digit tak nol tepat sekali. Tentukan jumlah terkecil yang mungkin dari anggota-anggota himpunan dengan kondisi tersebut yang bisa diperoleh. Penyelesaian. Jawabannya adalah 207. Diperhatikan bahwa digit 4,6 dan 8 tidak bisa muncul pada digit satuan, sehingga diperoleh jumlahan dari anggota-anggota himpunan dengan kondisi tersebut setidaknya 40 + 60 + 80 + 1 + 2 + 3 + 5 + 7 + 9 = 207.
Di lain pihak, nilai ini bisa didapatkan dari himpunan
{2, 5, 7, 43, 61, 89}. Contoh 7.2.8. Tentukan semua 11111(n)adalahkuadrat sempurna.
PENDIDIKAN MATEMATIKA B 2017
bilangan
bulat
positifnsehingga
145
Penyelesaian. Diperhatikan bahwa 11111 (n) = n4 + n3 + n2 + n + 1. n n 2 2 Jika n genap, maka n + dan n + + 1 adalah 2 bilangan bulat berurutan. 2 2 Diperoleh n2 n 2 ( n2 +
= n4 + n3 + 2 < n4+ n3+ n2+ n + 1 ( n )2 < n2 + 2 + 1 . Jadi, 11111(n) bukan kuadrat sempurna untuk bilangan genap n. Jika n ganjil, maka n2 + n2−12 dan n2 + n2 + 12 adalah bilangan bulat berurutan. Diperhatikan bahwa 2 )
n ( n2 + 2
1
2
− 2 )
< n4+ n3+ n2+ n + 1.
dan n ( n2 +
1
5n2
2
n
1
= n4 + n3 + 4 +2 + 2 n2−2n−3 4 3 2 4 = n +n +n +n+ 1 + (n−3)(n+ 1) = n4 +n3 +n2 +n+ 1 + .4 Untuk n bilangan ganjil lebih dari 3, 11111(n) berada diantara 2 bilangan bulat kuadrat berurutan, yaitu 2 +2 )
n
1
2
n
1
2
2 − 2 ) Dan (n2 + 2 + 2 ) . Jadi, 11111(n) bukan kuadrat sempurna untuk setiap bilangan positif lebih dari ( n2 +
3. Untuk n = 3, diperoleh
11111
(3)
= 121 = 112.
Jadi, bilangan bulat positif
yang memenuhi hanya n = 3. Pada contoh terakhir, diperoleh bahwa suatu bilangan bulat bukan kuadrat sempurna jika bilangan tersebut terletak di antara 2 bilangan kuadrat berurutan. Cara ini sangat bermanfaat dalam menyelesaikan beberapa masalah terkait persamaan Diophantine.
Dalam beberapa sistem numerik, basis tidak harus selalu bernilai kon-stan. Berikut salah satu contohnya.
PENDIDIKAN MATEMATIKA B 2017
146
Teorema 7.2.9. Setiap bilangan bulat positifkmempunyaiekspansi basis fak-torial yang tunggal, katakan (f1, f2, f3, . . . , fm), yang berarti bahwa k = 1! ·f1 + 2! ·f2 + 3! ·f3 + · · · + m! ·fm, dengan untuk setiap i = 1, 2, . . . , m, fi bilangan bulat, 0 ≤ fi ≤ i dan fm>0. Bukti. Diberikan bilangan bulat positif k. Diperhatikan bahwa terdapat dengan tunggal bilangan bulat positif m1 dengan sifat m1! ≤k < (m1 + 1)!. Berdasarkan Algoritma Pembagian, diperoleh k = m1!fm1 + r1 untuk suatu bilangan bulat positif fm1 dan bilangan bulat r1 dengan 0 ≤r1
