BAB II KETERBAGIAN
2.1
Pendahuluan
Pada pertemuan minggu ke-3, dan 4 ini dibahas konsep keterbagian, algoritma 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 pembagian 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 masing-masing merupakan bilangan bulat, tetapi pembagian bilangan yang satu dengan yang lain belum tentu merupakan bilangan bulat. Definisi 2.2.1. Diberikan bilangan bulat m dan n (n ̸= 0). Bilangan m dikatakan habis 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 bulat n. Sebaliknya, 0 ̸ | m untuk 11
setiap bilangan bulat tak nol m, sebab m ̸= 0 = k.0 untuk setiap bilangan bulat k. Dari definisi keterbagian diperoleh beberapa sifat dasar sebagai berikut. Teorema 2.2.2. Diberikan bilangan bulat x, y dan z. 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
y |y; x
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 tersebut 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 ). Contoh 2.2.3. Tentukan semua bilangan bulat n sehingga bilangan bulat.
n + 20 merupakan n − 13
Penyelesaian. Diperhatikan bahwa n − 13 + 33 33 n + 20 = =1+ . n − 13 n − 13 n − 13 n + 20 33 bulat, maka bulat. Artinya n − 13|33 atau n − 13 faktor n − 13 n − 13 dari 33. Karena faktor dari 33 adalah −33, −11, −3, −1, 1, 3, 11 dan 33, maka Jika
diperoleh nilai n yang mungkin adalah −20, 2, 10, 12, 14, 16, 24 atau 46. Dapat 12
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) dengan 2 3 sifat + = 1. m n Penyelesaian. Misalkan bilangan bulat positif n dan m memenuhi maka berlaku 2n + 3m
2 3 + = 1, m n
= mn
⇔ (m − 2)(n − 3) = 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 sampai 20. Sebanyak 20 anak secara bergiliran melakukan ekperimen terhadap kotakkotak 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 kelipatan 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 j 2.2.2, hal ini terjadi jika dan hanya jika anak ke melakukan eksperimen teri hadap kotak tersebut. Akibatnya, hanya kotak bernomor 1, 4, 9 dan 16 yang 13
dikenai eksperimen sebanyak bilangan ganjil, sehingga hanya kotak-kotak tersebut 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 kali n ≥ 1 bilangan bulat berurutan selalu habis dibagi oleh n!. (n! = 1 × 2 × . . . × n) Bukti. Pertama-tama, akan ditunjukkan perkalian n bilangan bulat positif berurutan habis dibagi oleh n!. Akan digunakan induksi matematika untuk membuktikannya. 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 pernyataan 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 ditunjukkan 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 ditunjukkan pernyataan 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). 14
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 dibuktikan dengan cara yang sama seperti bagian pertama dengan mengalikan hasil
kalinya dengan (−1)n .
Contoh 2.2.7. Tunjukkan bahwa n6 − n2 selalu habis dibagi oleh 60 untuk semua bilangan 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 15
bulat yang dinotasikan Z dapat dipartisi menjadi dua himpunan bagian, himpunan 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 positif n ≥ 1. Tunjukkan bahwa a. 2n dapat dinyatakan sebagai jumlahan dua bilangan ganjil berurutan. b. 3n dapat dinyatakan sebagai jumlahan tiga bilangan bulat berurutan. Penyelesaian. Untuk a., persamaan 2n = (2k − 1) + (2k + 1) memberikan penyelesaian 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 ganjil a, b dan c. Tunjukkan bahwa akar-akar persamaan kuadrat ax2 + bx + c = 0 bukan bilangan bulat. 16
Penyelesaian. Diandaikan bilangan bulat n merupakan akar persamaan ax2 + bx + c = 0. Diperoleh an2 + bn + c = 0. Akan ditinjau dua kasus, yaitu n bilangan genap 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.10. Diberikan k bilangan genap. Tunjukkan bahwa tidak ada bilangan ganjil n1 , n2 , . . . , nk dengan sifat 1 1 1 1= + + ... + . n1 n2 nk Penyelesaian. Diandaikan terdapat bilangan ganjil n1 , n2 , . . . , nk dengan sifat 1 1 1 1= + + ... + . n1 n2 nk Dengan menyamakan penyebut pada ruas kanan, diperoleh n1 n2 . . . nk = s1 + s2 + . . . + sk dengan s1 , s2 , . . . , sk bilangan ganjil. Diperhatikan bahwa ruas kiri merupakan 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 positif a dan 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. 17
Bukti. Diberikan sebarang bilangan bulat positif a dan b. Pertama-tama, ditunjukkan 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 sehingga 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 sama ketika dibagi oleh d > 1. Tentukan nilai d. Penyelesaian. Misalkan sisanya adalah r. Berdasarkan Algoritma Pembagian, diperoleh 1059 = q1 d + r 1417 = q2 d + r 2312 = q3 d + 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, 18
yang berarti d merupakan faktor dari 2.179, 7.179 dan 5.179. Karena d > 1, maka
diperoleh d = 179.
n
Contoh 2.3.3. Diberikan bilangan bulat positif n. Tunjukkan bahwa 32 +1 habis dibagi oleh 2 tetapi tidak habis dibagi oleh 4. n
Penyelesaian. Diperhatikan bahwa 32 merupakan bilangan ganjil, sehingga n
n
diperoleh 32 + 1 bilangan genap, yang berarti habis dibagi oleh 2. Karena 32 = n−1
(32 )2
n−1
= 92
n−1
= (8 + 1)2 , maka berdasarkan teorema Binomial Newton: ( ) ( ) ( ) m m−1 m m−2 2 m m m (x + y) = x + x y+ x y + ... + xy m−1 + y m , 1 2 m−1
dengan mengambil m = 2n−1 , x = 8 dan y = 1 diperoleh ( n−1 ) ( n−1 ) ( n−1 ) 2 2 2 2n−1 2n−1 2n−1 −1 m−2 (8 + 1) =8 + 8 + 8 + . . . + n−1 8 + 1. 1 2 2 −1 n
n−1
Akibatnya 32 + 1 = (8 + 1)2
+ 1 = (8K + 1) + 1 = 4(2K) + 2 untuk suatu
2n
bilangan bulat positif K. Jadi, 3 +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 bulat a dan b (a ̸= 0), terdapat dengan tunggal pasangan bilangan bulat non-negatif (q, r) dengan sifat b = aq + r dan 0 ≤ r < |a|.
2.4
Bilangan Prima Pada bagian ini dijelaskan mengenai konsep bilangan prima dan bilangan
komposit. Definisi 2.4.1. Bilangan bulat p > 1 dikatakan prima jika untuk setiap bilangan bulat d dengan d > 1, d ̸= p berlaku d ̸ | p. Bilangan bulat n > 1 yang tidak prima dikatakan komposit. 19
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 = a1 a2 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 bulat n > 1. Jika n komposit, maka n √ memiliki faktor prima yang kurang dari atau sama dengan n. Bukti.
Diketahui n komposit.
Misalkan n = ab untuk suatu a, b dengan
1 < a ≤ b dan a faktor positif terkecil dari n. Diperoleh n = ab ≥ a2 , se√ hingga diperoleh a ≤ 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. Diketahui p dan q bilangan prima yang memenuhi p + 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 positif n dengan 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 20
genap. Satu-satunya bilangan prima genap adalah 2. Dari ketiga bilangan tersebut, 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 bilan
gan prima.
Contoh 2.4.5. Tunjukkan bahwa n4 + 4 merupakan bilangan prima jika dan hanya 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 masing-masing merupakan 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 = p1 p2 . . . pm + 1. Jika P prima, maka P > pm , kontradiksi dengan fakta bahwa pm bilangan 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 |p1 p2 . . . pk . . . pm + 1. Artinya pk |1, suatu kontradiksi. Jadi, ada tak hingga 21
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.
Soal Latihan 1. Tunjukkan bahwa 15 + 25 + . . . + 995 + 1005 habis dibagi 10100, namun tidak habis dibagi 3. 2. Diketahui p dan p + 2 adalah bilangan prima yang lebih besar dari 3. Tentukan sisa dari p ketika dibagi oleh 6. 3. Tentukan bilangan bulat positif n terbesar sehingga n + 10 habis membagi n3 + 100. 4. Tunjukkan bahwa untuk setiap bilangan bulat positif n berlaku n5 −5n3 +4n habis dibagi oleh 120. 5. Diketahui x, y dan z adalah bilangan prima yang memenuhi persamaan 34x − 51y = 2012z. Tentukan nilai dari x + y + z. 6. Tentukan semua bilangan bulat positif n sehingga n4 + 4n merupakan bilangan prima. 7. Diketahui m dan n adalah bilangan bulat yang memenuhi m2 + 3m2 n2 = 30n2 + 517. Tentukan nilai dari 2m2 n2 . 8. Tunjuukan bahwa jika |ab| ̸= 1, maka a4 +4b4 merupakan bilangan komposit. 9. Diberikan polinomial p(x) = xn +a1 xn−1 +. . .+an−1 x+an dengan a1 , a2 , . . . , an bilangan bulat. Jika p(0) dan p(1) keduanya bilangan ganjil, tunjukkan bahwa p(x) tidak memiliki akar bulat.
22
10. Tentukan semua bilangan positif p dengan sifat p, p+8 dan p+16 merupakan bilangan prima. 11. Tentukan semua bilangan bulat n yang memenuhi bulat.
3n2 + 4n + 5 bilangan 2n + 1
12. (a) Tunjukkan bahwa jika bilangan bulat a dan b bersisa 1 ketika dibagi oleh 4, maka ab bersisa 1 ketika dibagi oleh 4. (b) Tunjukkan ada tak hingga banyaknya bilangan prima berbentuk 4k−1. 13. Tentukan semua pasangan bilangan prima berbeda (p, q) sehingga p2 +7pq+ q 2 merupakan bilangan kuadrat sempurna.
23
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 untuk 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 bulat n > 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 = p1 r1 dengan r1 > 1. Jika r1 prima, maka n = p1 p2 dengan p2 = r1 merupakan faktorisasi yang dimaksud. Jika r1 komposit, maka r1 = p2 r2 dengan p2 prima dan r2 > 1, sehingga n = p1 p2 r2 . Jika r2 prima, maka n = p1 p2 p3 dengan p3 = r3 merupakan faktorisasi yang dimaksud. Jika r2 komposit, maka secara rekursif diperoleh barisan bilangan bulat
24
r1 > r2 > . . . ≥ 1. Setelah sejumlah langkah, diperoleh pk+1 = 1, sehingga didapat n = p1 p2 . . . pn merupakan faktorisasi yang dimaksud. Selanjutnya, akan ditunjukkan ketunggalannya. Diasumsikan n memiliki dua faktorisasi prima berbeda, yaitu: n = p 1 p 2 . . . p k = q1 q2 . . . q h 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 = p1 p2 . . . pk−1 = q1 q2 . . . qh−1 dan 1 < n′ < n, kontradiksi dengan fakta bahwa n bilangan terkecil yang memiliki dua faktorisasi prima berbeda. Tanpa mengurangi keumuman, misalkan p1 ≤ q1 . Berdasarkan Algoritma Pembagian diperoleh: q1 = p1 c1 + r1 q2 = p1 c2 + r2 .. . qh = p1 ch + rh dengan 1 ≤ ri < p1 , i = 1, . . . , h. Diperoleh bahwa n = q1 q2 . . . qh = (p1 c1 + r1 )(p1 c2 + r2 ) . . . (p1 ch + rh ) Dengan menjabarkan bentuk pada ruas kanan persamaan tersebut diperoleh n = mp1 + r1 r2 . . . rh untuk suatu bilangan bulat m. Dengan mengambil n′ = r1 r2 . . . rh , maka diperoleh n = p1 p2 . . . pk = p1 m + n′ . Diperoleh bahwa p1 |n′ , yang artinya n′ = p1 s untuk suatu bilangan bulat s. Berdasarkan pembuktian eksistensi faktorisasi prima diperoleh s dapat dituliskan sebagai perkalian bilanganbilangan prima, katakan s = s1 s2 . . . si dengan s1 , s2 , . . . , si bilangan prima. Di lain pihak, dengan menggunakan faktorisasi r1 , r2 . . . , rh sebagai perkalian bilangan-bilangan prima, diperoleh n′ = t1 t2 . . . tj dengan t1 , t2 , . . . , tj bilangan 25
prima. Diperhatikan bahwa tu < p1 untuk setiap u = 1, 2 . . . , j, sehingga faktorisasi n′ = t1 t2 . . . tj berbeda dengan n′ = p1 s1 s2 . . . 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α1 1 pα2 2 . . . pαk k 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 bahwa m5 + 3m4 − 5m3 − 15m2 + 4m + 12 ̸= 33 untuk setiap 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 positif n sehingga 28 + 211 + 2n merupakan bilangan kuadrat sempurna. Penyelesaian. Misalkan 28 + 211 + 2n bilangan kuadrat sempurna. Artinya, k 2 = 28 +211 +2n = 2304+2n = 482 +2n . Diperoleh 2n = k 2 −482 = (k−48)(k+48). Berdasarkan ketunggalan dari faktorisasi prima, diperoleh k − 48 = 2s dan k + 48 = 2t untuk suatu bilangan bulat positif s, t dengan s + t = n. Diperhatikan bahwa 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.
26
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 bulat a dan b. Jika bilangan prima p membagi 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.
Definisi 3.2.5. Diberikan bilangan bulat n > 1 dan bilangan prima p. Bilangan pk 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 positif n yang memenuhi 2n ∥31024 − 1. Penyelesaian. Diperhatikan bahwa 21 0 = 1024 dan x2 − y 2 = (x + y)(x − y), sehingga diperoleh 10
32
9
9
9
8
8
= (32 + 1)(32 − 1) = (32 + 1)(32 + 1)(32 − 1) 9
8
7
1
0
= . . . = (32 + 1)(32 + 1)(32 + 1) . . . (32 + 1)(32 + 1)(3 − 1). k
Berdasarkan Contoh 2.3.3, 2∥32 untuk setiap bilangan bulat positif k. Jadi,
jawabannya adalah 9 + 2 + 1 = 12.
27
Berdasarkan Teorema 3.2.1, diperoleh bahwa setiap bilangan bulat dibangun 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 bulat n tidak ada polinomial p(x) dengan koefisien 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) = ak xk + ak−1 xk−1 + . . . + a1 x + 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 j j j−1 (m + pi) = m + m (pi) + mj−2 (pi)2 i 2 ( ) j +... + m(pi)j−1 + (pi)j j−1 untuk setiap j = 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 bulat 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 suatu kontradiksi. Jadi, untuk setiap bilangan bulat n, tidak ada polinomial p(x) dengan koefisien bulat dengan sifat p(n) merupakan bilangan prima untuk setiap 28
bilangan bilat n ≥ 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) =1 n→∞ n/ log n lim
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α1 1 pα2 2 . . . pαk k faktorisasi prima dari n, maka τ (n) = (α1 + 1)(α2 + 1) . . . (αk + 1). Bukti. Diperhatikan bahwa berdasarkan faktorisasi prima dari n, setiap faktor positif dari n berbentuk pb11 pb22 . . . 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.3.2. Untuk setiap bilangan bulat positif n berlaku ∏
d=n
d|n
29
τ (n) 2
.
Bukti. Diperhatikan bahwa 2 ∏ ∏ ∏ ∏ ∏n d = d d= d d d|n d|n d|n d|n d|n ( ) ∏ ∏ n d. = = n = nτ (n) . d d|n
Jadi,
∏
d|n
d=n
τ (n) 2
.
d|n
Contoh 3.3.3. Tentukan peluang sebarang bilangan dipilih dari faktor positif 1020 merupakan kelipatan 1013 . Penyelesaian. Diperhatikan bahwa setiap faktor positif dari 1020 berbentuk 2a 5b dengan 0 ≤ a, b ≤ 20, sedangkan 1013 = 213 513 . Diperoleh faktor positif dari faktor positif 1020 yang merupakan kelipatan 1013 berbentuk 2a 5b dengan 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 positif n berlaku τ (n) ≤ 2 n. Bukti. Misalkan d1 < d2 < . . . < dk faktor-faktor positif dari n yang kurang √ dari atau sama dengan n. Diperoleh bahwa faktor lain yang tersisa adalah n n n , ,..., . d1 d2 dk √ Akibatnya diperoleh τ (n) ≤ 2k ≤ 2dk ≤ 2 n.
30
3.4
Jumlah Faktor
Untuk setiap bilangan bulat positif n, jumlah semua faktor positif dari n, termasuk 1 dan n, dinotasikan dengan σ(n). Jelas bahwa σ(n) =
∑
d.
d|n
Teorema 3.4.1. Jika n = pα1 1 pα2 2 . . . pαk k faktorisasi prima dari n, maka σ(n) =
pα1 1 +1 − 1 pαk +1 − 1 ... k . p1 − 1 pk − 1
Bukti. Diperhatikan bahwa setiap faktor positif dari n berbentuk pa11 pa22 . . . pakk dengan 0 ≤ bi ≤ αi , i = 1, 2, . . . , k. Setiap faktor positif dari n muncul tepat sekali pada penjabaran perkalian (1 + p1 + . . . + pα1 1 ) . . . (1 + pk + . . . + pαk k ). Akibatnya diperoleh σ(n) = (1 + p1 + . . . + pα1 1 ) . . . (1 + pk + . . . + pαk k ) =
pα1 1 +1 − 1 pαk +1 − 1 ... k . p1 − 1 pk − 1
Contoh 3.4.2. Tentukan jumlah semua faktor positif genap dari 10000. Penyelesaian. Diperhatikan bahwa setiap faktor positif dari 10000 berbentuk 2a 5b dimana a, b bilangan bulat dengan 1 ≤ a ≤ 5 dan 0 ≤ b ≤ 5. Setiap faktor genap dari 10000 muncul tepat sekali pada penjabaran perkalian (2 + 22 + 23 + 24 + 25 )(1 + 5 + 52 + 53 + 54 + 55 ). Akibatnya diperoleh (2 + 22 + 23 + 24 + 25 )(1 + 5 + 52 + 53 + 54 + 55 ) = 62. 31
56 − 1 = 242172. 5−1
Diperhatikan bahwa p prima jika dan hanya jika faktor positif dari p hanya 1 dan p, yang berarti σ(p) = p + 1. Akibatnya diperoleh karakteristik dari jumlah faktor terkait bilangan prima. Teorema 3.4.3. Bilangan bulat positif p merupakan bilangan prima jika dan hanya jika σ(p) = p + 1. Teorema 3.4.4. Untuk setiap bilangan komposit n berlaku σ(n) > 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. √ Karena a faktor dari n, maka na merupakan faktor dari n dengan na ≥ √nn = n. Diperoleh 1, a, na , n merupakan faktor positif dari n, sehingga didapat σ(n) ≥ √ 1 + a + na + n > n + n.
Soal Latihan 1. Tentukan bilangan bulat positif terkecil yang memiliki tepat 12 faktor positif. 2. Diketahui n = 231 319 . Tentukan banyaknya faktor positif dari n2 yang kurang dari n tetapi tidak membagi n. 3. Berapa banyak pembagi genap dan pembagi ganjil dari 56 − 1. 4. Tentukan bilangan bulat positif terkecil n yang mempunyai tepat 2013 faktor positif dan merupakan kelipatan dari 2013. 5. Tentukan semua nilai n sehingga σ(n) merupakan bilangan ganjil. 6. Tunjukkan bahwa untuk setiap bilangan bulat positif n berlaku τ (n) ≤ √ 3n. 7. Diberikan polinomial p(x) dengan koefisien bilangan bulat dan terdapat bilangan bulat berbeda a, b, c, d dengan sifat p(a) = p(b) = p(c) = p(d) = 5. Tunjukkan bahwa tidak ada bilangan bulat k dengan sifat f (k) = 8. 32
8. Diberikan n = pa11 pa22 . . . pakk dan m = pb11 pb22 . . . pbkk dengan p1 , p2 , . . . , pk bilangan prima berbeda dan a1 , a2 , . . . , ak , b1 , . . . , bk bilangan bulat nonnegatif. Tentukan banyaknya faktor positif dari n yang merupakan faktor dari m. 9. Bilangan bulat positif n dikatakan sempurna jika n sama dengan jumlahan semua faktor positif dari n yang kurang dari n. Tunjukkan bahwa (a) jika n bilangan sempurna, maka ∑1 d|n
d
= 2.
(b) untuk setiap bilangan bulat positif k dan bilangan prima p, pk bukan bilangan sempurna. 10. Diberikan bilangan bulat positif k. Tunjukkan bahwa hanya ada berhingga banyak bilangan bulat positif n dengan sifat σ(n) = n + k. 11. Diberikan bilangan bulat positif n dengan sifat 24|n + 1. Tunjukkan bahwa 24|σ(n).
33
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 bilangan 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 kelipatan persekutuan terkecil 4. Mahasiswa bisa menentukan kelipatan persekutuan terkecil 5. Mahasiswa bisa menerapkan sifat-sifat FPB dan KPK pada masalah bilangan 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 positif m dan n. Anggota terbesar dari himpunan Dm ∩ Dn disebut faktor persekutuan terbesar (greatest common divisor) dari m dan n, dinotasikan dengan gcd(m, n). Bilangan m dan n dikatakan relatif prima jika gcd(m, n) = 1.
34
Beberapa sifat dasar dari faktor persekutuan terbesar diberikan sebagai berikut. Teorema 4.2.2. Diberikan bilangan bulat positif m, n dan p. 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α1 1 . . . pαk k dan n = pβ1 1 . . . pβkk , αi , βi ≥ 0, i = 1, 2, . . . , k, maka min(α1 ,β1 )
gcd(m, n) = p1
min(αk ,βk )
. . . pk
.
f. Jika m = nq + r, maka gcd(m, n) = gcd(n, r). Contoh 4.2.3. Diberikan d = gcd(7n + 5, 5n + 4), dimana n adalah bilangan bulat 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 35
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 untuk suatu bilangan bulat positif k.
Contoh 4.2.4. Tunjukkan bahwa untuk setiap bilangan bulat positif n, 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. Diberikan a1 , a2 , . . . , as , m, n, p, d bilangan 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α1 1i . . . pαk ki , i = 1, . . . , s, maka min(α11 ,...,α1s )
gcd(a1 , . . . , as ) = p1
min(αk1 ,...,αks )
. . . pk
.
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 , . . . , an dikatakan sepasang-sepasang relatif prima. 36
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
= nq1 + r1 ,
1 ≤ r1 < n,
n
= r1 q2 + r2 , .. .
1 ≤ r2 < r 1 ,
rk−2
= rk−1 qk + rk ,
1 ≤ rk < rk−1 ,
rk−1 = rk qk+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 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, tentukan peluang bilangan tersebut habis dibagi 2013?
37
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 1 sama dengan peluang suatu bilangan kelipatan 5 habis dibagi 33, yaitu . 33 Contoh 4.3.2. Tentukan nilai dari gcd(2014 + 2, 20142 + 2, 20143 + 2, . . .). Penyelesaian. Misalkan d = gcd(2014+2, 20142 +2, 20143 +2, . . .). Diperhatikan bahwa 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 positif 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 B´ ezout Algoritma Euclid memberikan karakteristik penting terkait eksistensi penye-
lesaian persamaan linear dua variabel sebagai berikut. Teorema 4.4.1 (Identitas B´ezout). Untuk setiap bilangan bulat positif m dan n, terdapat bilangan bulat x dan y dengan sifat mx + ny = gcd(m, n). 38
Bukti. Berdasarkan Algoritma Euclid diperoleh bahwa r1 = m − nq1 ,
r2 = −mq2 + n(1 + q1 q2 ), . . . .
Karena ri+1 = ri−1 + ri qi+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 = αk m + βk n. Identitas B´ezout memberikan karakteristik terkait penyelesaian persamaan berbentuk ax + by = c. Akibat 4.4.2. Diberikan bilangan bulat a, b, c. Persamaan ax + by = c memiliki penyelesaian 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 positif a, b dan bilangan bulat c. Jika a|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 positif a, b yang relatif prima. Jika c bilangan 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 prima p dan bilangan p bulat k dengan sifat 1 ≤ k < p berlaku p| . k 39
Penyelesaian. Diambil sebarang bilangan prima p dan bilangan bulat k dengan sifat 1 ≤ k < p. Diperhatikan bahwa ( ) ( ) p p−1 k =p . k k−1 ( ) p Diperoleh bahwa p membagi k . Karena gcd(p, k) = 1, maka diperoleh bahwa k ( ) p p membagi . k
4.5
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 positif s dan t. Anggota terkecil dari himpunan 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, maka m′ = 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α1 1 . . . pαk k dan t = pβ1 1 . . . pβkk , αi , βi ≥ 0, i = 1, 2, . . . , k, maka max(α1 ,β1 )
lcm(s, t) = p1
max(αk ,βk )
. . . pk
.
Sifat berikut memberikan hubungan antara faktor persekutuan terbesar dengan kelipatan persekutuan terkecil. 40
Teorema 4.5.3. Untuk sebarang bilangan bulat positif m dan n berlaku mn = gcd(m, n).lcm(m, n). Bukti. Misalkan m = pα1 1 . . . pαk k dan n = pβ1 1 . . . pβkk , αi , βi ≥ 0, i = 1, 2, . . . , k. Berdasarkan Teorema 4.2.2 bagian e. dan Teorema 4.5.2 bagian f. diperoleh max(α1 ,β1 )+min(α1 ,β1 )
gcd(m, n).lcm(m, n) = p1
max(αk ,βk )+min(αk ,βk )
. . . pk
= pα1 1 +β1 . . . pαk k +βk = mn.
Contoh 4.5.4. Diketahui a dan b bilangan bulat positif dengan a + b = 52 dan lcm(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 berdasarkan Algoritma 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 , kelipatan 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 ).
Soal Latihan 1. Buktikan bahwa untuk setiap bilangan bulat positif n, pecahan tidak dapat disederhanakan. 2. Tentukan nilai dari
2013 ∑
gcd(k, 7).
k=1
41
n2 + n − 1 n2 + 2n
3. Diberikan bilangan bulat positif a, b dan c. Tunjukkan bahwa (a) gcd(ca, cb) = c gcd(a, b). (b) gcd(a, bc) = gcd(a, gcd(a, b)c). (c) gcd(a2 , b2 ) = (gcd(a, b))2 . (d) jika gcd(a, b) = 1, maka gcd(a + b, a2 − ab + b2 ) = 1 atau 3. 4. Tentukan banyaknya bilangan bulat positif k dengan sifat lcm(66 , 88 , k) = 1212 . 5. Tentukan semua pasangan bilangan bulat positif (a, b) yang memenuhi gcd(a, b) + lcm(a, b) = a + b + 6. 6. Tentukan bilangan bulat positif m dan n yang memenuhi m2 + n2 = 85113 dan lcm(m, n) = 1764. 7. Tentukan banyaknya tripel bilangan bulat positif berurutan (a, b, c) dengan sifat lcm(a, b) = 1000 dan lcm(b, c) = lcm(a, c) = 2000. 8. Tiga bilangan bulat positif a1 < a2 < a3 memenuhi gcd(a1 , a2 , a3 ) = 1 dan gcd(a1 , a2 ), gcd(a2 , a3 ), gcd(a3 , a1 ) > 1. Tentukan nilai minimal yang mungkin dari a1 + a2 + a3 . 9. Diberikan bilangan bulat positif n. Tunjukkan bahwa jika n = pα1 1 pα2 2 . . . pαk k faktorisasi prima dari n, maka terdapat sebanyak (2α1 + 1)(2α2 + 1) . . . (2αk + 1) pasangan bilangan bulat positif berbeda (a, b) dengan sifat lcm(a, b) = n. 10. Diberikan p1 , p2 , . . . , pk bilangan prima berbeda dan a1 , a2 , . . . , ak bilangan bulat positif berbeda. Tentukan banyaknya cara memfaktorkan pa11 pa22 . . . pakk menjadi perkalian dua bilangan bulat positif xy yang memenuhi x > y > 1 dan gcd(x, y) = 1. 11. Tunjukkan bahwa untuk setiap bilangan bulat positif a, b dan c berlaku (gcd(a, b, c))2 (lcm(a, b, c))2 = . lcm(a, b)lcm(a, c)lcm(b, c) gcd(a, b) gcd(a, c) gcd(b, c) 42
12. Tunjukkan bahwa untuk setiap bilangan bulat positif a dan b berlaku jika lcm(a, a + 5) = lcm(b, b + 5), maka a = b. 13. Diberikan bilangan bulat positif m dan n dengan m ganjil. Tunjukkan bahwa gcd(2m − 1, 2n + 1) = 1 14. Diberikan bilangan bulat positif n. Tentukan faktor persekutuan terbesar dari
( ) ( ) ( ) 2n 2n 2n , ,..., . 3 2n − 1 1
43
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 bulat a, b dan m dengan m ̸= 0. Bilangan a dan 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. Beberapa 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). 44
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 62013 oleh 37. Penyelesaian. Diperhatikan bahwa 36 =≡ −1 (mod 7), maka diperoleh 62013 ≡ 6.62012 ≡ 6.(62 )1006 ≡ 6.(−1)1006 ≡ 1 Jadi, sisa pembagian 62013 oleh 37 adalah 6.
Contoh 5.2.4. Tentukan dua digit terakhir dari 32013 . Penyelesaian. Diperhatikan bahwa 32013 = (35 )402 33 = (243)402 27 ≡ 43402 27 ≡ (1849)201 27 ≡ (49)201 27 ≡ (2401)100 49.27 ≡ (1)100 1323 ≡ 23 (mod 100). 45
(mod 37).
Jadi, dua digit terakhir dari 32013 adalah 23.
Contoh 5.2.5. Tunjukkan bahwa 7 habis membagi 32n+1 + 2n+2 untuk setiap bilangan 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 bulat a, b dan n, n ̸= 0 dengan sifat a = 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 | < |n|, maka diperoleh n|(a − b)
jika dan hanya jika r1 = r2 .
Diperhatikan bahwa Teorema 3.2.4 dapat dinyatakan dalam konsep kekongruenan sebagai berikut. Akibat 5.2.7. Diberikan bilangan prima p. Jika x dan y bilangan bulat dengan sifat xy ≡ 0 (mod p), maka x ≡ 0 (mod p) atau y ≡ 0 (mod p). Hal ini merupakan salah satu contoh kesamaan yang terdapat dalam beberapa konsep teori bilangan: p|xy (notasi keterbagian), xy ≡ 0 (mod p) (notasi kekongruenan) dan p = kxy (notasi persamaan Diophantine). Beberapa aplikasi dari Teorema 4.4.3 dan Teorema 4.4.4 diberikan sebagai berikut. Akibat 5.2.8. Diberikan bilangan bulat positif m dan bilangan bulat a, b dan c dengan c ̸= 0. Jika ac ≡ bc (mod m), maka a ≡ b (mod 46
m ). gcd(c, m)
Akibat 5.2.9. Diberikan bilangan bulat positif m dan a bilangan bulat yang relatif prima dengan m. Jika a1 dan a2 bilangan bulat dengan sifat a1 ≡ a2 (mod m), maka a1 a ≡ a2 a (mod m). Contoh 5.2.10. Tentukan semua bilangan prima p dan q dengan sifat p + q = (p − q)3 . Penyelesaian. Misalkan bilangan prima p dan q memenuhi p + q = (p − q)3 . Diperhatikan bahwa (p − q)3 = p + q ̸= 0, diperoleh p ̸= q yang berarti p dan q relatif prima. Karena p − q ≡ 2p (mod p + q), maka diperoleh 0 ≡ 8p3 (mod p + q). Karena p dan q relatif prima, maka p dan p + q relatif prima, sehingga diperoleh 0 ≡ 8 (mod p + q). Artinya p + q|8. Dapat dicek bahwa bilangan prima (p, q)
yang memenuhi hanya (3, 5) atau (5, 3).
Berikut diberikan sifat yang bermanfaat dalam menyederhanakan bentuk pangkat pada relasi kongruensi. Teorema 5.2.11. Diberikan bilangan bulat m, a dan b dengan a dan b relatif prima terhadap m. Jika x dan y bilangan bulat positif dengan sifat ax ≡ bx
(mod m) dan
ay ≡ by
(mod m),
maka agcd(x,y) ≡ bgcd(x,y)
(mod m).
Bukti. Berdasarkan Identitas B´ezout, terdapat bilangan bulat tak negatif u dan v dengan sifat gcd(x, y) = ux − vy. Diperoleh aux ≡ bux
(mod m) dan avy ≡ bvy
(mod m),
sehingga berlaku aux bvy ≡ avy bux mod m. Karena gcd(a, m) = gcd(m, n) = 1, maka diperoleh agcd(x,y) ≡ aux−vy ≡ bux−vy ≡ bgcd(x,y)
(mod m).
47
5.3
Kelas Residu Berdasarkan Teorema 5.2.2 bagian a. b. dan c., diperoleh bahwa untuk
sebarang bilangan bulat positif m, setiap bilangan bulat dapat diklasifikasikan secara tunggal ke dalam suatu kelas berdasarkan sisanya ketika dibagi oleh m. Jelas bahwa terdapat sebanyak m kelas. Definisi 5.3.1. Diberikan bilangan bulat positif n. Himpunan bilangan bulat S disebut himpunan kelas residu lengkap modulo n jika untuk setiap i dengan 0 ≤ i ≤ n − 1, terdapat s ∈ S dengan sifat i ≡ s mod n. Diperhatikan bahwa {a, a+1, a+2, . . . , a+m−1} merupakan himpunan kelas residu lengkap modulo m untuk sebarang bilangan bulat a. Contoh 5.3.2. Diberikan bilangan bulat positif n. Pernyataan-pernyataan dibawah ini benar. a. n2 ≡ 0 atau 1 (mod 3); b. n2 ≡ 0 atau ±1 (mod 5); c. n2 ≡ 0 atau 1 atau 4 (mod 8); d. n3 ≡ 0 atau ±1 (mod 9); e. n3 ≡ 2 atau 3 atau 5 (mod 7); f. n4 ≡ 0 atau 1 (mod 16). Bukti diserahkan sebagai latihan. Contoh 5.3.3. Tunjukkan bahwa tidak ada bilangan bulat x dan y yang memenuhi x2 − 5y 2 = 2013. Penyelesaian. Diandaikan bilangan bulat x dan y memenuhi x2 − 5y 2 = 2013. Diperhatikan bahwa x2 − 5y 2 ≡ 0 atau ±1 (mod 5). Di sisi lain, 2013 ≡ 3
(mod 5), suatu kontradiksi.
48
Contoh 5.3.4. Diberikan m bilangan genap positif. Diasumsikan bahwa {a1 , a2 , . . . , am } dan
{b1 , b2 , . . . , bm }
dua himpunan kelas residu lengkap modulo m. Tunjukkan bahwa {a1 + b1 , a2 + b2 , . . . , am + bm } bukan himpunan kelas residu lengkap modulo m. Penyelesaian. Diandaikan {a1 + b1 , a2 + b2 , . . . , am + bm } himpunan kelas residu lengkap modulo m. Diperoleh 1 + 2 + . . . + n ≡ (a1 + b1 ) + (a2 + b2 ) + . . . + (am + bm ) ≡ (a1 + a2 + . . . + am ) + (b1 + b2 + . . . + bm ) ≡ 2(1 + 2 + . . . + m)
(mod m),
m(m + 1) . Kontradiksi den2 m(m + 1) gan fakta bahwa untuk bilangan genap m, m ̸ | . Jadi, {a1 + b1 , a2 + 2 b2 , . . . , am + bm } bukan himpunan kelas residu lengkap modulo m.
sehingga 1 + 2 + . . . + m ≡ 0 (mod m) atau m|
Teorema 5.3.5. Diberikan bilangan bulat positif m dan a, b bilangan bulat dengan gcd(a, m) = 1. Jika S himpunan kelas residu lengkap modulo m, maka T = aS + b = {as + b : s ∈ S} merupakan himpunan kelas residu lengkap modulo m. Bukti. Diketahui S himpunan kelas residu lengkap modulo m. Diperoleh bahwa banyak anggota dari S ada sebanyak m, misalkan S = {s1 , s2 , . . . , sm } dengan si ̸≡ sj , i ̸= j dan untuk setiap i = 0, 1, 2, . . . , m − 1 terdapat j dengan sifat sj ≡ i mod m. Diperhatikan bahwa T = {as + b : s ∈ S}, maka diperoleh banyak anggota dari T ada sebanyak m, sehingga cukup ditunjukkan setiap anggotanya tidak kongruen satu sama lain dalam modulo m. Diandaikan terdapat asi + b ≡ asj + b (mod m) untuk suatu 1 ≤ i < j ≤ m. Diperoleh asi ≡ asj (mod m). Karena gcd(a, m) = 1, maka diperoleh si ≡ sj (mod m). Kontradiksi 49
dengan fakta si ̸≡ sj , i ̸= j. Jadi, T merupakan himpunan kelas residu lengkap
modulo m.
Selanjutnya, diberikan hubungan antara kelas residu dengan persamaan kongruensi linear. Teorema 5.3.6. Diberikan bilangan bulat positif m. Jika a, b bilangan bulat dengan gcd(a, m) = 1, maka terdapat bilangan bulat x dengan sifat ax ≡ b (mod m) dan semua bilangan x yang memenuhi kondisi tersebut berada pada tepat satu kelas residu modulo m. Bukti. Misalkan {c1 , c2 . . . , cm } himpunan kelas residu lengkap modulo m. Berdasarkan Teorema 5.3.5, {ac1 − b, ac2 − b, . . . , acm − b} merupakan himpunan kelas residu lengkap. Akibatnya, terdapat ci dengan sifat aci − b ≡ 0 (mod m), dengan kata lain ci merupakan solusi persamaan kongruensi ax ≡ b (mod m). Lebih lanjut, jika x dan x′ solusi persamaan kongruensi ax ≡ b (mod m), maka berlaku ax ≡ ax′ (mod m). Karena gcd(a, m) = 1, maka diperoleh x ≡ x′ (mod m).
Khusus untuk b = 1, pada Teorema 5.3.6 diperoleh bahwa jika gcd(a, m) = 1, maka terdapat x dengan sifat ax ≡ 1 (mod m). Bilangan x tersebut disebut invers dari a modulo m, dinotasikan dengan a−1 atau
1 a
(mod m). Karena se-
mua bilangan x yang memenuhi kondisi ax ≡ 1 (mod m) berada pada tepat satu kelas residu modulo m, maka invers dari a modulo m terdefinisi dengan baik. Teorema 5.3.7 (Teorema Wilson). Untuk setiap bilangan prima p berlaku (p − 1)! = −1 (mod p). Bukti. Untuk kasus p = 2 dan p = 3 cukup jelas. Diambil sebarang bilangan prima p ≥ 5. Misalkan S = {2, 3, . . . , p − 2}. Karena p prima, maka untuk sebarang s ∈ S memiliki invers tunggal s′ ∈ {1, 2, . . . , p − 1}. Lebih lanjut, s′ ̸= 1 dan s′ ̸= p − 1, akibatnya s′ ∈ S. Diperhatikan bahwa s′ ̸= s sebab jika s′ = s, maka s2 ≡ 1 (mod p), sehingga diperoleh p|s−1 atau p|s+1. Hal ini tidak 50
mungkin sebab s+1 < p. Akibatnya diperoleh bahwa anggota-anggota dari S dap−3 pasangan berbeda (s, s′ ) dengan sifat ss′ ≡ 1 (mod p). 2 p−3 persamaan kongruensi tersebut diperoleh (p − 2)! ≡ 1 2
pat dipartisi menjadi Dengan mengalikan
(mod p), sehingga didapat (p − 1)! ≡ −1 (mod p).
Diperhatikan bahwa konvers dari Teorema Wilson benar, yaitu jika (n − 1)! ≡ −1 (mod n) untuk suatu bilangan bulat positif n ≥ 2, maka n prima, sebab jika n = n1 n2 untuk suatu bilangan bulat positif n1 , n2 ≥ 2, maka n1 |1.2. . . . n1 . . . (n − 1) + 1, suatu kontradiksi. Hal ini memberikan cara lain mengetahui suatu bilangan merupakan bilangan prima atau tidak. Namun, untuk n yang cukup besar hal ini sulit dilakukan. Contoh 5.3.8. Diberikan p bilangan prima dengan p ≡ 1 (mod 4). Tunjukkan bahwa
[(
) ]2 p−1 ! ≡ −1 2
(mod p).
Penyelesaian. Berdasarkan Teorema Wilson diperoleh −1 ≡ (p−1)! ≡
∏ 1≤i≤(p−1)/2
i(p−i) ≡
∏
[( −i ≡ (−1) 2
1≤i≤(p−1)/2
(p−1)/2
) ]2 p−1 ! 2
(mod p).
Karena p ≡ 1 (mod 4), maka (−1)(p−1)/2 = 1. Jadi, [( ) ]2 p−1 ! ≡ −1 (mod p). 2
5.4
Teorema Kecil Fermat dan Teorema Euler Untuk setiap bilangan bulat positif m, banyaknya bilangan bulat positif
n yang kurang dari m dan relatif prima dengan m dinotasikan dengan φ(n). Fungsi φ disebut fungsi Euler. Jelas bahwa φ(1) = 1 dan untuk setiap bilangan prima p, φ(p) = p − 1. Lebih lanjut, jika n bilangan bulat positif dengan sifat φ(n) = n − 1, maka n prima. Beberapa karakteristik lain dari fungsi Euler diberikan sebagai berikut. 51
Teorema 5.4.1. Untuk setiap bilangan prima p dan bilangan bulat positif a berlaku φ(pa ) = pa − pa−1 . Teorema 5.4.2. Jika a dan b bilangan bulat positif yang relatif prima, maka φ(ab) = φ(a)φ(b). Bukti. Disusun bilangan 1, 2, . . . , ab sebagai berikut: 1 a+1 .. .
2 a+2 .. .
... a . . . 2a .. .. . . a(b − 1) + 1 a(b − 1) + 2 . . . ab. Jelas bahwa di antara bilangan-bilangan 1, 2, . . . , ab terdapat φ(ab) bilangan yang relatif prima dengan ab. Di lain pihak, terdapat φ(a) kolom yang mengandung bilangan-bilangan yang relatif prima dengan a. Karena setiap kolom merupakan himpunan kelas residu lengkap modulo b, maka terdapat tepat φ(b) bilangan pada masing-masing kolom yang relatif prima dengan b. Akibatnya, banyaknya bilangan yang relatif prima dengan ab pada susunan tersebut adalah φ(a)φ(b). Jadi,
φ(ab) = φ(a)φ(b).
Berdasarkan Teorema 5.4.1 dan Teorema 5.4.2 diperoleh karakteristik nilai fungsi Euler dari setiap bilangan bulat positif. Teorema 5.4.3. Diberikan bilangan bulat positif n. Jika n = pα1 1 pα2 2 . . . pαk k faktorisasi prima dari n, maka ( )( ) ( ) 1 1 1 1− ... 1 − . φ(n) = n 1 − p1 p2 pk Contoh 5.4.4. Tunjukkan bahwa ada tak hingga banyaknya bilangan bulat positif n dengan sifat 10|φ(n). Penyelesaian. Diambil n = 11k , k = 1, 2, . . .. Diperoleh φ(11k ) = 11k −11k−1 =
10.11k−1 .
Definisi 5.4.5. Diberikan bilangan bulat positif m. Himpunan bilangan bulat S disebut himpunan kelas residu tereduksi lengkap modulo m jika untuk setiap 0 ≤ i ≤ n − 1 dengan gcd(i, m) = 1, terdapat s ∈ S dengan sifat i ≡ s (mod m). 52
Jelas bahwa suatu himpunan kelas residu tereduksi lengkap modulo m memiliki sebanyak φ(m) anggota. Teorema 5.4.6. Diberikan bilangan bulat positif m dan a dengan gcd(a, m) = 1. Jika S himpunan kelas residu tereduksi lengkap modulo m, maka himpunan T = aS = {as|s ∈ S}, merupakan himpunan kelas residu tereduksi lengkap modulo m. Diberikan bilangan bulat positif m dan S = {a1 , a2 , . . . , aφ(m) } himpunan kelas residu tereduksi lengkap modulo m. Berdasarkan eksistensi dan ketunggalan invers dalam modulo m, dapat ditunjukkan bahwa himpunan invers anggota-anggota dari S, dinotasikan dengan −1 −1 {a−1 1 , a2 , . . . , aφ(m) }
atau
{
1 1 1 , ,..., a1 a2 aφ(m)
} ,
merupakan himpunan kelas residu tereduksi lengkap modulo m. Teorema 5.4.7 (Teorema Euler). Jika a dan m bilangan bulat positif dengan gcd(a, m) = 1, maka aφ(m) ≡ 1 (mod m). Bukti. Misalkan S = {a1 , a2 , . . . , aφ(m) } himpunan semua bilangan bulat positif yang kurang dari m dan relatif prima dengan m. Karena gcd(a, m) = 1, maka berdasarkan Teorema 5.4.6 berlaku {aa1 , aa2 , . . . , aaφ(m) } merupakan himpunan kelas residu tereduksi lengkap modulo m. Akibatnya diperoleh (aa1 )(aa2 ) . . . (aaφ(m) ) ≡ a1 a2 . . . aφ(m)
(mod m).
Karena gcd(ak , m) = 1, k = 1, 2, . . . , φ(m), maka diperoleh aφ(m) ≡ 1
(mod m).
Dengan mengambil m bilangan prima, maka Teorema Euler menjadi Teorema Kecil Fermat. 53
Teorema 5.4.8 (Teorema Kecil Fermat). Jika a bilangan bulat positif dan p bilangan prima, maka ap ≡ a (mod p). Contoh 5.4.9. Diberikan bilangan prima p ≥ 7. Tunjukkan bahwa 11 . . . 1} | {z (p−1) kali
habis dibagi oleh p. Penyelesaian. Diperhatikan bahwa 11 . . . 1} = | {z (p−1) kali
10p−1 − 1 . 9
Karena gcd(10, p) = 1, maka berdasarkan Teorema Kecil Fermat diperoleh p|10p−1 − 1, sehingga 11 . . . 1} | {z (p−1) kali
habis dibagi oleh p.
Contoh 5.4.10. Diberikan bilangan prima p > 5. Tunjukkan bahwa p8 ≡ 1 (mod 240). Penyelesaian. Diperhatikan bahwa 240 = 24 .3.5. Berdasarkan Teorema Kecil 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 positif yang relatif prima, maka terdapat bilangan bulat positif x dengan sifat ax ≡ 1 (mod m). Definisi 5.4.11. Diberikan bilangan bulat positif m. Bilangan bulat positif a dikatakan memiliki order d modulo m, dinotasikan ordm (a) = d, jika d adalah bilangan bulat positif terkecil dengan sifat ad ≡ 1 (mod m).
54
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 positif x memenuhi ax ≡ 1 (mod m) jika dan hanya 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.
Soal Latihan 1. Tunjukkan bahwa 7|22225555 + 55552222 . 2. Berapakah sisa pembagian 4343
43
oleh 100?
3. Tentukan digit ratusan dari 20132013 . 4. Tentukan semua bilangan bulat n1 , n2 , . . . , n12 yang memenuhi n41 + n42 + . . . + n412 = 2013. 5. Tentukan sisa pembagian 683 + 883 oleh 49. 6. Tunjukkan bahwa tidak ada bilangan bulat positif x dan y dengan sifat x3 = 2y + 15. 7. Tentukan order dari 5 modulo 12. 8. Tunjukkan bahwa untuk setiap bilangan bulat positif n berlaku n9 ≡ n3 (mod 504).
55
9. Diberikan p dan q bilangan prima berbeda. Tunjukkan bahwa untuk setiap bilangan bulat a berlaku pq|(apq − ap − aq + a). 10. Tunjukkan bahwa untuk setiap bilangan genap positif n berlaku n2 |2n! − 1. 11. Tunjukkan bahwa untuk setiap bilangan prima p > 5 berlaku p4 ≡ 1 (mod 240). 12. (a) Tentukan jumlah semua bilangan bulat positif yang kurang dari 2013 dan relatif prima dengan 2013. (b) Tentukan jumlah semua bilangan bulat positif yang kurang dari 4026 dan relatif prima dengan 2013. 13. Tentukan banyaknya bilangan bulat positif m < 2013 dengan sifat {2013, 4026, 6039, . . . , 2013m} merupakan himpunan kelas residu lengkap modulo m. 14. Diberikan p bilangan prima. Tunjukkan bahwa p membagi abp − bap untuk setiap bilangan bulat positif a dan b. 15. Tunjukkan bahwa untuk setiap bilangan bulat positif n berlaku ∑
φ(d) = n.
d|n
16. Tunjukkan bahwa untuk setiap bilangan prima ganjil p berlaku 12 .32 . . . . (p − 2)2 ≡ 22 .42 . . . (p − 1)2 ≡ (−1)(p−1)/2
56
(mod p).
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 outcomes 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 positif n dan a1 , a2 , . . . , an , b bilangan bulat dengan ai ̸= 0, i = 1, 2, . . . , n. Persamaan a1 x1 + a2 x2 + · · · + an xn = 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.
57
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 a′1 x1 + a′2 x2 + · · · + a′n 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 a′1 x1 + a′2 x2 + · · · + a′n xn ≡ b′
(mod dn−1 ),
yang ekuivalen dengan a′n xn ≡ b′
(mod dn−1 ).
(6.3)
Dengan mengalikan kedua ruas pada persamaan (6.2) dengan a′n φ(dn−1 )−1 dan menggunakan fakta bahwa a′n φ(dn−1 ) ≡ 1 (mod dn−1 ), diperoleh xn ≡ c (mod dn−1 ), dengan c = a′n φ(dn−1 )−1 b′ . Artinya, xn = c + dn−1 tn−1 untuk suatu bilangan bulat tn−1 . Dengan mensubstitusi xn ke persamaan (6.2), diperoleh a′1 x1 + · · · + a′n−1 xn−1 = b − a′n c − a′n dn−1 tn−1 . Diperhatikan bahwa dn−1 |(b′ − a′n c − a′n−1 dn−1 tn−1 ) atau yang ekuivalen dengan a′n c ≡ b′ (mod dn−1 ), sebab c = a′n φ(dn−1 )−1 b′ . Akibatnya, dengan membagi kedua ruas persamaan terakhir dengan dn−1 diperoleh a”1 x1 + a”2 x2 + · · · + a”n−1 xn−1 = b” 58
(6.4)
dengan a”i = a′i /dn−1 untuk i = 1, 2, . . . , n dan b” = (b′ − a′n c)/dn−1 + a′n tn−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−1 tn−1 maka diperoleh persamaan (6.2) memiliki solusi bulat dan solusinya dapat ditulis ke dalam n − 1 parameter. Contoh 6.2.3. Tentukan bilangan bulat x dan y yang memenuhi persamaan a. 96x + 54y = 20. b. 96x + 54y = 12. Penyelesaian. Berdasarkan Algoritma Euclid diperoleh 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 Algoritma 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, 59
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. Diberikan a, b dan c bilangan 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 x = x0 +
b a t, y = y0 − t gcd(a, b) gcd(a, b)
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. Diperoleh 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, x = x0 +
b a t, y = y0 − t. gcd(a, b) gcd(a, b)
60
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 positif n. Diasumsikan terdapat 666 triple 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, . . . , 61
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 ∑
(a − i − 1) =
i=0
a−1 ∑ i=0
i=
a(a − 1) 2
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 positif a dan b. 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 (a − 1)(b − 1) r dan s sama dengan . 2 Bukti. Misalkan bilangan bulat positif n dikatakan ”baik” jika terdapat bilangan bulat non-negatif r dan s dengan sifat ar+bs = n. Diperhatikan susunan berikut: 0 1 2 a a+1 a+2 2a 2a + 1 2a + 2 ... ... ...
... k ... a + k . . . 2a + k ... ...
... a − 1 . . . 2a − 1 . . . 3a − 1 ... ...
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 62
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 v=0 j=0
a
=
(a − 1)(b − 1) . 2
Diperhatikan bahwa bilangan bulat positif terbesar yang tidak baik berada 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 positif a dan b yang 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. Diketahui n bilangan bulat positif dengan gcd(n, 1991) = 1. Tunn jukkan abhwa dapat ditulis sebagai jumlahan dua bilangan rasional positif 1991 dengan penyebut kurang dari 1991 jika dan hanya jika terdapat bilangan bulat positif m, a, b dengan m ≤ 10 dan mn = 11a + 181b. 63
Penyelesaian. (⇐) Diketahui m, a, b bilangan bulat positif dengan m ≤ 10 dan mn = 11a + 181b. Diperoleh a b n = + , 1991 181m 11m dengan 181m, 11m < 1991. n a b (⇒)Diketahui = + untuk suatu bilangan bulat positif a, b dengan gcd(a, r) = 1991 r r gcd(b, s) = 1 dan r, s < 1991. Tanpa mengurangi keumuman misalkan r = 181r1 dan s = 11s1 (1991 = 11.181). Diperoleh nr1 s1 = 11as1 + 181br1 . Akibatnya r1 |11as1 dan s1 |181br1 . Karena r1 < 11 dan gcd(r1 , a) = 1, maka r1 |s1 . Karena s1 < 181 dan gcd(s1 , b) = 1, maka s1 |r1 . Diperoleh s1 = r1 . Dipilih m = r1 . Jelas m merupakan bilangan bulat positif yang kurang dari 11 dan mn = 11a+181b.
Soal Latihan 1. Tentukan semua solusi bulat persamaan-persamaan linear Diophantine berikut. (a) 20x + 13y = 2013. (b) 3456x + 246y = 44. (c) 3u + 4v + 5w + 6x = 18. 2. Tentukan semua solusi bulat persamaan (6u + 9v)(7x + 8y) = 3. 3. Tentukan semua bilangan bulat x dan y dengan sifat 3x + 4y|2013. 4. Tunjukkan bahwa luas segitiga dengan titik-titik sudut (0, 0), (b, a), (x, y) adalah
|ax − by| . 2
5. Tentukan banyaknya bilangan bulat positif yang dapat dinyatakan dalam bentuk 4x + 10y + 19z dengan x, y, z bilangan bulat non-negatif dan x + y + z = 94. 64
6. Tentukan bilangan bulat positif a dan b dengan sifat banyaknya bilangan bulat positif n yang tidak dapat dinyatakan dalam bentuk ax + by untuk suatu bilangan bulat non-negatif x, y adalah 35 dan salah satu bilangan tersebut adalah 58. 170 merupakan bilangan rasional terbesar dengan penye1991 but sama dengan 1991 yang tidak dapat dinyatakan sebagai jumlahan dua
7. Tunjukkan bahwa
bilangan rasional dengan penyebut kurang dari 1991. 8. Tentukan bilangan bulat positif terbesar yang tidak dapat dinyatakan dalam bentuk 42x + y untuk suatu bilangan bulat positif x dan y dengan y komposit. 9. Diberikan bilangan real positif a, b dan c. Tunjukkan bahwa terdapat paling sedikit c2 /ab pasangan bilangan bulat non-negatif (x, y) yang memenuhi ax + by ≤ c.
65
BAB VII SISTEM NUMERIK DAN FUNGSI TANGGA
7.1
Pendahuluan Representasi bilangan sangat penting dalam komunikasi matematis, baik di
bidang matematika maupun bidang ilmu lain. Beberapa representasi yang bisa dijumpai di antaranya biner untuk aljabar Boole, 12-an, dan desimal. Selain itu, di dunia sains juga dikenal dengan pendekatan atas dan pendekatan bawah untuk suatu angka real yang kontinum. Sistem pendekatan ini memiliki sifat-sifat yang unik, yang dapat dipandang sebagai fungsi berundak. Sifat-sifat fungsi berundak (tangga) merupakan akibat sifat-sifat elementer bilangan bulat. Untuk itu pada bagian ini dibahas mengenai konsep representasi basis dari bilangan bulat, beberapa kriteria keterbagian pada representasi desimal, serta fungsi tangga berupa fungsi floor dan ceilling. Dengan mempelajari topik bahasan pada Minggu ke-12 dan 13 ini, diharapkan mahasiswa memiliki kemampuan: 1. Mahasiswa mampu menjelaskan fungsi numerik 2. Mahasiswa mampu menjelaskan pengertian fungsi tangga 3. Mahasiswa mampu menerapkan fungsi numerik dan tangga dalam permasalahan teori bilangan dan di bidang lain
7.2
Sistem Numerik
Teorema 7.2.1. Diberikan bilangan bulat b > 1. Untuk setiap bilangan bulat n ≥ 1 , terdapat dengan tunggal sistem bilangan bulat (k, a0 , a1 , . . . , ak ) dengan sifat 0 ≤ ai ≤ b − 1, i = 0, 1, . . . , k, ak ̸= 0, dan n = ak bk + ak−1 bk−1 + · · · + a1 b + a0 .
(7.5)
Bukti. Pertama-tama, dibuktikan existensi dari sistem tersebut. Berdasarkan
66
Algoritma Pembagian diperoleh n q1 qk−1
= q1 b + r1 , 0 ≤ r1 ≤ b − 1 = q2 b + r1 , 0 ≤ r2 ≤ b − 1 ... = qk b + r1 , 0 ≤ rk ≤ b − 1
dengan qk hasil bagi terakhir yang tidak sama dengan nol. Dipilih q0 = n, a0 = n − q1 b, a1 = q1 − q2 b, . . . , ak−1 = qk−1 − qk b, ak = qk . Diperoleh k ∑ i=0
i
ai b =
k−1 ∑
(qi − qi+1 b)b + qk b = q0 + i
k
i=0
k ∑ i=1
ai b − i
k ∑
ai bi = q0 = n.
i=1
Selanjutnya, akan dibuktikan ketunggalannya. Diasumsikan n = c0 + c1 b + · · · + ch bh representasi lain dari n. Akan ditinjau 2 kasus, yaitu h ̸= k dan h = k. Kasus h ̸= f . Tanpa mengurangi keumuman misalkan h > k, diperoleh n ≥ bh ≥ bk+1 . Akan tetapi, n = a0 + a1 b + · · · + ak bk ≤ (b − 1)(1 + b + · · · + bk = bk+1 − 1 < bk+1 , suatu kontradiksi. Kasus h = k. Diperhatikan bahwa a0 + a1 b + · · · + ak bk = c0 + c1 b + · · · + ck bk , sehingga diperoleh b|(a0 −c0 ). Di lain pihak, |a0 −c0 | < b, maka diperoleh a0 = c0 . Akibatnya, didapat a1 + a2 b + · · · + ak bk = c1 + c2 b + · · · + ck bk . Dengan mengulangi prosedur di atas, diperoleh a1 = c1 , a2 = b2 , . . . , ak = ck .
Definisi 7.2.2. Diberikan bilangan bulat positif n dan b > 1. Penyajian n ke dalam bentuk seperti pada (7.5) disebut representasi dari n dalam basis b, dinotasikan dengan n = ak ak−1 . . . a0 (b) . 67
Khusus untuk b = 10, penyajian tersebut dinamakan representasi desimal dan cukup dituliskan dalam bentuk n = ak ak−1 . . . a1 a0 .
(Contoh:
2010 = 2010(10) ). Contoh 7.2.3. Diberikan xy dan yx bilangan bulat positif dua digit. Buktikan bahwa jumlahan keduanya merupakan bilangan komposit. Penyelesaian. Karena xy = 10x + y dan yx = 10y + x, maka jumlahan keduanya sama dengan 11x+11y = 11(x+y), yang merupakan bilangan komposit.
Contoh 7.2.4. Tentukan bilangan bulat yang terdiri dari 6 digit dengan angka terakhir 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 + 104 a + 103 b + 102 c + 10d + e
= 5(105 a + 104 b + 103 c + 102 d + 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 dua digit 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.
68
Contoh 7.2.6. Tuliskan 1111011(2) ke dalam basis 10 dan tuliskan 2010 ke dalam basis 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. Diperoleh representasi desimal dari 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 pertama adalah hasil bagi terakhir yang tak nol. Susunan perhitungannya diberikan sebagai berikut. 2010 2009 1
7 287 287 0
7 41 7 35 5 6
Jadi, 2010 = 5601(7) .
Contoh 7.2.7. Beberapa himpunan yang terdiri dari bilangan-bilangan prima seperti {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 anggotaanggota 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 bilangan bulat positif n sehingga 11111(n) adalah kuadrat sempurna.
69
Penyelesaian. Diperhatikan bahwa 11111(n) = n4 + n3 + n2 + n + 1. Jika n genap, maka n2 +
n 2
dan n2 +
n 2
+ 1 adalah 2 bilangan bulat berurutan.
Diperoleh (
Jadi, 11111(n)
n )2 n2 = n4 + n3 + 2 2 4 3 < n + n + n2 + n + 1 ( )2 n < n2 + + 1 . 2 bukan kuadrat sempurna untuk bilangan genap n. n2 +
Jika n ganjil, maka n2 +
n 2
−
1 2
dan n2 +
n 2
+
1 2
adalah bilangan bulat berurutan.
Diperhatikan bahwa ( )2 n 1 2 n + − < n4 + n3 + n2 + n + 1. 2 2 dan
( )2 n 1 5n2 n 1 2 n + + = n4 + n3 + + + 2 2 4 2 2
n2 − 2n − 3 4 (n − 3)(n + 1) = n4 + n3 + n2 + n + 1 + . 4 Untuk n bilangan ganjil lebih dari 3, 11111(n) berada diantara 2 bilangan bulat = n4 + n3 + n2 + n + 1 +
kuadrat berurutan, yaitu ( )2 n 1 2 n + − 2 2
( )2 n 1 2 dan n + + . 2 2
Jadi, 11111(n) bukan kuadrat sempurna untuk setiap bilangan positif lebih dari 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 konstan. Berikut salah satu contohnya. 70
Teorema 7.2.9. Setiap bilangan bulat positif k mempunyai ekspansi basis faktorial 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 < m1 !. Karena k < (m1 + 1)! = m1 ! · (m1 + 1), maka fm1 ≤ m. Dengan mengulangi proses ini, diperoleh r1 = m2 !fm2 + r2 , untuk suatu m2 bilangan bulat positif yang tunggal dengan m2 ! ≤ r1 < (m2 + 1)!, 1 ≤ fm2 ≤ m2 , dan 0 ≤ r2 < m2 !. Dengan melanjutkan proses ini berulangulang, akan diperoleh suatu ekspansi basis faktorial yang tunggal dari k.
Teorema 7.2.10. Diberikan F0 = 1, F1 = 1, dan Fn+1 = Fn + Fn−1 untuk setiap bilangan bulat positif n. (Barisan ini dinamakan barisan Fibonacci, dan sukusukunya dinamakan bilangan Fibonacci. Setiap bilangan bulat non-negatif n dapat dituliskan dengan tunggal sebagai suatu jumlahan dari bilangan-bilangan Fibonacci yang tidak berurutan, yaitu n=
∞ ∑
αk Fk ,
k=0
dengan αk ∈ {0, 1} dan (αk , αk + 1) ̸= (1, 1) untuk setiap k. Ekspresi untuk n ini disebut dengan representasi Zeckendorf dari n. Bukti dari teorema ini hampir sama dengan teorema sebelumnya. 71
Contoh 7.2.11. Diberikan (f1 , f2 , f3 , . . . , fj ) adalah ekspansi basis faktorial dari 16! − 32! + 48! − 64! + · · · + 1968! − 1984! + 2000!. Tentukan nilai dari f1 − f2 + f3 − f4 + · · · + (−1)j−1 fj . Penyelesaian. Karena (n + 1)! − n! = n!(n + 1) − n! = n!n, maka diperoleh (n + 16)! − n! = (n + 16)! − (n + 15)! + (n + 15)! − (n + 14)! + · · · + (n + 1)! − (n)! = (n + 15)!(n + 15) + (n + 14)!(n + 14) + · · · + (n + 1)!(n + 1) + n!n. Akibatnya, diperoleh ekspansi basis faktorial dari (n + 16)! − n! adalah (0, 0, . . . , 0, n, n + 1, . . . , n + 14, n + 15), dengan banyak bilangan nol pada bagian awal adalah n − 1.
Diperhatikan
bahwa ekspansi basis faktorial dari 16! adalah (0, 0, . . . , 0, 1), sehingga diperoleh ekspansi yang dicari adalah (0, 0, . . . , 0; 1; 0, . . . , 0; 32, 33, . . . , 47; 0, . . . , 0; 64, . . . , 79; . . . ; 1984, . . . , 1999). Diperhatikan bahwa dimulai pada posisi 32,ekspansi tersebut terdiri dari kelompok atas 16 bilangan tak nol yang saling bergantian dengan kelompok atas 16 bilangan nol. Dengan pengecualian untuk f16 = 1, nilai dari setiap fi yang tak kosong adalah i. Masing-masing dari 62 kelompok atas 16 bilangan tak nol memberikan hasil 8 untuk jumlahan yang dicari, dan f16 memberikan hasil -1. Jadi, nilai dari jumlahan yang dicari adalah 8 · 62 − 1 = 495.
7.3
Kriteria Keterbagian pada Sistem Desimal Diberikan beberapa kriteria keterbagian untuk bilangan bulat pada repre-
sentasi desimal. Teorema 7.3.1. Diberikan n = ah ah−1 . . . a0 bilangan bulat positif. 72
a. Jika S(n) = a0 + a1 + . . . + ah merupakan jumlah digit-digit dari n, maka n ≡ s(n) (mod 3). Secara khusus, n habis dibagi oleh 3 jika dan hanya jika S(n) habis dibagi 3. b. Jika S(n) = a0 + a1 + . . . + ah merupakan jumlah digit-digit dari n, maka n ≡ S(n) (mod 9). Secara khusus, n habis dibagi oleh 9 jika dan hanya jika S(n) habis dibagi 9. c. Jika s′ (n) = a0 − a1 + . . . + (−1)h ah , maka n habis dibagi oleh 11 jika dan hanya jika s(n) habis dibagi 11. d. n habis dibagi oleh 7,11 atau 13 jika dan hanya jika ah ah−1 . . . a3 −a2 a1 a0 habis dibagi oleh bilangan yang sama. e. n habis dibagi oleh 27 atau 37 jika dan hanya jika ah ah−1 . . . a3 + a2 a1 a0 habis dibagi oleh bilangan yang sama. f. n berturut-turut habis dibagi oleh 2k atau 5k dengan k ≤ h jika dan hanya jika ah ah−1 . . . a0 habis dibagi oleh bilangan yang sama. Contoh 7.3.2. Diberikan a679b bilangan lima digit yang habis dibagi 72. Tentukan nilai a dan b. Penyelesaian. Diperhatikan bahwa 72 = 8.9. Karena 8 dan 9 relatif prima, maka a679b habis dibagi oleh 8 dan 9. Karena a679b habis dibagi 8, maka 79b habis dibagi 8. Diperoleh nilai b yang memenuhi hanya b = 2. Karena a6792 habis dibagi 9, maka a + 6 + 7 + 9 + 2 habis dibagi 9. Diperoleh bilangan a yang
memenuhi hanya a = 3.
Contoh 7.3.3. Kuadrat sempurna atau tidak? a. Tentukan semua bilangan bulat positif k dengan sifat bilangan k-digit 11 . . . 1 kuadrat sempurna. b. Apakah terdapat bilangan kuadrat sempurna 5 digit yang terdiri dari digit-digit genap berbeda. c. Tentukan semua bilangan bulat positif n dengan sifat bilangan n digit 200 . . . 013 merupakan bilangan kuadrat sempurna. 73
Penyelesaian. a. Jelas k = 1 memenuhi. Diperhatikan bahwa untuk k ≥ 1 berlaku . . . 1} ≡ 11 ≡ 3 |11 {z
(mod 4),
k kali
yang berarti 11 . . . 1 bukan kuadrat sempurna. b. Tidak. Diperhatikan bahwa 0 + 2 + 4 + 6 + 8 = 20 ≡ 2 (mod 9), sedangkan setiap bilangan kuadrat sempurna kongruen 0, 1, 4, 7 modulo 9. Akibatnya setiap bilangan kuadrat sempurna 5 digit yang terdiri dari digit-digit genap berbeda bukan kuadrat sempurna. c. Diperhatikan bahwa untuk setiap bilangan bulat positif n, jumlah digit-digit bilangan tersebut sama dengan 6, kelipatan 3 tapi bukan kelipatan 9. Jadi, tidak ada bilangan bulat positif n dengan sifat bilangan n digit 200 . . . 013 merupakan bilangan kuadrat sempurna.
Contoh 7.3.4. Tentukan banyaknya bilangan 5 digit abcde dengan sifat abc + de habis dibagi 11. Penyelesaian. Diperhatikan bahwa abcde = abc × 100 + de = (abc + de) + 99 × abc. Diperoleh abc + de habis dibagi 11 jika dan hanya jika abcde habis dibagi 11. Diperhatikan bahwa bilangan 5 digit terbesar yang habis dibagi oleh 11 adalah 99990 (9090 × 11) dan bilangan 4 digit terbesar yang habis dibagi oleh 11 adalah 9999 (909 × 11). Diperoleh ada tepat 9090 − 909 = 8181 bilangan 5 digit yang merupakan kelipatan 11. Jadi, banyaknya ada 8181 bilangan.
Teorema 7.3.5. Diberikan n1 , n2 bilangan bulat positif. Jika S(n) menyatakan jumlah digit-digit dari n, maka a. 9|S(n1 ) − n1 ; 74
b. S(n1 + n2 ) ≤ S(n1 ) + S(n2 ); c. S(n1 n2 ) ≤ min(n1 S(n2 ), n2 S(n1 )); d. S(n1 n2 ) ≤ S(n1 )S(n2 ). Bukti. Misalkan n1 = ak ak−1 . . . a0 , n2 = bh bh−1 . . . b0 dan n1 + n2 = cs cs−1 . . . c0 . a. Cukup jelas dari Teorema 7.3.1. b. Dipilih t terkecil dengan sifat ai + bi < 10 untuk setiap i < t. Diperoleh at + bt ≥ 10, sehingga ct = at + bt − 10 dan ct+1 = at+1 + bt+1 + 1. Akibatnya berlaku
t+1 ∑ i=1
ci ≤
t+1 ∑
ai +
t+1 ∑
i=1
bi .
i=1
Dengan melanjutkan proses ini diperoleh S(n1 + n2 ) ≤ S(n1 ) + S(n2 ). c. Tanpa mengurangi keumuman misalkan min(n1 S(n2 ), n2 S(n1 )) = n1 S(n2 ). Dengan menggunakan bagian b., diperoleh S(n1 n2 ) = S (n2 + n2 + . . . + n2 ) {z } | n1 kali
≤ S(n2 ) + S(n2 ) + . . . + S(n2 ) = n1 S(n2 ). | {z } n1 kali
d. Diperhatikan bahwa dari bagian b. dan c. berlaku ( ) ( h ) h ∑ ∑ S(n1 n2 ) = S n1 bi 10i = S n1 bi 10i i=0
≤ ≤
h ∑ i=0 h ∑
( ) S n1 bi 10i =
i=0 h ∑
S (n1 bi )
i=0
bi S (n1 ) = S (n1 )
i=0
h ∑
bi
i=0
= S (n1 ) S (n2 ) .
75
Contoh 7.3.6. Tentukan bilangan bulat positif n dengan sifat S(n) = 2013S(3n). Penyelesaian. Diambil n = 1 33 . . . 3} 5, | {z 6037 kali
diperoleh n = 4 00 . . . 0} 5. | {z 6037 kali
Diperhatikan bahwa S(n) = 3.6037 + 1 + 5 = 18117 = 2013.9 = 2013S(3n).
Contoh 7.3.7. Misalkan jumlahan digit-digit dari representasi desimal 44444444 adalah A. Jika B adalah jumlahan digit-digit dari A, maka tentukan jumlahan digit-digit dari B. Penyelesaian. Misalkan a = 44444444 . Diperhatikan bahwa 4444 < 104 , maka diperoleh a = 44444444 < 104.4444 = 1017776 , sehingga banyaknya digit dari a tidak lebih dari 17776 digit. Karena setiap digit kurang dari atau sama dengan 9, maka diperoleh A = S(a) ≤ 17776.9 = 159984. Diantara bilangan bulat positif yang kurang dari atau sama dengan 159984, bilangan dengan jumlah digit terbesar adalah 99999, sehingga diperoleh B = S(A) ≤ 45. Diantara bilangan bulat positif yang kurang dari atau sama dengan 45, bilangan dengan jumlah digit terbesar adalah 39, sehingga diperoleh S(B) ≤ 12. Diperhatikan bahwa S(B) ≡ B ≡ S(A) ≡ A ≡ S(a) ≡ a ≡ 44444444
(mod 9)
dan 44444444 ≡ (4 + 4 + 4 + 4)4444 ≡ 164444 ≡ (−2)4444 ≡ (−2)3.1481+1 ≡ (−8)1481 .(−2) ≡ 1.(−2) ≡ 7
(mod 9).
Diperoleh bahwa nilai S(B) adalah 7.
Soal Latihan 76
1. Tentukan jumlah semua bilangan 2 digit yang habis dibagi oleh setiap digitnya. 2. Tentukan bilangan bulat positif terkecil n dengan sifat representasi desimal dari 15n hanya memuat digit 0 dan 8. 3. Tentukan bilangan 6 digit abcdef yang memenuhi 7 × abcdef = 6 × def abc. 4. Tentukan bilangan bulat positif terkecil yang merupakan kelipatan 84 dan hanya terdiri dari digit 6 atau 7. 5. Sebuah speedometer yang rusak pada sebuah mobil memproses dari digit 3 ke digit 5, selalu melewati digit 4, tanpa menghiraukan letak kesalahan. Contohnya, setelah melakukan perjalanan 1 km, speedometer berubah dari 000039 ke 000050. Jika pada odometer tersebut sekarang terbaca 002005, sudah berapa km jarak yang ditempuh mobil tersebut dari awal? 6. Diketahui n bilangan 7 digit yang habis dibagi oleh setiap digitnya. Tentukan tiga digit yang bukan digit dari n. . . . 1}. Tentukan jumlah digit-digit dari 7. Diketahui M = 11 . . . 1} dan N = |11 {z | {z 62 kali
61 kali
3M N . 8. Diberikan bilangan 7 digit M = abcdef g. Misalkan N = gf edcba. Tunjukkan representasi desimal dari M + N memuat setidaknya satu digit genap. 9. Untuk setiap bilangan bulat positif n, didefinisikan p(n) sebagai hasil kali digit-digit tak nol dari n. Misalkan S = p(1) + p(2) + . . . + p(999). Tentukan faktor prima terbesar dari S. 10. Tunjukkan bahwa setiap bilangan bulat positif memiliki kelipatan yang memuat digit-digit 0, 1, 2, . . . , 9. 11. Tentukan bilangan bulat positif terkecil x dengan sifat tiga digit terakhir dari x3 adalah 888. 77
12. Tunjukkan bahwa bilangan 11 . . . 19 dalam basis 9 merupakan jumlahan dari k bilangan bulat positif pertama untuk suatu bilangan bulat positif k. 13. Diberikan bilangan bulat positif n dengan sifat setiap digitnya (kecuali digit pertama) lebih besar dari digit di sebelah kirinya. Tentukan jumlah digitdigit dari 9n. 14. Tunjukkan bahwa untuk setiap bilangan bulat positif n, terdapat bilangan n digit yang habis dibagi 5n dan semua digitnya bilangan ganjil.
7.4
Fungsi Tangga Diperhatikan bahwa untuk setiap bilangan real x terdapat dengan tunggal
bilangan bulat n dengan sifat n ≤ x < n + 1. Definisi 7.4.1. Diberikan bilangan real x. Bilangan bulat yang lebih besar dari atau sama dengan x disebut floor dari x, ditulis n = ⌊x⌋. Selisih x − ⌊x⌋ disebut bagian pecahan dari x, dinotasikan dengan {x}. Bilangan bulat yang lebih besar dari atau sama dengan x disebut ceiling dari x, dinotasikan dengan n = ⌈x⌉. Diperhatikan bahwa jika x bilangan bulat, maka ⌊x⌋ = ⌈x⌉ dan {x} = 0, sedangkan jika x bukan bilangan bulat, maka ⌈x⌉ = ⌊x⌋ + 1. Contoh 7.4.2. Selesaikan sistem persamaan berikut: x + ⌊y⌋ + {z} = 200.0, {x} + y + ⌊z⌋ = 190.1, ⌊x⌋ + {y} + z = 178.8. Penyelesaian. Karena untuk setiap bilangan real x berlaku x = ⌊x⌋+{x}, maka dengan menjumlahkan ketiga persamaan tersebut diperoleh 2x + 2y + 2z = 568.9,
or x + y + z = 284.45.
Dengan mengurangkan masing-masing persamaan yang diberikan dengan persamaan terakhir diperoleh {y} + ⌊z⌋ = 84.45, ⌊x⌋ + {z} = 94.35, {x} + ⌊y⌋ = 105.65. 78
Didapat {y} = 0.45, ⌊z⌋ = 84, ⌊x⌋ = 94, {z} = 0.35, {x} = 0.65, ⌊y⌋ = 105. Jadi,
x = 94.65, y = 105.45 dan z = 84.35.
Contoh 7.4.3. Diberikan bilangan real positif a dengan {a−1 } = {a2 } dan 2 < a2 < 3. Tentukan nilai dari a6 − 8a−1 . Penyelesaian. Diperhatikan bahwa a > 1, maka a−1 < 1, sehingga diperoleh {a−1 } = a−1 . Karena 2 < a2 < 3, maka {a2 } = a2 − 2. Akibatnya diperoleh a−1 = {a−1 } = {a2 } = a2 − 2 atau a3 − 2a − 1 = 0. Diperoleh (a + 1)(a2 − a − 1) = a3 − 2a − 1 = 0. √ 1+ 5 Nilai a positif yang memenuhi hanya a = . Diperhatikan bahwa 2 a6 = (a3 )2 = (2a + 1)2 = 4a2 + 4a + 1 = 4(a + 1) + 4a + 1 = 8a + 5. Diperoleh a7 = 8a2 + 5a = 13a + 8, sehingga berlaku a6 − 8a−1 =
a7 − 8 = 13. a
Contoh 7.4.4. Tentukan semua solusi real dari persamaan 4x2 − 40 ⌊x⌋ + 51 = 0. Penyelesaian. Diperhatikan bahwa karena untuk setiap bilangan real x berlaku ⌊x⌋ ≤ x, maka diperoleh (2x − 3)(2x − 17) = 4x2 − 40x + 51 ≤ 4x2 − 40 ⌊x⌋ + 51 = 0, sehingga didapat
3 2
≤x≤
17 . 2
Akibatnya diperoleh 1 ≤ ⌊x⌋ ≤ 8. Di lain pihak √ 40 ⌊x⌋ − 51 x= , 2
sehingga berlaku
⌊√ ⌊x⌋ =
⌋ 40 ⌊x⌋ − 51 . 2 79
Dengan mensubstitusi ⌊x⌋ ∈ {1, 2, 3, . . . , 8} ke persamaan tesebut, diperoleh bahwa nilai ⌊x⌋ yang memenuhi hanya 2, 6, 7 atau 8. Diperoleh nilai x yang √
memenuhi adalah
29 , 2
√
189 , 2
√
229 2
√
dan
269 . 2
Contoh 7.4.5. Tentukan bilangan bulat terbesar yang kurang dari atau sama √ √ dengan ( 6 + 5)4 . Penyelesaian. Dengan menggunakan Binomial Newton diperoleh √ √ √ √ √ √ √ √ √ √ ( 6 + 5)4 = ( 6)4 + 4( 6)3 5 + 6( 6)2 ( 5)2 + 4 6( 5)3 + ( 5)4 √ √ √ = 36 + 24 30 + 180 + 20 30 + 25 = 241 + 49 30 dan √ √ √ √ √ √ √ √ √ √ ( 6 − 5)4 = ( 6)4 − 4( 6)3 5 + 6( 6)2 ( 5)2 − 4 6( 5)3 + ( 5)4 √ √ √ = 36 − 24 30 + 180 − 20 30 + 25 = 241 − 49 30. Diperoleh
√ √ √ √ ( 6 + 5)4 + ( 6 − 5)4 = 482. √ √ √ √ Diperhatikan bahwa 6 − 5 < 1, maka ( 6 − 5)4 < 1. Akibatnya diperoleh ⌊√ √ 4⌋ ( 6 + 5) = 481. Beberapa karakteristik dari fungsi floor atau fungsi tangga diberikan sebagai berikut. Teorema 7.4.6. Diberikan bilangan real x, y. a. Jika a dan b bilangan bulat dengan b > 0 dan q, r berturut-turut hasil ⌊ ⌋ { } bagi dan sisa ketika a dibagi oleh b, maka q = ab dan r = ab .b. b. Untuk setiap bilangan bulat n berlaku ⌊x + n⌋ = ⌊x⌋ + n dan ⌈x + n⌉ = ⌈x⌉ + n. c. Jika x bilangan bulat, maka ⌊x⌋ + ⌊−x⌋ = 0; jika x bukan bilangan bulat, maka ⌊x⌋ + ⌊−x⌋ = 1. 80
d. Jika x ≤ y, maka ⌊x⌋ ≤ ⌊y⌋. e. ⌊x⌋ + ⌊y⌋ ≤ ⌊x + y⌋ ≤ ⌊x⌋ + ⌊y⌋ + 1. f. Jika x, y ≥ 0, maka ⌊x⌋ · ⌊y⌋ ≤ ⌊xy⌋. g. Jika x ≥ 0, maka untuk setiap bilangan bulat positif n banyaknya keli⌊ ⌋ patan positif dari n yang kurang dari atau sama dengan x adalah nx . h. Untuk setiap bilangan bulat positif n berlaku ⌊ ⌋ ⌊ ⌋ ⌊x⌋ x = . n n Contoh 7.4.7. Tunjukkan bahwa untuk setiap bilangan real x dan y berlaku ⌊2x⌋ + ⌊2y⌋ ≥ ⌊x⌋ + ⌊y⌋ + ⌊x + y⌋ . Penyelesaian. Diberikan bilangan real x dan y. Karena x = ⌊x⌋ + {x} dan y = ⌊y⌋ + {y}, maka diperoleh ⌊2x⌋ + ⌊2y⌋ = 2 ⌊x⌋ + ⌊2{x}⌋ + 2 ⌊y⌋ + ⌊2{y}⌋ dan ⌊x + y⌋ = ⌊x⌋ + ⌊y⌋ + ⌊{x} + {y}⌋ . Akibatnya, cukup dibuktikan ⌊2{x}⌋ + ⌊2{y}⌋ ≥ ⌊{x} + {y}⌋ . Tanpa mengurangi keumuman, misalkan {x} ≥ {y}. Diperoleh 2{x} ≥ {x}+{y}, sehingga diperoleh ⌊2{x}⌋ + ⌊2{y}⌋ ≥ ⌊2{x}⌋ ⌊{x} + {y}⌋ . Jadi, ⌊2x⌋ + ⌊2y⌋ ≥ ⌊x⌋ + ⌊y⌋ + ⌊x + y⌋ .
81
Contoh 7.4.8. Tunjukkan bahwa untuk setiap bilangan bulat positif n berlaku ⌊√ ⌋ ⌊√ ⌋ √ n+ n+1 = 4n + 2 . Penyelesaian. Diambil sebarang bilangan bulat positif n. Diperhatikan bahwa √ √ √ ( n + n + 1)2 = 2n + 1 + 2 n2 + n dan n< Diperoleh
√ n2 + n < n + 1.
√ √ √ √ 4k + 1 < n + n + 1 < 4n + 3.
Karena setiap bilangan kuadrat bersisa 0 atau 1 ketika dibagi oleh 4, maka 4n + 2 dan 4n + 3 bukan bilangan kuadrat, sehinga diperoleh ⌊√ ⌋ ⌊√ ⌋ ⌊√ ⌋ 4k + 1 = 4k + 2 = 4k + 3 . Jadi,
⌊√ ⌋ ⌊√ ⌋ √ n+ n+1 = 4n + 2 .
Contoh 7.4.9. Diberikan p dan q bilangan bulat yang relatif prima. Tunjukkan bahwa
⌊ ⌋ ⌊ ⌋ ⌊ ⌋ p 2p (q − 1)p (p − 1)(q − 1) + + ... + = . q q q 2
Penyelesaian. Karena gcd(p, q) = 1, maka
ip bukan bilangan bulat untuk setiap q
i = 1, 2, . . . , q − 1. Diperoleh ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ip (q − i)p ip −ip + =p+ + =p−1 q q q q untuk setiap i = 1, 2, . . . , q − 1. Akibatnya, 2
⌋ q−1 ⌊ ∑ ip i=1
q
=
⌋ q−1 (⌊ ∑ ip q
i=1 q−1
=
∑
⌊
(q − i)p + q
⌋)
(p − 1) = (p − 1)(q − 1).
i=1
82
Jadi,
⌊ ⌋ ⌊ ⌋ ⌊ ⌋ p 2p (q − 1)p (p − 1)(q − 1) + + ... + = . q q q 2 Selanjutnya, diberikan salah satu sifat terkenal terkait fungsi tangga
yaitu Identitas Hermit. Teorema 7.4.10 (Identitas Hermit). Untuk setiap bilangan real x dan bilangan bulat positif n berlaku ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ 1 2 n−1 ⌊x⌋ + x + + x+ + ... + x + = ⌊nx⌋ . n n n Bukti. Diambil sebarang bilangan real x dan bilangan bulat positif n. Kasus x bilangan bulat cukup jelas. Diasumsikan x tidak bulat, berarti 0 < {x} < 1, sehingga terdapat 1 ≤ i ≤ n − 1 dengan sifat {x} + ekuivalen dengan
i−1 i < n dan {x} + ≥ 1, n n n−i n−i+1 ≤ {x} < . n n
Akibatnya diperoleh ⌊
⌋ ⌊ ⌋ 1 i−1 ⌊x⌋ = x + = ... = x + n n dan
⌊ ⌋ ⌊ ⌋ ⌊ ⌋ i i+1 n−1 x+ = x+ = ... = x + , n n n
sehingga berlaku ⌊ ⌋ ⌊ ⌋ 1 n−1 ⌊x⌋ + x + + ... + x + = i ⌊x⌋ + (n − i)(⌊x⌋ + 1) n n = n ⌊x⌋ + n − i. Di sisi lain, n ⌊x⌋ + n − i ≤ n ⌊x⌋ + n{x} = nx < n ⌊x⌋ + n − i + 1,
83
yang berarti ⌊nx⌋ = n ⌊x⌋ + n − i. Jadi, ⌋ ⌊ ⌋ ⌊ 1 n−1 + ... + x + = n ⌊x⌋ + n − i ⌊x⌋ + x + n n = ⌊nx⌋ .
Contoh 7.4.11. Diberika bilangan real x. Tunjukkan bahwa ⌋ ∞ ⌊ ∑ x + 2k = ⌊x⌋ . k+1 2 k=1 Penyelesaian. Dengan mengambil n = 2 pada Identitas Hertmit diperoleh ⌊ ⌋ 1 ⌊x⌋ + x + = ⌊2x⌋ , 2 atau
⌋ ⌊ 1 = ⌊2x⌋ − ⌊x⌋ . x+ 2
Akibatnya diperoleh ⌋ ∑ ⌋ ∑ ∞ ⌊ ∞ ⌊ ∞ (⌊ ∑ x + 2k x x ⌋ ⌊ x ⌋) 1 = + = − k+1 = ⌊x⌋ . k+1 k+1 k 2 2 2 2 2 k=1 k=1 k=1
7.5
Pangkat Tertinggi Fungsi floor memiliki cukup banyak aplikasi, salah satunya dalam menen-
tukan pangkat tertinggi suatu bilangan pada faktorisasi prima bilangan berbentuk n!. Teorema 7.5.1. Diberikan bilangan bulat positif n dan p dengan p prima. Bilangan bulat non-negatif k yang memenuhi pk ∥n! adalah ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ n n n + 2 + 3 + .... p p p 84
Bukti. Akan dibuktikan dengan induksi matematika. Basis Induksi. Untuk n = 1 diperoleh p0 ∥1!. Di sisi lain, untuk setiap bilangan bulat positif s berlaku
⌊
1 ps
⌋ = 0,
sehingga diperoleh
⌊ ⌋ ⌊ ⌋ ⌊ ⌋ 1 1 1 0= + 2 + 3 + .... p p p Terbukti untuk kasus n = 1. Langkah Induksi. Diasumsikan pernyataan benar untuk setiap n < m. Akan ditunjukkan pernyataan benar untuk n = m. Misalkan k memenuhi pk ∥m!. Diperhatikan bahwa banyaknya bilangan kelipatan p di antara 1, 2, . . . , m adalah ⌊ ⌋ m . Diperoleh k memenuhi p ⌊
pk ∥p(2p)(3p) . . . (k1 p) = pk1 (k1 )!,
⌋ m dengan k1 = , sehingga cukup dicari k dengan sifat p pk−k1 ∥(k1 )!
Berdasarkan asumsi induksi diperoleh ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ k1 k1 k1 k − k1 = + 2 + 3 + .... p p p Karena untuk setiap bilangan bulat positif s berlaku ⌊ ⌋ m ⌊ ⌋ ⌊ ⌋ p k1 m = s = s , s p p p maka diperoleh
Jadi,
⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ m m m m k− = 2 + 3 + 4 + .... p p p p ⌊
⌊
⌋ ⌊ ⌋ ⌊ ⌋ m m m k= + 2 + 3 + .... p p p Terbukti pernyataan benar untuk kasus n = m.
85
Contoh 7.5.2. Tentukan banyaknya digit nol berurutan yang terletak pada bagian akhir dari representasi desimal 2013!. Penyelesaian. Akan dicari m dengan sifat 10m ∥2013!. Diperhatikan bahwa 10 = 2.5 dan 2 < 5. Diperoleh bilangan p, q dengan 2p ∥2013! dan 5q ∥2013! memenuhi q < p, sehingga didapat m = q. Akibatnya ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ 2013 2013 2013 2013 m=q= + + + = 402 + 80 + 16 + 3 = 501. 5 25 125 625
Contoh 7.5.3. Diberikan m dan n bilangan bulat positif. Tunjukkan bahwa m!(n!)m habis membagi (mn)!. Penyelesaian. Diambil sebarang bilangan prima p. Misalkan w, x, y, z bilangan bulat non-negatif dengan sifat pw ∥m!, px ∥n!, py ∥m!(n!)m dan pz ∥(mn)!. Cukup ditunjukkan x ≤ y. Diperhatikan bahwa y = w+mx, sehingga cukup ditunjukkan ⌋ ∞ ⌊ ∑ mn i=1
pi
≥
⌋ ∞ ⌊ ∑ m i=1
pi
+m
∞ ⌊ ⌋ ∑ n i=1
pi
.
Jelas bahwa jika p > n, jumlahan kedua pada ruas kanan bernilai 0, sehingga ketaksamaan benar. Diasumsikan p ≤ n. Misalkan s bilangan bulat positif dengan sifat ps ≤ n < ps+1 . Diperoleh ⌋ ∞ ⌊ ∑ mn i=1
pi
s ⌊ ∑
⌋ ∑ ⌋ ∞ ⌊ mn n = m i + p pi ps i=1 i=1 ⌋⌊ ⌋ s ⌊ ⌋ ∞ ⌊ ∑ ∑ n m n ≥ m + i i p p ps i=1 i=1 ⌋ ∞ ⌊ ∞ ⌊ ⌋ ∑ ∑ m n + . ≥ m i i p p i=1 i=1
Soal Latihan
86
⌊√ ⌋ √ 1. Diketahui x dan y bilangan real dengan sifat ⌊ x⌋ = 9 dan y = 12. Tentukan nilai terkecil yang mungkin dicapai oleh ⌊y − x⌋. 2. Diketahui n bilangan bulat positif dengan 7 digit terakhir dari n! adalah 8000000. Tentukan nilai n. 3. Diketahui s dan t bilangan bulat positif dengan sifat 7s ∥400! dan 3t ∥((3!)!)!. Tentukan nilai s + t. 4. Tentukan bilangan bulat positif terkecil n dengan sifat 10290 |n!. 5. Tentukan semua bilangan real x yang memenuhi ⌊ ⌋ ⌊ ⌋ 3 4 + = 5. x x ⌊ 6. Tentukan sisa pembagian
1066 1033 + 3
⌋ oleh 1000.
7. Tunjukkan bahwa untuk setiap bilangan bulat positif n berlaku ⌊√ ⌋ ⌊√ ⌋ √ √ n+ n+1 = n+ n+2 . 8. Tunjukkan bahwa untuk setiap bilangan bulat positif n berlaku ⌋ ⌊ ⌋ ⌊√ √ 1 3 1 n+ = n− + . 2 4 2 9. Tunjukkan bahwa untuk setiap bilangan bulat positif m dan n berlaku (a) m!n!(m + n)! membagi (2m)!(2n)!. (b) (k!)k
n +k n−1 +...+k+1
|(k n+1 )!.
10. Diberikan bilangan real r dengan sifat ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ 19 20 91 r+ + r+ + ... + r + = 546. 100 100 100 Tentukan ⌊100r⌋. 87
11. Tentukan banyaknya bilangan bulat berbeda pada barisan ⌊ ⌋ ⌊ 2 ⌋ ⌊ 2 ⌋ 1 2 20052 , ,..., . 2005 2005 2005 √ 5+1 12. Diberikan q = dan n bilangan bulat positif. Tentukan nilai dari 2 ⌊q ⌊qn⌋⌋ − ⌊q 2 n⌋. 13. Tunjukkan bahwa untuk setiap bilangan bulat positif n, ⌊ √ n⌋ (2 + 3) merupakan bilangan ganjil. 14. Diberikan p dan q bilangan bulat positif. Tunjukkan bahwa ⌋ q−1 ⌊ ∑ ip i=1
q
=
(q − 1)(p − 1) gcd(p, q) − 1 + . 2 2
15. Tunjukkan bahwa untuk setiap bilangan prima p > 2 berlaku ⌊ √ p⌋ (2 + 5) − 2p+1 habis dibagi oleh p.
88
Soal-Soal Tambahan 1. (a) Diberikan n bilangan bulat lebih dari 2. Tunjukkan bahwa diantara bilangan-bilangan
1 2 n−1 , ,..., , n n n ada sebanyak genap bilangan yang tidak dapat disederhanakan.
(b) Tunjukkan bahwa 12n + 1 30n + 2 tidak dapat disederhanakan untuk setiap bilangan bulat positif n. 2. Diberikan k bilangan bulat positif lebih dari 1. Tunjukkan bahwa terdapat bilangan prima p dan barisan bilangan bulat positif a1 , a2 , . . . , an dengan ai < aj untuk setiap i < j dan setiap suku pada barisan p + ka1 , p + ka2 , p + ka3 . . . merupakan bilangan prima. 3. Diberikan bilangan bulat positif m dan n dengan sifat lcm(m, n) + gcd(m, n) = m + n. Tunjukkan bahwa salah satu diantara dua bilangan tersebut habis dibagi oleh bilangan yang lain. 4. Tunjukkan bahwa untuk setiap bilangan bulat positif a dan b berlaku (36a + b)(a + 36b) ̸= 2k untuk setiap bilangan bulat positif k.
89
5. Tentukan jumlah semua bilangan berbentuk a/b dengan a dan b merupakan faktor positif dari 27000 yang relatif prima. 6. Diberikan x, y, z bilangan bulat positif dengan sifat 1 1 1 − = . x y z Misalkan h = gcd(x, y, z). Tunjukkan bahwa hxyz dan h(y − z) merupakan bilangan kuadrat sempurna. 7. Diberikan p bilangan prima dengan p ≡ 2 (mod 3) dan p|a2 + ab + b2 untuk suatu bilangan bulat a dan b. Tunjukkan bahwa a dan b habis dibagi oleh p. 8. Tentukan semua bilangan bulat positif n dengan sifat
√ 3 n! + 5 bilangan
bulat. 9. Tentukan semua bilangan prima p dengan sifat τ (p2 + 11) = 6. 10. Diberikan bilangan bulat positif n. Jika a ≡ b (mod n), tunjukkan bahwa an ≡ bn (mod n2 ). Apakah sebaliknya tetap berlaku? 11. Diberikan p bilangan prima dan k bilangan bulat dengan 1 ≤ k ≤ p − 1. Tunjukkan bahwa
( ) p−1 ≡ (−1)k k
(mod p).
12. Diberikan bilangan prima p. Tunjukkan bahwa terdapat tak hingga banyaknya bilangan bulat positif n dengan sifat p|2n − n. 13. Diberikan k bilangan ganjil positif. Tunjukkan bahwa 1 + 2 + . . . + n|(1k + 2k + . . . + nk ) untuk setiap bilangan bulat positif n. 14. Diberikan p bilangan prima lebih dari 5. Tunjukkan bahwa tidak ada bilangan bulat x dengan sifat x4 = p − 4. 15. Tunjukkan bahwa untuk setiap bilangan bulat positif n berlaku σ(1) + σ(2) + . . . + σ(n) ≤ n2 . 90
16. Tentuka semua himpunan berhingga atas bilangan bulat positif yang memenuhi i+j gcd(i + j) merupakan anggota S untuk setiap i, j ∈ S. 17. Diketahui bahwa 229 merupakan bilangan sembilan digit dengan setiap digitnya berbeda. Tentukan digit diantara 0,1,2,. . . ,9 yang bukan merupakan digit dari 229 . 18. Tunjukkan bahwa untuk setiap bilangan bulat lebih dari 1, bilangan n5 + n4 + 1 merupakan bilangan komposit. 19. Bilangan 10 digit dikatakan ”menarik” jika setiap digitnya berbeda dan merupakan kelipatan dari 11111. Tentukan banyaknya bilangan menarik. 20. Tentukan semua bilangan prima p dan q dengan sifat pq|(5p − 2p )(5q − 2q ). 21. Tunjukkan bahwa terdapat tak hingga banyaknya bilangan yang tidak memuat digit 0 dan habis dibagi oleh jumlah dari digit-digitnya. 22. Diberikan a dan b bilangan bulat positif yang relatif prima dan dibentuk deret artimatik berikut: a, a + b, a + 2b, . . .. (a) Tunjukkan bahwa terdapat tak hingga banyaknya suku dari barisan aritmatik tersebut yang memiliki faktor prima sama. (b) Tunjukkan bahwa terdapat tak hingga banyaknya pasangan suku dari barisan aritmatik tersebut yang relatif prima. 23. Diberikan n bilangan bulat positif. (a) Tentukan gcd(n! + 1, (n + 1)! + 1). (b) Diberikan a dan b bilangan bulat positif. Tunjukkan bahwa gcd(na − 1, nb − 1) = ngcd(a,b) − 1. (c) Diberikan a dan b bilangan bulat positif. Tunjukkan bahwa gcd(na + 1, nb + 1) habis membagi ngcd(a,b) + 1.
91
(d) Diberikan m bilangan bulat positif dengan gcd(m, n) = 1. Tentukan gcd(5m + 7m , 5n + 7n ). 24. Diberikan a bilangan bulat dengan sifat 1+
1 1 1 a + + ... + = . 2 3 23 23!
Tentukan sisa pembagian a oleh 13. 25. (a) Diberikan p > 3 bilangan prima dan m, n bilangan bulat yang relatif prima dengan sifat m 1 1 1 = 2 + 2 + ... + . n 1 2 (p − 1)2 Tunjukkan bahwa p|m. (b) Diberikan p > 3 bilangan prima. Tunjukkan bahwa ( ) 1 1 2 p |(p − 1)! 1 + + . . . + . 2 p−1 26. Tentukan semua pasangan bilangan bulat non-negatif (x, y) dengan sifat x2 + 3y dan y 2 + 3x merupakan bilangan kuadrat sempurna. 27. Tentukan tiga digit terakhir dari 20032002
2001
.
28. Diberikan p ≥ 3 bilangan prima dan {a1 , a2 , . . . , ap−1 } dan {b1 , b2 , . . . , bp−1 } dua himpunan kelas residu lengkap modulo p. Tunjukkan bahwa {a1 b1 , a2 b2 , . . . , ap−1 bp−1 } bukan himpunan kelas residu lengkap modulo p. 29. Tunjukkan bahwa setiap bilanga bulat positif kurang dari n! dapat dinyatakan sebagai jumlahan tidak lebih dari n bilangan positif yang merupakan faktor dari n!. 30. Tunjukkan bahwa untuk setiap bilangan ganjil n > 1 berlaku n ̸ |2n + 1. 92
31. Diberikan a dan b bilangan bulat positif. Tunjukkan bahwa banyaknya solusi bulat non-negatif (x, y, z) dari persamaan ax + by + z = ab adalah 1 [(a + 1)(b + 1) + gcd(a, b) + 1]. 2 32. Diberikan p, q dan r bilangan prima lebih dari 2 dengan sifat q r + 1. Tunjukkan bahwa 2r|p − 1 atau p|q 2 − 1. 33. Tunjukkan bahwa untuk setiap bilangan bulat positif n berlaku ⌋ ⌊ (n − 1)! . n(n + 1) 34. Tentukan semua bilangan bulat positif n sehingga n memiliki kelipatan dengan digit-digitnya tidak sama dengan 0. 35. Tentukan bilangan bulat terbesar n dengan sifat n habis dibagi oleh setiap √ bilangan bulat positif yang kurang dari 3 n. 36. Tentukan semua bilangan real x dengan sifat x⌊x⌊x⌊x⌋⌋⌋ = 88. 37. Tentukan bilangan bulat a, b, c yang sepasang-sepasang relatif prima dengan a, b, c > 1 dan b|2a + 1,
c|2b + 1,
a|2c + 1.
38. Diberikan n bilangan bulat positif dan p1 , p2 , . . . , pn bilanga prima berbeda yang lebih dari 3. Tunjukkan bahwa 2p1 p2 ...pn + 1 memiliki setidaknya 4n faktor positif. 39. Untuk setiap bilangan bulat positif k, didefinisikan p(k) sebagai faktor ganjil terbesar dari k. Tunjukkan bahwa untuk setiap bilangan bulat positif n berlaku
p(1) p(2) p(n) 2(n + 1) 2n < + + ... + < . 3 1 2 n 3
40. Tentukan semua bilangan bulat positif k dengan sifat τ (n2 ) =k τ (n) untuk suatu bilangan bulat positif n.
93
Materi Pengayaan 1. Dapat di lihat pada website: http://www.imo-official.org 2. Untuk diskusi dengan anak-anak berbakat di bidang matematika silahkan akses http://www.olimpiade.org N1. Carilah semua pasangan bilangan bulat (x, y) yang memenuhi persamaan 5x2 + 20x2 y 2 − 28y 2 = 2013. N2. Apakah terdapat suatu barisan bilangan asli a1 , a2 , a3 , . . . yang memenuhi dua syarat berikut: (i) setiap bilangan asli muncul tepat sekali sebagai suku di barisan dan (ii) untuk setiap bilangan asli n berlaku n habis membagi a1 +a2 +· · ·+an . N3. Bilangan asli n dikatakan ”kuat” jika terdapat bilangan asli x sehingga xnx + 1 habis dibagi 2n . (a) Tunjukkan bahwa 2013 merupakan bilangan kuat. (b) Jika n adalah bilangan kuat, tentukan bilangan asli terkecil x sehingga xnx + 1 habis dibagi 2n . N4. Bilangan rasional positif x dan y memenuhi persamaan x+2 y+2 + = 3 − xy. y+2 x+2 Buktikan bahwa dalam bentuk pecahan paling sederhana, penyebut dari x dan y merupakan bilangan kuadrat sempurna. N5. Cari semua bilangan asli n sehingga terdapat bilangan-bilangan asli x1 , x2 , . . . , xm dengan m ≥ 2 yang memenuhi persamaan x1 + x2 + . . . + xm = x1 x2 . . . xm = n.
94
N6. Suatu himpunan tak kosong A ⊂ Z dikatakan tertutup apabila untuk setiap a, b ∈ A (tidak harus berbeda) terdapat c ∈ A (boleh sama dengan a atau b) sedemikian sehingga 2013 | ab + c. Sebagai contoh {0, 1, 2, 3, . . . , 2012} dan {2013} keduanya tertutup, sementara {3, 4, 5, 6, 7} tidak tertutup. Notasikan X = {1, 2, 3, . . . , 2013}. (a) Buktikan bahwa himpunan X dapat dipartisi menjadi tiga himpunan bagian tak kosong yang masing-masing tertutup. (b) Buktikan bahwa bagaimanapun cara mempartisi X pada soal (a), selalu terdapat satu partisi dengan banyak unsur paling sedikit 1200. Catatan. Faktorisasi prima dari 2013 adalah 3 × 11 × 61 dan 1200 = 2 × 10 × 60 = ϕ(2013) adalah banyak bilangan asli di X yang relatif prima dengan 2013. N7. Suatu bilangan asli x dikatakan bersifat ” binom” jika terdapat bilangan(n) bilangan asli m dan n dengan 1 < m ≤ n2 sehingga m = x. (a) Buktikan bahwa 2013 tidak bersifat binom. (b) Apakah ada bilangan asli kelipatan 2013 yang bersifat binom? (Keterangan:
(n) m
=
n! ) (n−m)!m!
N8. Suatu fungsi f : N → N dikatakan komutatif dengan FPB apabila berlaku f (gcd(m, n)) = gcd(f (m), f (n)) untuk setiap bilangan asli m, n dan dikatakan multiplikatif apabila berlaku f (mn) = f (m)f (n) untuk setiap bilangan asli m, n. (a) Buktikan bahwa terdapat fungsi multiplikatif yang tidak komutatif dengan FPB. (b) Buktikan bahwa fungsi multiplikatif yang juga memenuhi f (f (n)) = n untuk setiap bilangan asli n selalu komutatif dengan FPB. 95
N9. Pasangan bilangan bulat positif (p, q) dikatakan serasi jika p dan q keduanya prima atau relatif prima. Tentukan semua pasangan serasi (p, q) yang memenuhi sifat terdapat bilangan bulat non negatif n sehingga n−2 p+q = 2 pq n +4
Solusi
Hubungi Pembina Tim IMO Indonesia
96
