Teori Bilangan

DAFTAR ISI

BAB I BILANGAN BULAT

1.1 Bilangan Asli

1.2 Bilangan Cacah

1.3 Bilangan Bulat

1.4 Sistem Bilangan Bulat

1.5 Prinsip Urutan Yang Rapi

BAB II PRINSIP INDUKSI MATEMATIKA

2.1 Notasi Jumlah dan Notasi Kali

2.2 Prinsip Induksi Matematika

BAB III KONSEP DASAR KETERBAGIAN

BAB IV FAKTOR PERSEKUTUAN TERBESAR (FPB) DAN KELIPATAN PERSEKUTUAN TERKECIL (KPK)

BAB I

BILANGAN BULAT

Uraian

Pembahasan tentang bilangan bulat (integers) tidak bisa dipisahkan dari uraian tantang bilangan asli (natural numbers) dan bilangan cacah (whole members) karena kreasi tentang bilangan-bilangan ini merupakan proses sosial dan budaya yang berlangsung berurutan dalam waktu ribuan tahun.

Konsep tentang bilangan dan cara mencacah (menghitung, counting) berkembang selama sekitar 15.000 tahun, mulai dari zaman prasejarah (poleolithic, Old Stone Age) sampai dengan zaman sejarah (sekitar tahun 400 S.M.). Dalam periode atau zaman ini, mereka diduga telah mempelajari cara bertani atau bercocok taman, cara berternak, cara menggunakankaleder, cara mengukur atau menimbang berat, cara memindahkan barang dengan kereta atau gerobak, cara membuat perahu, cara berburu, cara pengobatan tradisional, dan cara berhitung.

1.1 Bilangan Asli

Sejak periode sejarah, diduga dimulai sekitar tahun 400 S.M., orang melalui memikirkan bilangan sebagai konsep abstrak. Misalnya, mereka menyebut tiga kerikil dan tiga binatang mempunyai sifat persekutuan, yaitu suatu kuantitas yang disebut tiga. Sifat persekutuan tiga ini bisa dimiliki oleh kelompok benda apa saja sehingga sifat ini menjadi terbatas dari obyek atau sasaran pembicaraan. Dalam istilah yang lebih sederhana, sifat-sifat persekutuan satuan (oneness), duaan (twoness), atau tigaan (threeness) merupakan sifat persekutuan yang dimiliki oleh sebarang kumpulan benda untuk menunjukkan kesamaan kuantitas.

Keperluan tentang kuantitas merupakan kebutuhan dasar manusia dalam kehidupan berkeluarga dan bermasyarakat, terutama untuk menghitung (mencacah) dan membandingkan jumlah barang atau benda.

Keperluan menghitung (mencacah, counting) mendorong orang untuk mencari cara yang mudah, antara lain dengan membuat lambang bilangan (numeral) dan cara menggunakannya (sistem numerasi). Sistem numerasi membuat sekumpulan lambang dasar dan sejumlah aturan untuk menghasilkan lambang-lambang bilangan yang lain. Beberapa peradaban yang telah mengembangkan sistem numerasi antara lain adalah Mesir (sekitar tahun 3000 S.M.), Babylonia (sekitar tahun 2000 S.M.), Yunani atau Greek (sekitar tahun 600 S.M.), Mayan (sekitar tahun 300 S.M.), Jepang – China (sekitar tahun 200 S.M.), Romawi (sekitar tahun 100 M), dan Hindu-Arab (mulai sekitar tahun 300 S.M. di India, mengalami perubahan di wilayah timur tengah sekitar tahun 750 Masehi, berkembang di Eropa dan dipakai di seluruh dunia sampai sekarang). Dari uraian di atas kita dengan singkat telah melihat perjalanan pengembangan konsep bilangan sejak pertama kali pada zaman Poleolithic sampai pada zaman sejarah. Dengan demikian kita perlu membuat asumsi bahwa manusia telah menemukan konsep bilangan asli (counting/natural members) dan telah menemukan himpunan lambang untuk menyatakan konsep bilangan asli yaitu 1, 2, 3, 4, … Untuk selanjutnya himpunan bilangan asli dinyatakan dengan N = {1, 2, 3, 4, … }

1.2 Bilangan Cacah

Untuk kepentingan masyarakat zaman pertanian, sebelum zaman revolusi, mereka hanya memerlukan mencacah, menjumlah, dan mengalikan. Seiring dengan perkembangan zaman, masyarakat memerlukan sistem bilangan yang dapat memenuhi keperluan lain, yaitu mengurangkan dan membagi. Dengan demikian mereka mempunyai tuntutan pekerjaan yang tidak sekedar berhitung (aritmetika) tetapi hal lain yang lebih luas.

Jika sebelumnya mereka menerima pernyataan tanpa bukti (postulat):

p + q adalah suatu bilangan asli

p x q adalah suatu bilangan asli

maka kesulitan akan muncul ketika pengertian pengurangan mulai diperkenalkan melalui penjumlahan:

p – q = r jika ada r sedemikian hingga p = q + r

Kita bisa melihat kesulitan itu. Pengurangan pada unsur-unsur himpunan bilangan asli dapat dilakukan hanya jika p lebih dari q, artinya himpunan bilangan asli tidak bersifat tertutup terhadap pengurangan. Pada awalnya tentu mereka memahami bahwa:

3 – 2 = 1, 4 – 3 = 1, 5 – 4 = 1

dan mulai mempertanyakan bagaimana dengan

3 – 3 = ? , 4 – 4 = ?, 5 – 5 = ?

Jawabannya adalah mereka perlu “tambahan” bilangan baru, yang kemudian disebut dengan nol (zero), yang diberi makna:

3 = 3 + 0, 4 = 4 + 0, 5 = 5 + 0

Sekarang kita telah menambahkan unsur baru 0 ke dalam sistem bilangan asli, sehingga diperoleh himpunan baru yang disebut himpunan bilangan cacah, dinyatakan dengan:

W = {0, 1, 2, 3, 4, …}

1.3 Bilangan Bulat

Dengan berkembangnya masyarakat industri, manusia memerlukan bilangan untuk keperluan pembukuan tingkat lanjut, antara lain untuk menghitung hutang dan pihutang, serta tabungan dan pinjaman. Pertanyaan yang muncul serupa dengan permasalahan:

6 – 7 = ?, 8 – 10 = ?, 3 – 10 = ?

Permasalahan ini serupa dengan usaha menambah bilangan-bilangan baru di dalam W sehingga mereka dapat melakukan semua pengurangan, atau himpunan baru yang diperoleh bersifat tertutup terhadap pengurangan.

Jawaban terhadap kesulitan mereka adalah tambahan bilangan-bilangan baru yang diperoleh dari:

0 – 1, 0 – 2, 0 – 3, 0 – 4, …

yang kemudian dilambangkan dengan:

-1, -2, -3, -4, …

sehingga diperoleh himpunan baru yang disebut himpunan bilangan bulat, dan dinyatakan dengan:

Z = {…, -2, -1, 0, 1, 2, 3, …}

Dengan digunakannya garis bilangan untuk menyatakan representasi bilangan, dan memberi makna terhadap bilangan-bilangan di sebelah kanan nol sebagai bilangan positif serta di sebelah kiri nol sebagai bilangan negatif, maka himpunan bilangan bulat dapat dinyatakan sebagai:

Z = {…, -2, -1, 0, 1, 2, 3, …}

1.4 Sistem Bilangan Bulat

Untuk keperluan menghitung, orang dapat melakukan penjumlahan, pengurangan, perkalian, atau pembagian bilangan. Apa yang dilakukan oleh orang itu kemudian disebut sebagai suatu operasi. Pada dasarnya suatu operasi adalah mengambil sepasang bilangan untuk mendapatkan bilangan lain yang tunggal. Bilangan yang diperoleh mungkin unsur atau bukan unsur dari himpunan tertentu.

Definisi 1.1

Suatu sistem matematika adalah suatu himpunan bersama-sama dengan satu atau lebih operasi pada himpunan itu.

Notasi

Suatu sistem matematika yang terdiri dari himpunan S dan operasi * ditunjukkan dengan (S, #)

Jika # adalah operasi kedua S, maka (S, *, #) adalah sistem matematika yang terdiri dari himpunan S, operasi pertama *, dan operasi kedua #.

Berdasarkan pengetahuan yang telah kita pelajari sebelumnya, beberapa definisi yang terkait dengan sifat operasi adalah:

Definisi 1.2

Ditentukan bahwa * adalah suatu operasi pada himpunan S.

Operasi * disebut bersifat:

a. tertutup jika p * q = r dan r Î S untuk setiap p, q Î S.

b. komutatif jika p * q = q * p untuk setiap p, q Î S

c. assosiatif jika p * (q * r) = (p * q)*r untuk setiap p, q, c Î S

d. mempunyai unsur identitas jika untuk semua p Î S, ada i Î S, sehingga p * i = i * p = p . I disebut unsur identitas operasi *.

e. memenuhi sifat inversi (invertibel) jika untuk semua pÎ S, ada x Î S, sehingga p * x = x * p = i. x disebut inversi dari p, dan p disebut inversi dari x.

Definisi 1.3

Ditentukan bahwa * adalah suatu operasi pertama dan ⋕ adalah suatu operasi kedua pada himpunan S. Operasi * bersifat distributif terhadap # jika p * (q #r) = (p * q) # (p * r) untuk semua p, q, r Î S.

Selanjutnya, sifat-sifat operasi penjumlahan dan perkalian pada himpunan bilangan bulat merupakan aksioma, yaitu:

1. tertutup: p + q Î Z dan p x q Î Z untuk semua p, q, Î Z

2. komutatif: p + q = q + p dan p x q = q x p untuk semua p, q Î Z

3. assosiatif: p + (q + r) = (p + q) + r dan p x (q x r) = (p x q) x r untuk semua p, q, r Î Z

4. mempunyai unsur identitas p + 0 = p dan p x 1 = p untuk semua p Î Z

5. memenuhi sifat identitas penjumlahan:

untuk semua p Î Z, ada 0 Î Z sehingga p + 0 = 0 + p = p 0 adalah unsur identitas penjumlahan

6. memenuhi sifat inversi (invertibel) penjumlahan:

untuk semua p Î Z, ada x Î Z sehingga p + x = x + p = 0. x disebut inversi dari p, ditunjukkan dengan x = -p

7. distributif perkalian terhadap penjumlahan (p + q) . r = p . r + q . r

8. memenuhi hukum kanselasi: jika p, q, r Î Z, r ¹ 0, dan pr = qr, maka p = q

Dalam kaitannya dengan urutan bilangan bulat, kita akan menggunakan himpunan bilangan bulat positif {1, 2, 3, …}, untuk menyatakan hubungan kurang dari (atau lebih dari) antara dua bilangan bulat.

Definisi 1.4

Ditentukan p, q, Î Z

p disebut kurang dari q (atau q disebut lebih dari p), ditulis p < q atau q > p, jika ada suatu bilangan bulat positif r sehingga q – p = r

Contoh 1.1

(a). 5 > 4 sebab ada bilangan bulat positif 1 sehingga 5 – 4 = 1

(b). 2 < 7 sebab ada bilangan bulat positif 5 sehingga 7 – 2 = 5

(c). p > 0 untuk setiap p Î {1, 2, 3, …} sebab ada bilangan bulat positif p sehingga p – 0 = p

Dua sifat dasar tentang urutan bilangan bulat yang perlu untuk dipahami adalah:

(1) ketertutupan bilangan bulat positif: p + q dan pq adalah bilangan-bilangan bulat positif untuk semua bilangan-bilangan bulat positif p dan q

(2) hukum trikotomi: Untuk setiap p Î Z berlaku salah satu dari p > 0, p = 0, atau p < 0.

Himpunan bilangan bulat disebut suatu himpunan yang terurut karena Z mempunyai suatu himpunan bagian yang tertutup terhadap penjumlahan dan perkalian, serta memenuhi hukum trikotomi untuk setiap bilangan bulat

Contoh 1.2

Buktikan: Jika p < q dan r > 0, maka pr < qr

Bukti:

Diketahui bahwa p < q, maka menurut definisi 1.4, q – p > 0. Selanjutnya, karena q – p > 0 dan r > 0, maka menurut sifat dasar ketertutupan perkalian urutan bilangan bulat positif, r (q – p) > 0. Menurut sifat distributif, r(q – p) = rq – rp, dengan demikian r(q – p) > 0 berakibat rq – rp > 0.

rq – rp > 0, menurut definisi 1.4, rp < rq, dan menurut sifat komutattif perkalian, pr < qr.

Contoh 1.3

Buktikan: (–1)p = –p

Bukti: (–1)p + 1.p = (-1 + 1).p = 0, dan –p + p = -p + 1.p = 0, sehingga (-1)p + 1.p = -p + 1.p. Berdasarkan hukum kanselasi, (-1)p = -p

Contoh 1.4

Sistem (Z, Æ), yaitu sistem bilangan bulat terhadap operasi penjumlahan, merupakan suatu grup, dan juga merupakan grup Abel sebab operasi Æ terhadap bilangan bulat memenuhi sifat-sifat terhadap assosiatif, mempunyai unsur identitas, dan memenuhi sifat inversi.

1.5 Prinsip Urutan yang Rapi (Well Ordering Principle)

Suatu himpunan H disebut terurut rapi (well ordered) jika setiap himpunan bagian dari H yang tidak kosong mempunyai unsur terkecil

Perlu diingat kembali bahwa k disebut unsur terkecil suatu himpunan S jika k kurang dari atau sama dengan x untuk setiap x S.

Contoh 1.5

(a) S = {2,5,7} mempunyai unsur terkecil 2 sebab 2 ≤ x untuk setiap x S, yaitu

2 ≤ 2, 2 ≤ 5, dan 2 ≤ 7

(b) M = {3} mempunyai unsur terkecil 3 sebab 3 ≤ x untuk setiap x M, yaitu 3 ≤ 3

Contoh 1.6

(a) S = {2,5,7} adalah himpunan yang terurut rapi sebab setiap himpunan bagian dari S yang tidak kosong, yaitu {2}, {5}, {7}, {2,5}, {2,7}, {5,7} dan {2,5,7}mempunyai unsur terkecil berturut-turut adalah 2,5,7,2,2,5, dan 2.

(b) Z⁺ adalah himpunan yang terurut rapi sebab semua himpunan bagian dari Z⁺

yang tidak kosong mempunyai unsur terkecil

yang tidak kosong dan tidak mempunyai unsur terkecil, misalnya {…, -2, -1, 0}

Definisi 1.5

Bilangan riil terbesar [x] adalah bilangan bulat terbesar kurang dari atau sama dengan x, yaitu [x] adalah bilangan bulat yang memenuhi [x] ≤ x ≤ [x] + 1

Sebagai catatan perlu diingat kembali bahwa Fungsi f(x) = [x] disebut dengan fungsi bilangan bulat terbesar, atau juga disebut dengan fungsi lantai (floor function). Fungsi g(x) = disebut fungsi atap (ceiling function), dimana adalah bilangan bulat terkecil lebih dari atau sama dengan x, misalnya dan

Suatu bilangan riil x disebut rasional jika dan hanya jika ada bilangan-bilangan bulat a dan b, b 0, dan x = a/b. Suatu bilangan yang tidak rasional disebut bilangan irasional, misalnya log 5 , , bilangan e = 2,71828…, dan bilangan = 3,14…

Contoh 1.7

(a) [2/3] = 0 , [7/3] = 2 , dan [ ] = 3

(b) [ – 2/3] = – 1 , [ –7/3] = – 3

Tugas dan Latihan

Tugas

Untuk memperluas wawasan Anda tentang sistem numerasi, carilah dan bacalah sumber-sumber pustaka yang memuat sejarah bilangan. Selanjutnya jawablah beberapa pertanyaan berikut

1. Apa maksudnya sistem numerasi bersifat aditif?

2. Apa yang disebut dengan sistem numerasi menggunakan nilai tempat?

3. Apa maksudnya sistem numerasi bersifat multiplikasi?

4. Sebutkan beberapa cara menuliskan lambang bilangan dan terjadi pada sistem numerasi yang mana.

5. Sebutkan basis-basis bilangan yang pernah digunakan.

2. Latihan

Untuk memperdalam pemahaman Anda tentang materi bilangan bulat, kerjakanlah soal-soal latihan berikut:

1. Tunjukkan bahwa –(p + q) = (– p) + (– q) untuk semua p, q Î Z

2. Tunjukkan bahwa – (p.q) = p . (-q) untuk semua p, q Î Z

3. Diketahui p, q, r Î Z, p < q, dan r < 0

Buktikan: p + r < q + r

4. Diketahui p, q, r Î q, p > q dan q > r

Tunjukkan: p > r

5. Diketahui C = {1, -1}

Selidiki apakah (C, x) merupakan sistem grup.

BAB II

PRINSIP INDUKSI MATEMATIKA

Uraian

Prinsip induksi matematika merupakan suatu alat berharga untuk membuktikan hasil-hasil yang terkait dengan bilangan bulat, atau hubungan tertentu yang dapat diperluas berlaku untuk semua bilangan asli. Hasil-hasil yang terkait terutama tentang penjumlahan, dan hubungan tertentu antara lain dapat berupa ketidaksamaan, keterbagian, atau differensial.

Dalam kaitannya dengan hasil penjumlahan, prinsip induksi matematika melibatkan notasi jumlah (summation) dan notasi kali (products). Kedua notasi ini sangat bermanfaat untuk menyederhanakan tulisan sehingga menjadi lebih singkat dan lebih mudah dipahami.

2.1. Notasi Jumlah dan Notasi Kali

Notasi jumlah adalah notasi yang dilambangkan dengan å, dan notasi kali adalah notasi yang dilambangkan dengan , dan didefinisikan sebagai:

Huruf i dari indeks jumlah notasi jumlah atau notasi kali disebut variabel dummy karena dapat diganti oleh sebarang huruf, misalnya:

= =

i = 1 disebut batas bawah (lower limit) dan i = r disebut batas atas (upper limit).

Contoh 2.1

(a) = 1 + 2 + 3 + 4 = 10

(b) = 1 . 2 . 3 . 4 = 24

(d) 3 = 3 . 3 . 3 . 3 . 3 = 243

(e) = 1² + 2² + 3² = 14

(f) = 1² . 2² . 3² = 36

Selanjutnya, indeks jumlah tidak harus dimulai dari 1, artinya dapat dimulai dari bilangan bulat selain 1 asalkan batas bawah tidak melebihi batas atas.

Contoh 2.2

(a) = 3 + 4 + 5 = 12

(b) = (2.4 – 1) + (2.5 – 1) + (2.6 – 1) = 27

(d) = (2 – 1)(3 – 1) (4 – 1) = 1 . 2 . 3 = 6

Beberapa sifat yang terkait dengan notasi jumlah adalah:

(1) = tx_r+ tx_r+1 + … + tx_s= t(x_r + x_r+1 + … + x_s) =

(2) = (x_r + y_r) + (x_r+1 + y_{r + 1})+ … + (x_s + y_s)

= (x_r + x_{r
+ 1} + … + x_s) + (y_r + y_{r + 1}+ … + y_s) = +

(3) x_i y_j = (x_i ) = x_i (y_c + y_c+1 + … + y_d)

= x_a (y_c + y_c+1 + … + y_d) + x_a+1(y_c + y_{c +1} + …+y_d) + … + x_b(y_c + y_c+1 + … + y_d)

= (x_a + x_a+1 + … + x_b)(y_c + y_c+1 + … + y_d) =

(4) = = = y_j x_i = x_i y_j

Contoh 2.3

(a) 2x_i = 2x₃ + 2x₄ + 2x₅ = 2(x₃ + x₄ + x₅) = 2 x_i

(b) (2a_i + 3b_i) = (2a₂ + 3b₂) + (2a₃ + 3b₃) + (2a₄ + 3b₄) = (2a₂ + 2a₃ + 2a₄) + (3b₂ + 3b₃ + 3b₄)

= 2(a₂ + a₃ + a₄) + 3(b₂ + b₃ + b₄) = 2 a_i + 3 b_i

(d) ij² = (i . j² + 2 . j² + 3 . j²) = = 6 . 1² + 6 . 2² = 6 . 1 + 6 . 4 = 30

2.2 Prinsip Induksi Matematika (Principle of Mathematical Induction)

S adalah suatu himpunan bagian dari himpunan bilangan asli yang unsur-unsurnya memenuhi hubungan.

Jika: (a) 1 Î S

(b) k Î S berakibat (k + 1) Î S maka: S memuat semua bilangan asli, yaitu S = N

Bukti:

Misalkan S Ì N dan unsur-unsur S memenuhi suatu hubungan, serta (a) dan (b) dipenuhi oleh S. Harus dibuktikan bahwa S = N. Untuk membuktikan S = N digunakan bukti tidak langsung.

Anggaplah S ≠ N, maka tentu ada F Ì N dan F ≠ Æ yang mana F = {t Î N| t Ï S}. Karena F ≠ Æ dan F Ì N, maka menurut prinsip urutan rapi, F mempunyai unsur terkecil k, yaitu k Î F tetapi k Ï S. k ≠ 1 sebab 1 Î S, berarti k > 1, dan akibatnya k – 1 Î N. k adalah unsur terkecil F, maka k – 1 Ï F sebab k – 1 < k, berarti k – 1 Î S. k – 1 Î S dan S memenuhi (b), maka (k – 1) + 1 Î S, atau k – 1 + 1 Î S, yaitu k Î S.

Terjadi kontradiksi karena k Ï S dan k Î S, jadi S = N

Dalam pernyataan lain, prinsip induksi matematika dapat ditulis dengan S(n) adalah suatu pernyataan yang memenuhi hubungan untuk satu atau lebih n Î N. Jika: (a) S(1) benar (b) S(k) benar berakibat S (k + 1) benar maka S(k) benar untuk semua n Î N.

Contoh 2.4

Buktikan untuk sebarang n Î Z⁺, = 1 + 2 + 3 + … + n = n (n + 1)

Bukti: S(n) : = n (n + 1)

S(1) benar sebab untuk n = 1:

= = 1 dan n (n + 1) = . 1 (1 + 1) = . 2 = 1

Misalkan S(k) benar, yaitu untuk n = k:

= 1 + 2 + … + k = k (k + 1)

Harus dibuktikan S(k + 1) benar, yaitu:

= 1+ 2 + 1…+ k+ k + 1 = (k +1)(k + 1 +1) = (k +1) (k+ 2)

= 1 + 2 + … + k + k + 1 = k(k + 1) + k + 1

k(k + 1) = (k + 1) ( k + 1) =(k + 1) . (k + 2)

= (k + 1)( k + 2)

Jadi: S(n) benar untuk sebarang n Î Z⁺

Contoh 2.5

Buktikan untuk sebarang n Î Z⁺, = 1² + 2² + …+ n² = n(n + 1)(2n + 1)/6

Bukti: S(n) = = n(n + 1)(2n + 1)/6

S(1) benar sebab untuk n = 1:

= = 1² = 1 dan n(n + 1)(2n + 1) = . 1 . 2 . 3 = 1

Misalkan S(k) benar, yaitu untuk n = k:

= 1² + 2² + … + k² = k(k + 1)(2k + 1)

Harus dibuktikan S(k + 1) benar, yaitu

= 1² + 2² + … +k² + (k + 1)² = (k + 1)(k + 2)(2k + 3)

= 1² + 2² + … +k² + (k + 1)² = k(k + 1) (2k + 1) + (k + 1)²

k(k + 1) (2k + 1)

= (k + 1) { k (2k + 1) + (k + 1)}

= (k + 1) {k(2k + 1) +6 (k + 1)}

= k (k + 1) + (2k² + k + 6k +6)

= (k + 1) (2k² + 7k + 6)

= (k + 1)(k + 2) (2k +3)

Jadi: S(n) benar untuk sebarang n Î Z⁺

Contoh 2.6

Buktikan: untuk semua n Î Z⁺, dan n ³ 6, 4n < n² – 7

Bukti : S(n): 4n < n² – 7, n ³ 6

S(6) benar sebab untuk n = 6

4n = 4 . 6 = 24, n² – 7 = 6² – 7 = 36 – 7 = 31, dan 24 < 31

Misalkan S(k) benar, yaitu untuk n = k:

4k < k² – 7

Harus dibuktikan bahwa S(k + 1) benar, yaitu untuk n = k + 1,

4(k + 1) < (k + 1)² – 7

4(k + 1) = 4k + 4 < (k² – 7) + 4

4k + 4 < (k² – 7) + 13, sebab 4 < 13

4k + 4 < (k² – 7) + (2k + 1), sebab 2k + 1 ³ 13 untuk

n ≥ 6

4k + 4 < (k² + 2k + 1) – 7

4k + 4 < (k + 1)² – 7

Jadi: 4n < n² – 7 untuk semua bilangan bulat n ³ 6

Contoh 2.7

Buktikan: 6^{n
+ 2} + 7^{2n + 1} habis dibagi oleh 43 untuk semua n Î Z⁺

Bukti : S(n) : 6^{n + 2} + 7^{2n + 1} habis dibagi oleh 43

S(1) benar sebab untuk n = 1:

6^{n + 2} + 7^{2n + 1} = 6³ + 7⁵ = 559 = 43(13)

559 habis dibagi oleh 43

Misalkan S(k) benar, yaitu untuk n = k:

6^{k
+ 2} + 7^{2k + 1} habis dibagi oleh 43

Harus dibuktikan bahwa S(k + 1) benar, yaitu untuk

n = k + 1, 6^{k + 3} + 7^2k+3 habis dibagi oleh 43

(6^{k + 3} + 7^{2k + 3}) – (6^{k + 2} + 7^{2k + 1})

= (6^{k + 3} – 6^{k + 2}) + (7^{2k + 3} – 7^{2k +1})

= 6^{k + 2} (6 – 1) + 7^{2k +
1} (7² – 1)

= 5 . 6^{k + 2} + 48 . 7^{2k
+ 1}

= 5 .6^{k + 2} + (5 + 43) . 7^{2k
+ 1}

= 5(6^{k + 2} + 7^{2k + 1}) + 43 . 7^{2k + 1}

= 5 . 43x + 43 . 7^{2k + 1}

6^{k
+ 3} + 7^{2k + 3}– 43x = 5 . 43x + 43 . 7^{2k + 1}

6^{k
+ 3} + 7^{2k + 3} = 6(43x) + 43 . 7^{2k + 1}

= 43 (6x + 7^{2k + 1})

6^{k
+ 3} + 7^{2k + 3} habis dibagi oleh 43 sebab mempunyai faktor 43

Jadi: 6^{n + 3} + 7^{2n + 3} habis dibagi oleh 43 untuk semua n Î Z⁺

Tugas Dan Latihan

Tugas

Buktikan dengan induksi matematika

1. n < 2ⁿ untuk semua n Î Z⁺

2. n³ – n habis dibagi 3 untuk semua n Î Z⁺

3. 2ⁿ < ! untuk setiap bilangan bulat positif n ³ 4

Latihan

Buktikan dengan induksi matematika

1. Di dalam barisan harmonis:

1 + + + + …

berlaku

³ 1 + , untuk setiap bilangan bulat n ³ 0

2. = nx^{n – 1} untuk setiap bilangan bulat n ³ 0

3. = + + … + =

4. t² = 1² + 2² + 3² + … + r² = r(r + 1)(2r + 1)/6 untuk setiap n Î Z⁺

5. = + + + + … + = –

dengan hubungan menggunakan hubungan: =

BAB III

KONSEP DASAR KETERBAGIAN

Uraian

Pembagian bilangan bulat merupakan bahan pelajaran matematika yang sudah diberikan di sekolah dasar. Bahan pelajaran ini diperluas penggunaannya sampai pada pemfaktoran prima, faktor persekutuan terbesar (FPB), kelipatan persekutuan terkecil (KPK), dan keterbagian oleh bilangan tertentu (misalnya keterbagian oleh 2,3, atau 9). Untuk memberikan dasar atau landasan yang lebih kuat kepada guru matematika di sekolah, maka mereka perlu belajar lebih mendalam tentang konsep-konsep dasar keterbagian.

Keterbagian (divisibility) merupakan dasar pengembangan teori bilangan, sehingga konsep-konsep keterbagian akan banyak digunakan di dalam sebagian besar uraian atau penjelasan matematis tentang pembuktian teorema.

Jika suatu bilangan bulat dibagi oleh suatu bilangan bulat yang lain, maka hasil baginya adalah suatu bilangan bulat atau suatu bilangan yang tidak bulat, misalnya, jika 40 dibagi 8, maka hasil baginya adalah bilangan bulat 8; tetapi jika 40 dibagi 16, maka hasil baginya adalah 2,5. Keadaan inilah yang memberikan gagasan tentang perlunya definisi keterbagian.

Definisi 3.1

Suatu bilangan bulat q habis dibagi oleh suatu bilangan bulat p ≠ 0 jika ada suatu bilangan bulat x sehingga q = px

Notasi

p | q dibaca p membagi q, p faktor dari q, q habis dibagi p, atau q kelipatan dari p

p Q q dibaca p tidak membagi q, p bukan faktor dari q, q tidak habis dibagi p, atau q bukan kelipatan dari p

Contoh 3.1

a. 6 | 18 sebab ada bilangan bulat 3 sehingga 18 = 6.3

b. 12 Q 15 sebab tidak ada bilangan bulat x sehingga 15 = 12.x

c. 5 | -30 sebab ada bilangan bulat -6 sehingga -30 = 5.(-6)

d. -4 | 20 sebab ada bilangan bulat 5 sehingga 20 = (-4).5

Berdasarkan definisi 2.1 diatas jelas bahwa faktor-faktor suatu bilangan bisa merupakan bilangan bulat positif atau merupakan bilangan bulat negatif. Dengan demikian, faktor-faktor dari:

6, adalah 1, -1, 2, -2, 3, -3, 6, dan -6

15, adalah 1, -1, 3, -3, 5, -5, 15, dan -15

Beberapa sifat sederhana keterbagian adalah :

1. 1 | p untuk setiap p Î Z

2. p | 0 untuk setiap p Î Z dan p ≠ 0

3. p | p untuk setiap p Î Z dan p ≠ 0

4. Jika p | q, maka kemungkinan hubungan antara p dan q adalah p < q, p = q, atau p > q (misal 3 | 6, 3 | 3, atau 3 | -3)

Teorema 3.1

Jika p, q Î Z dan p | q, maka p | qr untuk semua r Î Z

Bukti:

Diketahui bahwa p | q, maka menurut definisi 3.1, ada suatu xÎZ sehingga q = px.

q = px berarti qr = pxr, atau qr = p(x.r) dengan xr Î Z (sebab x Î Z dan r Î Z)

Sesuai dengan definisi 3.1, karena qr = p(xr) maka p | qr

Teorema 3.2

Jika p , q, r Î Z, p | q, dan q | r , maka p | r

Bukti:

Diketahui p | q dan q | r, maka menurut definisi 3.1, tentu ada x, y Î Z sehingga q = px dan r = qy,

r = qy dan q = px, maka r = (px)y atau r = p (xy) dengan x, yÎZ

Sesuai dengan definisi 3.1, karena r = p(xy), maka p | r

Teorema 3.3

Jika p, q Î Z, p | q dan q | p, maka p = q

Bukti:

Diketahui p | q dan q | p maka menurut definisi 3.1, terdapat x,y Î Z sehingga p = qx dan q = py.

Jadi: p = (py)x = p(yx) = (xy) = (xy)p, atau 1.p = (xy) p.

Maka xy = 1

Dengan demikian, karena x,y Î Z dan xy = 1, maka diperoleh x = -1 = y atau x = 1 = y

Jika x = -1 = y, maka p = -q

Jika x = 1 = y, maka p = q

Teorema 3.4

Jika p, q, r Î Z, p | q dan p | r, maka p | q + r

Bukti:

Karena p | q dan p | r, maka menurut definisi 3.1, ada x,y Î Z sehingga q = px dan r = py. Dengan demikian q + r = px + py = p(x + y). Kerena x,yÎZ, maka sesuai dengan sifat tertutup penjumlahan bilangan bulat, x + y Î Z. Jadi : p | q + r

Teo 3.4 dapat diperluas tidak hanya berlaku untuk q, r tetapi untuk q, r, s, t,.., artinya jika p|q, p|r, p | s, p | t, dan…, maka p | q + r + s + t +…

Selanjutnya, teorema 3.4 tetap berlaku jika operasi penjumlahan (+) diganti dengan operasi pengurangn (-), buktikan !

Teorema 3.5

Jika p, q, r Î Z, p | q dan p | r, maka p | qx + ry untuk semua x, y Î Z (qx + ry disebut kombinasi linear dari q dan r)

Buktikan!

Teorema 3.6.

Jika p, q, r Î Z, p > 0, q > 0, dan p | q, maka p £ q

Bukti:

Karena p | q, maka menurut definisi 3.1, ada x Î Z sehingga q = px

Karena p > 0, q > 0, dan q = px, maka x > 0

Karena x Î Z dan x > 0, maka kemungkinan nilai-nilai x adalah 1, 2, 3, …, yaitu x = 1 atau x > 1

Jika x = 1, maka q = px = p(1) = p.

Jika x > 1, dan q = px, maka p < q

Jadi p ≤ q

Teorema 3.7

Jika p, q, r Î Z, p > 0, q > 0, p | q dan q | p, maka p = q.

Buktikan!

Teorema 3.8

p | q jika dan hanya jika kp | kq untuk semua k Î Z dan k ≠ 0

Buktikan!

Teorema 3.9

Jika p, q, r Î Z, p ≠ 0, p | q + r, dan p | q, maka p | r

Buktikan!

Uraian berikutnya membahas tentang algoritma pembagian. Suatu algoritma didefinisikan sebagai serangkaian langkah-lanbgkah atau prosedur yang jelas dan terhingga untuk menyelesaikan suatu masalah. Kita lazim menggunakan istilah algoritma pembagian (division algoritma) meskipun istilah ini tidak menunjukkan adanya altoritma. Pembicaraan algoritma sebagai prosedur dalam menyelesaikan masalah terdapat nanti pada pembahasan tentang algoritma Enclides.

Teorema 3.10, Algoritma Pembagian

Jika p, q Î Z dan p > 0, maka ada bilangan-bilangan r, s Î Z yang masing-masing tunggal sehingga q = rp + s dengan 0 £ s < p.

Jika p tidak membagi q, maka s memenuhi ketidaksamaan 0 < s < p.

Dari pernyataan q = rp + s, 0 ≤ s < p, r disebut hasil bagi (quotient), s disebut sisa (remainder), q disebut yang dibagi (dividend) dan p disebut pembagi (divisor). Kita secara tradisi menggunakan istilah algoritma meskipun sesungguhnya algoritma pembagian bukan merupakan suatu algoritma.

Sebelum membuktikan Teorema 2.9, agar lebih mudah dalam memahami langkah-langkah pembuktian, simaklah dengan cermat uraian berikut:

Ditentukan dua bilangan bulat 4 dan 7 dengan 4 | 7, maka dapat dibuat barisan aritmetika 7 - (r.4) dengan x Î Z

untuk r = 3, 7 - (r.4) = 7 - 12 = -5

untuk r = 2, 7 - (r.4) = 7 - 8 = -1

untuk r = 1, 7 - (r.4) = 7 - 4 = 3

untuk r = 0, 7 - (r.4) = 7 – 0 = 7

untuk r = -1, 7 - (r.4) = 7 – (-4)= 11

dan seterusnya

sehingga diperoleh barisan …, -5, -1, 3, 7, 11, …

Barisan ini mempunyai suku-suku yang negativf, dan suku-suku yang tidak negatif sebagai unsur-unsur himpunan T.

T = {3, 7, 11,…} atau T = {7 – (4.r) | r Î Z, 7 – (4.r) ³ 0}

Karena T N dan N adalah himpunan yang terurut rapi, maka menurut prinsip urutan rapi, T mempunyai unsur terkecil.

Perhatikan bahwa unsur terkecil T adalah 3.

Karena 3 Î T, maka 3 = 7 – (4.r) untuk suatu r Î Z. dalam hal ini r = 1, sehingga

3 = 7 - (4.1), atau 7 = 1.4 + 3

Dengan demikian dapat ditentukan bahwa:

7 = 1.4 + 3 dengan 0 £ 3 < 4

Karena 4 │ 7, maka 7 = r.4 + s dengan r = 1 dan s = 3

Perhatikan bahwa untuk 4, 7 Î Z, ada r, s Î Z sehingga 7 = r.4 + s dengan 0 ≤ s < 4

Marilah sekarang kita membutikan Teorema 3.10

Bukti:

Dengan p, q Î Z dapat dibentuk suatu barisan aritmatika (q – rp) dengan r Î Z, yaitu … , q – 3p, q – 2p, q – p, q, q + 2p, q + 3 p, …

yang mempunyai bentuk umum q – rp

Ambil suatu himpunan T yang unsur-unsurnya adalah suku barisan yang tidak negatif, yaitu:

T = {q – rp | r Î Z, q – rp ³ 0}

Karena T N dan N adalah himpunan yang terurut rapi, maka menurut prinsip urutan rapi, T mempunyai unsur terkecil, misalnya s.

Karena s Î T, maka s = q – rp untuk suatu r Î Z, sehingga q = rp + s.

Jadi jika p, q Î Z dan p > 0, maka ada r, s Î Z sehingga q = rp + s.

Sampai disini pembuktian baru pada tahap menunjukkan eksistensi dari r dan s. berikutnya akan dibuktikan bahwa 0 ≤ s < p dengan menggunakan bukti tidak langsung.

Anggaplah bahwa 0 £ s < p tidak benar, s < 0 atau s ³ p.

Karena s Î T, maka s tidak mungkin negatif, sehingga kemungkinannya tinggal s ³ p.

s ³ p, maka s – p ³ 0, sehingga (q – rp) – p ³ 0 atau q – (r + 1) p ³ 0.

Karena s – p ³ 0 dan s – p = q – (r + 1) p atau s – p mempunyai bentuk q – rp, maka s – p Î T

Karena p > 0, maka s – p < s, sehingga s – p merupakan unsur T yang lebih kecil dari s. Hal ini bertentangan dengan pengambilan s sebagai unsur terkecil dari T.

Jadi: 0 £ s < p

Selanjutnya, buktikan ketunggalan dari r dan s

Petunjuk: gunakan bukti tidak langsung, misalnya r dan s tidak tunggal, yaitu ada r₁, r₂, s₁, s₂ Î Z dan :

q = r₁p + s₁, 0 < s₁ < p

q = r₂p + s₂, 0 < s₁ < p

Contoh 3.1

Tunjukkan:

a. Jika p | q, maka p²| q²

b. Jika p | q, maka p | 3q²

Jawab:

a. Karena p | q, maka sesuai dengan definisi 2.1, ada bilangan k Î Z sehingga q = kp, dengan demikian q² = k²p².

Sesuai dengan sifat ketertutupan perkalian bilangan bulat, karena k Î Z, maka k . k = k² Î Z

q² = k²p² dan k² Î Z, maka sesuai dengan definisi 2.1, p²| q².

b. Karena p | q, maka sesuai dengan teorema 2.1, p|qr untuk semua r Î Z

Ambil r = 3q, maka 3q Î Z untuk sebarang q Î Z

Dengan demikian, dari p | qr dan r = 3q Î Z, maka p | q (3q) atau

p | 3q².

Contoh 3.2.

Diketahui: (a₁a₀) = a₁.10 + a₀ dan 3 | t

Tunjukkan bahwa t | a₁ + a₀

Jawab:

t = a₁.10 + a₀ = a₁ (9 + 1) + a₀ = 9a₁ + (a₁ + a₀)

3 | t atau 3 | 9a₀ + (a₁ + a₀) dan 3 | 9a₀, maka menurut teorema 2.9, 3 | a₁ + a₀

Contoh 3.3

Diketahui t = (a₄a₃a₂a₁a₀) = a₄.10⁴ + a₃.10³+ a₂.10²+ a₁.10 + 4₀ dan 11 | t

Tunjukkan bahwa t | a₀ – a₁ + a₂ – a₃ - a₃ + a₄

Jawab:

t = a₄.10⁴ + a₃.10³ + a₂.10² + a₁.10 + a₀

= a₀ + a₁(11 – 1) + a₂ + a₁(99 + 1) + a₃ (1001 – 1) + a₄ (9999 + 1)

= (11a₁ + 99a₂ + 1001a₃ + 9999a₄) + (a₀-a₁+ a₂ -a₃+ a₄)

t = 11(a₁ + 9a₂+ 91a₃ + 909a₄) + (a₀-a₁+ a₂ -a₃+ a₄)

Karena 11 | t, yaitu 11 | 11(a₁ + 9a₂ + 91a₃+ 909a₄) + (a₀-a₁+ a₂ -a₃+ a₄) dan 11 | 11 (a₁ + 9a₂ + 91a₃+ 909a₄), maka menurut teorema 2.9, 11 | (a₀-a₁+ a₂ -a₃+ a₄)

Contoh 3.4

Menurut teorema algoritma pembagian, nyatakan sebagai q = rp + s, 0 ≤ s < p, jika:

a. p = 7 dan q = - 100

b. p = 12 dan q = - 150

Jawab:

a. -100 = (-15)(7) + 5, 0 £ 5 < 7

b. -150 = (-13)(12) + 6, 0 £ 6 < 12

Teorema algoritma pembagian dapat digunakan untuk memilahkan atau memisahkan himpunan bilangan bulat menjadi n himpunan bagian yang saling lepas (disjoint) dengan n Î {2, 3, 4,…}

Jika p = 2 dan q adalah sebarang bilangan bulat, maka menurut teorema algoritma pembagian, q dapat dinaytakan sebagai:

q = 2p + s, 0 ≤ s < 2

Karena r Î Z dan 0 ≤ r < 2, maka kemungkinan nilai-nilai s adalah s = 0 dan s = 1

untuk s = 0, q = 2p + s = 2p + 0 = 2p

untuk s = 1, q = 2p + s = 2p + 1

q = 2p dengan p Î Z disebut bilangan bulat genap (even integer) dan q = 2p + 1 dengan p Î Z disebut bilangan bulat ganjil atau gasal (odd integer). Dengan demikian himpunan bilangan bulat dapat dipisahkan menjadi dua himpunan bagian yang lepas, yaitu himpunan bilangan bulat genap dan himpunan bilangan bulat ganjil. Dengan kata lain, setiap bilangan bulat selalu dapat dinyatakan sebagai salah satu dari:

q = 2p atau q = 2p + 1, p Î Z

Dengan jalan lain yang sama, setiap bilangan bulat selalu dapat dinyatakan sebagai:

q = 3p, q = 3p + 1, q = 3p + 2, p Î Z

q = 4p, q = 4p + 1, q = 4p + 2, q = 4p + 3 , p Î Z

q = 5p, q = 5p + 1, q = 4p + 2, q = 5p + 3 , q = 5p + 4, p Î Z

dan seterusnya.

Contoh 3.5

Buktikan: 2 | n³ – n untuk sebarang n Î Z

Bukti:

Menurut teorema 2.10 (algoritma pembagian), setiap bilangan bulat n dapat dinyatakan sebagai n = 2p atau n = 2p + 1

Untuk n = 2p, dapat ditentukan:

n³ – n = n (n² -1)

= n (n -1) (n +1)

= 2p (2p -1) (2p +1)

Jadi 2 | n³ – n

Untuk n = 2p + 1, dapat ditentukan

n³ – n = n (n² -1)

= n (n -1) (n +1)

= (2p +1) (2p +1 - 1) (2p +1 + 1)

= 2p(2p + 1)(2p + 2)

Jadi 2 | n³ – n

Dengan demikian 2 | n³ – n untuk sekarang n Î Z

Selanjutnya, marilah kita lihat cara mengganti suatu bilangan dalam basis 10 menjadi basis yang lain dengan menggunakan teorema yang dibuktikan dengan menggunakan teorema algoritma pembagian.

Teorema 3.11

Jika q Î z dan q > 1, maka setiap n Î Z⁺ dapat dinyatakan secara tunggal dalam bentuk n = p_kq^k + p_k-1q^k-1+ ….. + p₂q² + p₁q¹+ p₀q⁰

yang mana k Î Z, k ≥ 0, p_t Î Z, 0 £ p_t < q – 1, t = 0, 1,…, k dan p_k ≠ 0

Bukti:

Karena q Î Z dan q > 1, maka q > 0, sehingga menurut teorema algoritma pembagian, hubungan antara n dan q adalah :

n = qr₀ + p₀, 0 £ p₀ < q (0 £ p₀ £ q -1)

Jika r₀ ≠ 0, maka hubungan antara r₀ dan q menurut teorema algoritma pembagian adalah:

r₀ = qr₁ + p₁, 0 ≤ p₁ ≤ q (0 ≤ p₁ ≤ q – 1)

Jika langkah serupa dikerjakan, maka diperoleh:

r₁ = qr₂ + p₂, 0 ≤ p₂ ≤ q (0 ≤ p₂ ≤ q – 1)

r₂ = qr₃ + p₃, 0 ≤ p₃ ≤ q (0 ≤ p₃ ≤ q – 1)

r_k-2 = qr_k-1 + p_k-1, 0 ≤ p_k-1 < q (0 ≤ p_k-1 ≤ q – 1)

r_k-1 = qr_k-1 + p_k-2, 0 ≤ p_k-2 < q (0 ≤ p_k ≤ q – 1)

Ambil r_k = 0, maka barisan r₀, r₁,…, r_k merupakan barisan bilangan bulat tidak negatif yang menurun, paling banyak mempunyai suku-suku bernilai nol (yaitu r_k), dan k suku yang positif (yaitu r₀,r₁,…, r_k-1).

Dari hubungan antara n, q, dan r_i (i = 0,1, 2,…, k) diatas dapat ditentukan bahwa:

n = qr₀ + p₀

= q(r₁ + p₁) + p₀ = q²r₁ + qp₁ + p₀

= q²(qr₂ + p₂) + qp₁ + p₀ = q³r₂ + q²p₂ + qp₁ + p₀

= ….

= q^k-1r_k-2 + q^k-2p_k-2 + q^k-3p_k-3 + …. + qp₁ + p₀

= q^k-1(qr^k-1 + p_k-1) + q^k-2p_k-2+ q^k-3p_k-3+ … + qp₁ + p₀

= q^kr_k-1 + q^k-1p_k-1+ q^k-2p_k-2+ q^k-3p_k-3+ … + qp₁ + p₀

= q^k(qr_k + p_k) + q^k-1p_k-1+ q^k-2p_k-2+ q^k-3p_k-3+ … + qp₁ + p₀

n = q^k+1r_k + q^kp_k+ q^k-1p_k-1+ q^k-2p_k-2+ q^k-3p_k-3+… + qp₁ + p₀

Karena r_k = 0, maka :

n = q^kp_k + q^k-1p_k-1+ q^k-2p_k-2+ q^k-3p_k-3+… + qp₁ + p₀

n = p_kq^k+ p_k-1q^k-1+ p_k-2q^k-2+p_k-3q^k-3 +… + qp₁ + p₀

n = (p_kp_k-1p_k-2p_k-3… p₁ + p₀)_q

Ini berarti bilangan asli n yang ditulis dalam lambang bilangan basis 10, dapat diubah menjadi lambang bilangan basis q > 1

Agar langkah-langkah dalam pembuktian teorema 2.10 dapat dipahami dengan sebaik-baiknya, marilah kita lihat suatu peragaan berikut ini.

Ambil n = 985 dan q = 6

985 = 6.164 + 1 (n = qr₀ + p₀, r₀ = 164, p₀ = 1)

164 = 6.27 + 2 (r₀ = qr₁ + p₁, r₁ = 27, p₁ = 2)

27 = 6.4 + 3 (r₁ = qr₂ + p₂, r₂ = 4, p₂ = 3)

4 = 6.0 + 4 (r₂ = qr₃ + p₃, r₃ = 0, p₃ = 4)

Dengan demikian dapat ditentukan bahwa:

985 = 6.164 + 1

= 6(6.27 + 2) + 1 = 6².27 + 6.2 + 1

= 6²(6.4 + 3) + 6.2 + 1 = 6³.4 + 6².3 + 6.2 + 1

Jadi: (985)₁₀ = (4321)₆

Perhatikan pola yang terdapat pada lambang bilangan basis 6 yang dicari. Angka-angka pada lambang bilangan basis 6 yang dicari merupakan sisa dari masing-masing algoritma pembagian.

Contoh 3.6.

Tuliskan (985)₁₀ dalam lambang bilangan basis 4 dan basis 3.

Jawab:

985 = 4.246 + 1

246 = 4.61 + 2

61 = 4.15 + 1

15 = 4.3 + 3

3 = 4.0 + 3

(985)₁₀ = (33121)₄

Pemeriksaan:

(33121)₄ = 3.4⁴ + 3.4³+ 1.4²+ 2.4 + 1

= 768 + 192+ 16+ 8 + 1

= 985

985 = 3.328 + 1

385 = 3.109 + 1

109 = 3.36 + 1

36 = 3.12 + 0

12 = 3.4 + 0

4 = 3.1 + 1

1 = 3.0 + 1

(985)₁₀ = (1100111)₃

Pemeriksaan:

(1100111)₃ = 1 . 3⁶ + 1 . 3⁵+ 0 . 3⁴+ 0 . 3³+ 1 . 3²+ 1 . 3 + 1

= 729 + 243 + 0 + 0 + 9 + 3 + 1 = 985

Tugas dan Latihan

Tugas

Carilah suatu sumber pustaka yang membicarakan tentang pembagian oleh 1001 dengan menggunakan cara pencoretan (scratch method). Ambil suatu bilangan, lakukan pembagian bilangan itu oleh 1001 dengan cara biasa dan jelaskan bagaimana proses pembagian itu dapat diganti dengan cara pecoretan untuk memperoleh sisia pembagian.

Berikan satu contoh pembagian suatu bilangan oleh 1001 dengan menggunakan cara pencoretan. Jelaskan manfaat dari cara pencoretan terhadap pembagian bilangan 7, 11 dan 13.

Latihan

1. Buktikan: jika a, b, c Î z , a | b dan a | c, maka a | b + c

2. Nyatakan q dalam bentuk q = rp + s, 0 £ s < p, jika :

q = 79 dan p = 8

q = 203 dan p = 13

q = -110 dan p = 7

q = -156 dan p = 8

3. Buktikan ketunggalan dari r dan s pada teorema algoritma pembagian

4. Diketahui: t = (a₄a₅a₃a₂a₁a₀) dan 7 | t

Tunjukkan bahwa 7 | (a₀ + 3a₁ + 2a₂) – (a₃ + 3a₄ + 2a₅)

5. Buktikan: 3 | n³-n untuk setiap n Î Z

6. Nyatakan (475)₁₀ dalam lambang bilangan basis 7 dan basis 5

BAB IV

FAKTOR PERSEKUTUAN TERBESAR (FPB)

DAN

KELIPATAN PERSEKUTUAN TERKECIL (KPK)

Uraian

Sebelum kita bahas tentang faktor (pembagi) persekutuan terbesar, marilah kita lihat beberapa peragaan berikut:

Perhatikan dua bilangan a = 6 dan b = 8.

Jika A adalah himpunan semua faktor dari a, dan B adalah himpunan semua faktor dari b, serta C adalah himpunan semua faktor persekutuan dari a dan b, maka:

A = {-6, -3, -2, -1, 1, 2, 3, 6}

B = {-8, -4, -2, -1, 1, 2, 4, 8}

C = A Ç B = {-2, -1, 1, 2}

Unsur (anggota, elemen) dari C yang terbesar adalah 2

2 merupakan faktor persekutuan yang terbesar dari a = 6 dan b = 8

2 juga merupakan bilangan bulat positif terbesar yang membagi a = 6 dan b = 8

Sekarang bagaimana kalau diambil a = -6 dan b = 8

A = {-6, -3, -2, -1, 1, 2, 3, 6}

B = {-8, -4, -2, -1, 1, 2, 4, 8}

C = A Ç B = {-2, -1, 1, 2}

Unsur dari C yang terbesar adalah 2.

2 merupakan faktor persekutuan yang terbesar dari a = -6 dan b = 8

2 juga merupakan bilangan bulat positif terbesar yang membagi a = -6 dan b = 8

Dengan jalan yang sama, jika diambil a = -6 dan b = -8, maka juga akan diperoleh faktor persekutuan terbesar dari a dan b adalah 2.

Jika untuk menyatakan faktor persekutuan terbesar dari a dan b digunakan lambang

(a, b), maka dapat ditentukan bahwa:

(6, 8) = 2

(-6, 8) = 2

(-6, -8) = 2

Ternyata, faktor persekutuan terbesar dari dua bilangan bulat a dan b, apapun tanda masing-masing, selalu diperoleh nilai yang bertanda positif. Bagaimana keadaan faktor persekutuan terbesar ini jika a atau b (tidak keduanya) bernilai nol?

Ambil a = 0 dan b = 6

A = himpunan semua faktor a = 0

= { …, -7, -6, -5, -4, -3, -2, -1, 1, 2, 3, 4, 5, 6, 7, …}

B = himpunan semua faktor b = 6

= {-6, -3, -2, -1, 1, 2, 3, 6}

C = A Ç B

= {-6, -3, -2, -1, 1, 2, 3, 6}

Unsur yang terbesar dari C adalah 6, berarti (a, b) = (0, 6) = 6

Untuk a = 0 dan b = 0, perhatikan bahwa:

A = {…, -4, -3, -2, -1, 1, 2, 3, 4, …}

B = {…, -4, -3, -2, -1, 1, 2, 3, 4, …}

C = {…, -4, -3, -2, -1, 1, 2, 3, 4, …}

Sehingga tidak mungkin menentukan unsur yang terbesar dari C, atau faktor persekutuan terbesar dari a = 0 dan b = 0 tidak ada.

Definisi 4.1

Ditentukan x, y Î Z, x dan y keduanya bersama-sama bernilai 0. p Î Z disebut pembagi (faktor) persekutuan (common divisor, common factor) dari x dan y jika p ç x (p membagi x) dan p ç y (p membagi y). p Î Z disebut pembagi (faktor) persekutuan terbesar (gcd = greatest common divisor, gcf = greatest common factor) dari x dan y jika p adalah bilangan bulat positif terbesar yang membagi x (yaitu p çx) dan membagi y (yaitu p ç y).

Notasi:

d = (x, y) dibaca d adalah faktor (pembagi) pesekutuan terbesar dari x dan y

d = (x₁, x₂, …, x_n) dibaca d adalah faktor (pembagi) persekutuan terbesar dari x₁, x₂, …, x_n

Perlu diperhatikan bahwa d = (a, b) didefinisikan untuk setiap pasang bilangan bulat a, b Î Z kecuali a = 0 dan b = 0

Demikian pula, perlu dipahami bahwa (a, b) selalu bernilai bilangan bulat positif, yaitu d Î Z dan d > 0 (atau d ³ 1).

Contoh 4.1

1. Himpunan semua faktor 16 adalah: A = {-16, -6, -4, -2, -1, 1, 2, 3, 4, 8, 16}

Himpunan semua faktor 24 adalah: B = {-24, -12, -8, -6, -4, -3, -2, -1, 1, 2, 3, 4, 6, 8, 12, 24}

Himpunan semua faktor persekutuan 16 dan 24 adalah: C = {-8, -4, -2, -1, 1, 2, 4, 8}

Karena unsur C yang terbesar adalah 8, maka (16, 24) = 8

Cobalah cari (-16, 24), (16, -24), (-16, -24), (24, -16), dan (-24, 16)

2. Himpunan semua faktor 12 adalah {-12, -6, -4, -3, -2, -1, 1, 2, 3, 4, 6, 12}

Himpunan semua faktor 18 adalah {-18, -9, -6, -3, -2, -1, 1, 2, 3, 6, 9, 18}

Himpunan semua faktor persekutuan 12 dan 18 adalah {-6, -3, -2, -1, 1, 2, 3, 6}

Jadi: (16, 24) = 8

3. Perhatikan:

(6, 9) = 3 dan 3 = (2) (6) + (-1) (9)

(16, 40) = 8 dan 8 = (3) (16) + (-1)(40)

(60, 105) = 15 dan 15 = (2) (60) + (-1)(105)

Dari ketiga kasus di atas nampak adanya pola bahwa (p,q) dapat dinyatakan sebagai kombinasi linier px + qy dengan x, y Î Z

4. Perhatikan bahwa (6, 9) = 3

Sekarang dibentuk kombinasi linear px + qy dengan x, y Î Z

Nilai-nilai 6p + 9q adalah sebagai berikut:

p = 0 dan q = 0 ® 6p + 9q = 0

p = 0 dan q = 1 ® 6p + 9q = 9

p = 1 dan q = 0 ® 6p + 9q = 6

p = 1 dan q = -1 ® 6p + 9q = -3

p = -1 dan q = 1 ® 6p + 9q = 3

p = -1 dan q = 2 ® 6p + 9q = 12

p = 2 dan q = -1 ® 6p + 9q = 3

p = 1 dan q = -2 ® 6p + 9q = -12

p = 0 dan q = -1 ® 6p + 9q = -9

p = 2 dan q = -2 ® 6p + 9q = -6

Nilai-nilai itu dapat disusun menjadi barisan:

…, -12, -9, -6, -3, 0, 3, 6, 9, 12, …

Ambil S = {3, 6, 9, 12, …}, yaitu himpunan yang unsur-unsurnya adalah suku-suku barisan yang positif, yaitu:

S = {6p + 9q ç6p + 9q > 0 dan p, q Î Z}

Karena S Ì N dan N adalah himpunan terurut rapi, maka S mempunyai unsur terkecil, yaitu 3.

Karena 3 Î S, maka 3 = 6p + 9q dengan p = 2 dan q = -1, atau p = -1 dan q = 1

Jelas bahwa 3 ç6 dan 3 ç9

Teorema 4.1

Jika d = (x, y), maka d adalah bilangan bulat posisitif terkecil yang mempunyai bentuk px + qy untuk suatu m, n Î Z, yaitu d dapat dinyatakan sebagai kombinasi linear dari x dan y.

Bukti:

Dibentuk kombinasi linear (px + qy) dengan p, q Î Z

Barisan bilangan (px + qy) memuat bilangan-bilangan yang bernilai negatif, bilangan nol (untuk p = 0 dan q = 0), dan bilangan-bilangan yang yang bernilai positif.

Ambil S = {px + qy çpx + qy > 0 dan p,q Î Z }, maka dapat ditentukan bahwa S Ì N. Karena S Ì N dan N merupakan himpunan yang terurut rapi, maka S mempunyai unsur terkecil, sebutlah dengan t.

Karena t Î S, maka tentu ada p = m dan q = n sehingga t = mx + ny. Selanjutnya dapat dibuktikan bahwa t çx dan t çy.

Untuk membuktikan t çx digunakan bukti tidak langsung.

Misalkan t Q x, maka menurut teorema 3.9, ada r, s Î Z sehingga

x = tr + s, 0 < s < t

x = tr + s

s = x – tr

= x – (mx + ny) r

= (1 – mr)x + (-ny)r

s = ix + jy dengan i = 1 – mr Î Z dan j = -nq Î Z

Jadi: s = ix + jy Î S dengan s < t

Dengan anggapan t Q x ternyata menghasilkan kontradiksi karena t adalah unsure terkecil S, dengan demikian anggapan t Q x adalah salah, berarti t çx

Dengan jalan yang sama dapat ditunjukkan bahwa t çy

Dari t çx dan t çy berarti t adalah faktor persekutuan dari x dan y.

Karena t adalah faktor persekutuan dari x dan y, dan d adalah faktor persekutuan terbesar dari x dan y, maka t ≤ d

Selanjutnya akan dibuktikan bahwa d ≤ t

d = (x, y), maka menurut definisi 3.3, d çx dan d çy

d çx dan d çy, maka menurut definisi 3.1, x = dv untuk suatu v Î Z dan y = dw untuk suatu w Î Z.

t = mx + ny

= m(dv) + n(dw)

t = d(mv + nw), berarti d çt

Karena d ç t, d > 0, dan t > 0, maka sesuai dengan teorema 3.6, d ≤ t

Karena t ≤ d dan d ≤ t, maka d = t

Jadi: d adalah bilangan bulat positif terkecil yang mempunyai bentuk mx + ny dengan m, n Î Z.

Teorema 4.2

Jika k Î N, maka k(x, y) = (kx, ky)

Bukti:

Misalkan d = (x, y) dan e = (kx, ky), maka menurut teorema 3.11, d = rx + sy dan e = mkx + nky untuk suatu r, s, m, n Î Z. d = rx + sy, maka kd = krx + ksy. Karena d = (x, y), maka menurut definisi 2.1, d çx dan d çy, dan menurut teorema 3.8, kd çkx dan kd çky

Menurut teorema 3.1, kd çkx dan kd çky berakibat kd çmkx dan kd çnky, dan menurut teorema 2.4, kd çmkx + nky, atau kd çe.

Jadi: k(x, y) ç(kx, ky).

Selanjutnya, karena e = (kx, ky), maka menurut difinisi 3.3, e çkx dan e çky, dan menurut teorema 2.8, e çkrx dan e çksy. Menurut teorema 3.4, e çkrx dan e çkry berakibat e çkrx + ksy, atau e çkhd.

Jadi: (kx, ky) çk(x, y)

Karena k(x,y) > 0, (kx,ky) > 0 , k(x, y) ç(kx, ky), dan (kx, ky) çk(x, y), maka menurut teorema 3.7, k(x, y) = (kx, ky)

Contoh 4.2

(60, 102) = (6.10, 6.17) = 6(10, 17) = 6.1 = 6

(108, 207) = (9.12, 9.23) = 9(12, 23) = 9.1 = 9

Teorema 4.3

Jika x, y Î Z dan d = (x, y), maka = 1

Bukti:

Misalkan x, y Î Z dan (x, y) = d

Kita akan tunjukkan bahwa dan tidak mempunyai pembagi persekutuan yang positif kecuali 1.

Misal e adalah suatu bilangan bulat positif yang membagi dan membagi , yaitu e ç dan e ç ,

menurut def 3.1, = ke dan = te untuk suatu k, t Î Z. Dengan demikian x = dek dan y = det, berarti de adalah faktor pesekutuan dari x dan y. Karena de adalah faktor persekutuan dari x dan y, dan d adalah faktor persekutuan terbesar dari x dan y, maka de ≤ d. Akibatnya e haruslah sama dengan 1

Jadi: = 1

Teorema 4.4

Jika p, q, r Î Z, p çqr, dan (p, q) = 1, maka p çr

Bukti:

Diketahui (p, q) = 1, maka menurut teorema 3.11, 1 adalah bilangan bulat positif terkecil yang dapat dinyatakan sebagai px + qy dengan x, y Î Z , yaitu px + qy = 1

Karena px + qy = 1, maka rpx + rqy = r, atau prx + qry = r.

Menurut teo 3.1, karena pçqr, maka p çqry untuk semua y Î Z. Selanjutnya, karena p çprx dan p çqry, maka menurut teorema 3.4, p çprx + qry. Jadi: p çr.

Teorema 4.5

Jika (x, t) = 1 dan (y, t) = 1, maka (xy, t) = 1

Bukti:

Diketahui (x, t) = 1 dan (y, t) = 1, maka menurut teorema 3.11, ada p, q, r, s Î Z sehingga px + qt = 1 dan ry + st = 1.

Dari 1 = px + qt dan 1 = ry + st dapat ditentukan bahwa

1.1 = (px + qt)(ry + st)

1 = prxy + pstx + qrty + qst²

1 = (pr)(xy) + (psx + qry + qst)t

Dengan demikian, sesuai teorema 3.11, karena 1 merupakan bilangan bulat positif terkecil yang merupakan kombinasi linear dari xy dan t, maka:

(xy, t) = 1

Teorema 4.6

Ditentukan x, y Î Z

d = (x, y) jika dan hanya jika d > 0, d çx, d çy, dan f çd untuk setiap pembagi persekutuan f dari x dan y

Bukti:

Kita buktikan jika d = (x, y), maka d > 0, d çx, d çy, dan f çd

d = (x, y), maka menurut definisi 3.3, d adalah bilangan bulat positif (d > 0) terbesar yang membagi x (d çx) dan membagi y (d çy)

Selanjutnya, menurut teorema 2.11, jika d = (x, y), maka d = mx + ny untuk suatu m, n Î Z

Misalkan f adalah sebarang pembagi persekutuan dari x dan y, maka f çx dan f çy, dan menurut teorema 3.1, f çmx dan f çny untuk sebarang m, n Î Z

Menurut teorema 3.4, f çmx dan f çny berakibat f çmx + ny.

Karena f çmx + ny dan d = mx + ny, maka f çd.

Kita buktikan jika d > 0, d çx, d çy, dan f çd untuk sebarang pembagi persekutuan f dari x dan y, maka d = (x, y)

Karena d > 0 , d çx dan d çy, maka d adalah faktor persekutuan dari x dan y. Selanjutnya, karena f adalah sebarang faktor persekutuan dari x dan y dan f çd, maka f ≤ d, d dan f adalah faktor-faktor persekutuan dari x dan y, f adalah sebarang faktor persekutuan dari x dan y, dan f ≤ d, maka d adalah faktor persekutuan yang terbesar dari x dan y. Jadi: d = (x, y).

Contoh 4.2

Faktor-faktor persekutuan 4 dan 6 adalah -1, 1, -2, dan 2. Faktor persekutuan terbesar 4 dan 6 adalah 2. Perhatikan bahwa sebarang faktor persekutuan 4 dan 6 membagi faktor persekutuan terbesar 4 dan 6, yaitu: -1 ç2, 1 ç2, -2 ç2, dan 2 ç2.

Contoh 4.3

(18, 24) = 6

Faktor-faktor persekutuan 18 dan 24 adalah -1, 1, -2, 2, -3, 3, -6, dan 6.

Perhatikan bahwa sebarang faktor persekutuan 18 dan 24 membagi 6, yaitu ± 1 ç6,

± 2 ç6, ± 3 ç6, dan ± 6 ç6.

Teorema 4.7

(x, y) = (y, x) = (x, -y) = (-x , y) = (-x, -y) untuk sebarang x, y Î Z.

Buktikan!

Teorema 4.8

a. (x, y) = (x, y + ax) untuk sebarang a Î Z

b. (x, y) = (x + yb, y) untuk sebarang b Î Z

Bukti:

a. Sesuai definisi 3.3, (x, y) > 0 dan (x, y + ax) > 0

Karena (x, y) > 0 dan (x, y + ax) > 0, maka untuk membuktikan (x, y) = (x, y + ax), sesuai dengan teorema 3.7 kita harus membuktikan bahwa (x, y) ç(x, y + ax) dan (x, y + ax ç (x, y). Kita akan membuktikan (x, y) ç(x, y + ax)

Sesuai definisi 3.3, (x, y) çx dan (x, y) çy

Menurut teorema 3.1, karena (x, y) çx, maka (x, y) çaxuntuk semua a Î Z. Selanjutnya, sesuai dengan teorema 3.4, karena (x, y) çax dan (x, y) çy, maka

(x, y) çy + ax

(x, y) çx dan (x, y) çy + ax, maka menurut definisi 3.3 (x, y) adalah faktor persekutuan dari x dan y + ax, dan akibatnya, sesuai dengan teorema 4.6,

(x, y) membagi (x,y + ax)

Jadi: (x, y) ç(x, y + ax)

Kita akan membuktikan (x, y + ax) ç(x, y)

Sesuai def 3.3, (x, y + ax) çx, sehingga menurut teorema 3.1, (x, y + ax) çax sehingga menurut teo 3.1, (x, y + ax) çax untuk semua a ÎZ; demikian pula, sesuai def 3.3, (x, y + ax) çy + ax.

Selanjutnya, sesuai teorema 3.9, karena: (x, y + ax çax dan (x, y + ax) çy + ax maka (x, y + ax) çy.

Karena (x, y + ax) çx dan (x, y + ax) çy, maka sesuai def 3.3, (x, y + ax) merupakan faktor pesekutuan dari x dan y, dan sesuai teorema 4.6 setiap faktor persekutuan x dan y tentu membagi (x, y)

Jadi: (x, y + ax) ç(x, y).

Karena (x, y) > 0, (x, y + ax) > 0, (x, y) ç(x, y + ax), dan (x, y + ax) ç(x, y), maka menurut teorema 2.7:

(x, y) = (x, y + ax)

b. Buktikan

Contoh 4.7.

(6, 9) = (6,9 + 7.6) = (6,51)

(12,18) = (12,18 + 5.12) = (12, 78)

(40,16) = (40,16 + 9.40) = (40, 376)

(40,16) = (40 + 5.16,16) = (120,16)

(12,18) = (12 + 7.18,18) = (138,18)

(36,15) = (6 + 2.15,15) = (6,15) = (6,3 + 2.6) = (6,3) = 3(2,1) = 3.1 = 3

(84,175) = (84,7 + 2.84) = (84,7) = 7(12,1) = 7.1 = 7

Contoh 4.8

Ditentukan s₀ = 48, s₁ = 27, s₂ = 21 s₃ = 6, s₄ = 3, dan s₅ = 0

Maka menurut teorema 3.9 (algoritma pembagian),kita dapat melakukan langkah-langkah berikut:

48 = 1.27 + 21, 0 ≤ 21 < 27, 0 ≤ s₂ < s₁

27 = 1.21 + 6, 0 ≤ 6 < 21, 0 ≤ s₃ < s₂

21 = 3.6 + 3, 0 ≤ 3 < 6, 0 ≤ s₄ < s₃

6 = 2.3 + 0 s₅ = 0

Selanjutnya, menurut teorema 3.11, kita dapat mencari (s, s) = (48, 27):

(s₀, s₁) = (48, 27)

= (21 + 1.27,27) = (21, 27)

= (s₂, s₁)

= (21,6 + 1.21) = (21, 6)

= (s₂, s₃)

= (3 + 3.6,6) = (3, 6)

= (s₄, s₃)

= (3,3 + 1.3) = (3,3) = (3,0 + 1,3)

= (3,0)

= (s₄ + s₅)

= s₅

Perhatikan bahwa secara bertahap dapat ditentukan:

(s₀, s₁) = (s₂, s₁) = (s₂, s₃) = (s₄, s₃) = (s₄, s₄) = s₄

Contoh. di atas memberi gambaran tentang langkah-langkah yang jelas dan terhingga untuk memperoleh faktor persekutuan terbesar dua bilangan secara sistematis. Marilah sekarang kita lihat suatu cara yang sistematis, dan disebut algoritma, untuk mencari faktor persekutuan terbesar dari dua bilangan bulat positif.

Algoritma ini disebut algoritma Euclides, dan istilah ini digunakan setelah Euclid, matematisi Yunani (Greek, 350 S.M.), menjelaskan algoritma ini dalam bukunya The Elements (Rosen K., 1993: 80).

Teorema 4.9 Algoritma Euclides

Ditentukan s₀, s₁ Î Z, s₀ ³ s₁, > 0

Jika algoritma pembagian digunakan secara berturut-turut untuk memperoleh

s_t = s_t+1 k_t+1 + s_t+2, 0 ≤ s_t+2 ≤ s_t+1, t = 0, 1, 2, …, n – 2 dan s_n+1 = 0

maka (s₀, s₁) = s_n, sisa yang tidak nol dalam algoritma pembagian

Bukti:

Karena s₀, s₁ Î Z, s₀ ³ s₁ > 0, maka dengan menggunakan algoritma pembagian secara berturut-turut akan diperoleh:

s₀ = s₁ k₁ + s₂, 0 ≤ s₂ < s₁

s₁ = s₂ k₂ + s₃, 0 ≤ s₃ < s₂

s_t-2 = s_t-1k_t-1 + s_t , 0 ≤ s_t < s_t-1

s_n-3 = S_n-2 k_n-2 + s_n-1, 0 ≤ s_n-1 < s_n-2

s_n-2 = s_n-1 k_n-1 + s_n , 0 ≤ s_n < s_n-1

s_n-1 = s_n k_n + s_n-1 , s_n+1 = 0

maka sesuai teorema 4.8:

(s₀, s₁) = (s₁ + s₂, s₁)

= (s₂, s₁)

= (s₂, s_2.2 + s₃)

= (s₂, s₃)

= …

= (s_n-3, s_n-2)

= (s_n-2, s_n-1)

= (s_n-1, s_n)

= (s_n, 0)

(s₀, s₁) = s_n

Contoh 4.9

Carilah (963, 657) dengan menggunakan algoritma Euclides

Jawab: 963 = 1.657 + 306, 0 ≤ 306 < 657

657 = 2.306 + 45, 0 ≤ 45 < 306

306 = 6.45 + 36, 0 ≤ 36 < 45

45 = 1.36 + 9, 0 ≤ 9 < 36

36 = 4.9 + 0

Jadi: (963, 657) = 9

Menurut teorema 4.1, jika d = (x, y), maka d dapat dinyatakan sebagai kombinasi linear dari x dan y. Algoritma Euclides dapat digunakan untuk mencari kombinasi linear d dari x dan y.

Dalam kaitannya dengan algoritma Euclides, jika d = (s₀, s₁), maka dapat ditentukan bahwa d = ms₀ + ns₁:

s_n-2 = s_n-1 k_n-1 + s_n, maka s_n = s_n-2 - s_n-1 k_n-1

s_n-3 = s_n-2 k_n-2 + s_n-1, maka s_n-1 = s_n-3 - s_n-2 k_n-2

s_n-4 = s_n-3 k_n-3 + s_n-2, maka s_n-2 = s_n-4 - s_n-3 k_n-3

s₁ = s₂k₂ + s₃, maka s₃ = s₁ – s₂ k₂

s₀ = s₁k₁ + s₂, maka s₂ = s₀ – s₁ k₁

Dengan demikian:

s_n = s_n-2 – s_n-1 k_n-1

= s_n-2 – (s_n-3 – s_n-2 k_n-2)k_n-1

= s_n-2 (1 + k_n-2 k_n-1) – s_n-3

= (s_n-4 – s_n-3 k_n-3)(1 + k_n-2 k_n-1) – s_n-3

= s_n-4 (1 + k_n-2 k_n-1) + s_n-3{k_n-3(1 + k_n-2 k_n-1)}

Jika proses serupa diteruskan dengan substitusi berturut-turut:

s_n-3, s_n-4, … , s₃, s₂

maka akan diperoleh bentuk:

(s₀, s₁) = s_n

(s₀, s₁) = s₀m + s₁n = ms₀ + ns₁

Ini berarti bahwa (s₀, s₁) dapat dinyatakan sebagai kombinasi linear dari s₀ dan s₁

Contoh 4.10

Nyatakan (205, 75) sebagai kombinasi linear dari 205 dan 75

Jawab: 205 = 2.75 + 55 , 55 = 205 – 2. 75

75 = 1.55 + 20 , 20 = 75 – 1.55

55 = 2.20 + 15 , 15 = 55 – 2.20

20 = 1.15 + 5 , 5 = 20 – 1.15

15 = 3.5 + 0

(205, 75) = 5

Dengan demikian dapat ditentukan:

(205, 75) = 5

= 20 – 1.15 = 20 – 1 . (55 – 2.20)

= 3.20 – 1.55 = 3.(75 – 1.55) – 1.55

= 3.75 – (4) . 55 = 3.75 – 4 (205 – 2.75)

(205,75) = 11.75 + (-4) . 205

Contoh 4.11

Carilah nilai-nilai m, n Î Z yang memenuhi hubungan

(7897, 4399) = m(7897) + n (4399)

Jawab: 7897 = 1.4399 + 3498 , 3498 = 7897 – 1.4399

4399 = 1.3498 + 901 , 901 = 4399 – 1.3498

3498 = 3.901 + 795 , 795 = 3498 – 3.901

901 = 1.795 + 106 , 106 = 901 – 1.795

795 = 7.106 + 53 , 53 = 795 – 7.106

106 = 2.53 + 0

Dengan demikian dapat ditentukan:

(7897, 4399) = 53

= 795 – 7.106 = 795 – 7. (901 – 1.795)

= 8.795 – 7.901 = 8(3498 – 3.901) – 7.901

= 8.3498 – 31.901 = 8.3498 – 31(4399 – 1.3498)

= 39.3498 – 31.4399 = 39.(7897 – 1.4399) – 31.4399

(7897, 4399) = 39.7897 + (-70) . 4399

Jadi: m = 7897 dan n = -70

Cara untuk menyatakan (p, q) sebagai kombinasi linear dari p dan q memerlukan pemrosesan yang panjang karena perlu kerja berdasarkan langkah-langkah algoritma Euclides, dan dilanjutkan kerja mundur berdasarkan modifikasi dari setiap langkah dalam algoritma Euclides.

Terdapat cara lain untuk menyatakan (p, q) sebagai kombinasi linear dari p dan q, yang secara langsung dapat menggunakan langkah-langkah algoritma Euclides.

Teorema 4.10

Ditentukan p, q Î N

Maka (p, q) = r_n p + l_nq, n = 0, 1, 2, …, yang mana r_n dan k_n adalah suku ke n dari barisan-barisan yang secara rekursif didefinisikan sebagai:

r₀ = 1, l₀ = 0

r₁ = 0, l₁ = 1

dan

r_i = r_i-2 – k_i-1 r_i – 1

l_i = l_i-2 – k_i-1 l_i-1

untuk i = 2, 3, … , n dengan k_i adalah hasil bagi dalam algoritma Euclides memperoleh (p, q)

Bukti:

Berdasarkan langkah-langkah algoritma Euclides pada teorema 2.20, dipilih p = s₀ dan q = s_1, kemudian kita gunakan cara pembuktian induksi matematika untuk membuktikan (p, q) = s_n= r_np + l_nq

untuk i = 0, p = s₀ = 1.p + 0.q = r₀p + l₀q,

untuk i = 1, q = s₁ = 0 . p + 1 . q = r₁ + l₁ q

Sekarang, anggaplah bahwa:

s_i = r_ip + l_iq, i = 1, 2, …, n – 1

Sesuai dengan keadaan langkah ke n dalam pembuktian teorema 2.20 (algoritma Euclides) dapat ditunjukkan bahwa:

s_n-2 = s_n-1 k_n-1 + s_n , atau s_n = s_n-2 – s_n-1 k_n-1

Dengan demikian, sesuai dengan prinsip induksi matematika:

s_n = s_n-2 – s_n-1 k_n-1

= (r_n-2 p + l_n-2 + q) – (r_n-1 p + l_n-1 q) k_n-1

= (r_n-2 – r_n-1 k_n-1) p + (l_n-2 – l_n-1 k_n-1) q

= (r_n-2 – k_n-1 r_n-1) p + (l_n-2 – k_n-1l_n-1) q

s_n = r_np + l_n q

Contoh 4.12

Carilah (205, 75) dan nyatakan sebagai kombinasi linear dari 205 dan 75.

Jawab: 205 = 2.75 + 55 , k₁ = 2

75 = 1.55 + 20 , k₂ = 1

55 = 2.20 + 15 , k₃ = 2

20 = 1.15 + 5 , k₄ = 1

15 = 3.5 + 0

Jadi: (205, 75) = 5

r_o = 1 l_o = 0

r₁ = 0 l₁ = 1

r₂ = r_o – k₁.r₁ l₂ = l_o – k₁ l₁

= 1 – 2. 0 = 0 – 2.1

= 1 = -2

r₃ = r₁ – k₂ – r₂ l₃ = l₁ - k₂ l₂

= 0 – 1. 1 = 1 – 1 (-2)

= 1 = 3

r₄ = r₂ – k₃ . r₃ l₄ = l₂ – k₃ l₃

= 1 – 2(-1) = -2 – 2 . 3

= 3 = -8

r₅ = r₃ – k₄ r₄ l₅ = l₃ – k₄ l₄

= -1 – 1 (3) = 3 – 1 . (-8)

= -4 = 11

Jadi: (205, 75) = (-4) . 205 + 11.75

Contoh 4.13

Langkah-langkah pada contoh 2.15 memerlukan tempat mencari yang luas dan waktu yang panjang. Untuk menyederhanakan langkah-langkah pencarian, kita dapat mengurangi tempat dan waktu dengan mengoperasikan atau menggunakan tabel. Dengan menggunakan tabel, contoh 2.15 dapat dikerjakan sebagai berikut:

n r l k

1 1 0 2

2 0 1 1

3 1 -2 2

4 -1 3 1

5 3 -8

6 -4 11

jadi: (205, 75) = (-4) . 205 + 11. 75

Contoh 4.14

Carilah m dan n jika (8517, 2669) = m . 8517 + n . 2669

Jawab:

8517 = 3.2669 + 510 , k₁ = 3

2669 = 5.510 + 119 , k₂ = 5

510 = 4.119 + 34 , k₃ = 4

119 = 3 . 34 + 17 , k₄ = 3

34 = 2 . 17 + 0

n r l k

1 1 0 3

2 0 1 5

3 1 -3 4

4 -5 16 3

5 21 -67

6 -68 217

Jadi: (8517, 2669) = (- 68) . 8517 + 217 . 2669

m = -68 dan n = 217

Marilah sekarang kita mempelajari pasangan pasangan pembahasan FPB (faktor Persekutuan ter Besar)yang disebut KPK (Kelipatan Persekutuan ter Kecil). Topik FPB dan KPK merupakan materi pelajaran matematika di sekolah sejak Sekolah Dasar.

Definisi 4.2

Jika x, y Î Z, x ¹ 0, dan y ¹ 0, maka:

a) m disebut kelipatan persekutuan (common multiple) dari x dan y jika x çm

dan y çm

b) m disebut kelipatan persekutuan terkecil (least common multiple, l.c.m) dari x

dan y jika m adalah bilangan bulat positif terkecil sehingga x çm dan y çm.

Notasi:

m = [x, y] dibaca m adalah kelipatan persekutuan terkecil dari x dan y

Dengan jalan yang sama dapat didefinisikan kelipatan persekutuan terkecil dari 3 bilangan, 4 bilangan, …, n bilangan, misalnya:

n = [x, y, z] dibaca n adalah kelipatan persekutuan terkecil dari x, y, dan z.

p = [a, b, c, d] dibaca p adalah kelipatan persekutuan terkecil dari a, b, c, dan d.

Contoh 4.15

a. Carilah [12, 16]

Jawab: Karena [12, 16] bernilai positif, maka [12, 16] dapat dicari dari kelipatan-

persekutuan 12 dan 16 yang positif.

Kelipatan 12 yang positif adalah 12, 24, 36, 48, 60, …

Kelipatan 16 yang positif adalah 16, 32, 48, 64, 80, …

48 adalah kelipatan persekutuan 12 dan 16 sebab 12ç48 dan 16ç48

96 adalah kelipatan persekutuan 12 dan 16 sebab 12ç96 dan 16ç96

Kelipatan-kelipatan persekutuan 12 dan 16 adalah 48, 96, 144, 192, …

Dari barisan bilangan kelipatan persekutuan 12 dan 16, yang terkecil

adalah 48, sehingga [12, 16] = 48

b. Carilah [25, 15]

Jawab: Kelipatan 25 yang positif adalah 25, 50, 75, …

Kelipatan 15 yang positif adalah 15, 30, 45, …

Kelipatan-kelipatan persekutuan 25 dan 15 yang positif adalah 75, 150, 225, …

Kelipatan-kelipatan persekutuan 25 dan 15 yang positif dan terkecil adalah 75,

sehingga [25, 15] = 75

Perhatikan kelipatan-kelipatan persekutuan 4 dan 5 yang positif, yaitu: 20, 40, 60, 80, …

Dan yang terkecil adalah 20, sehingga [4, 5] = 20

Ternyata 20ç20, 20ç40, 20ç60, 20ç80, …, 20çk untuk sebarang kelipatan persekutuan k dari 4 dan 5

Teorema 4.11

Ditentukan x, y Î Z, x ≠ 0, dan y ≠ 0

m = [x, y] jika dan hanya jika x çm, y çm, m > 0, dan untuk sebarang kelipatan persekutuan n dari x dan y berlaku m çn

Bukti:

(→)

Ambil m = [x, y], maka menurut definisi 3.4, x çm, y çm dan m > 0

Misalkan n adalah sebarang kelipatan persekutuan x dan y, maka x çn dan y çn. Harus ditunjukan bahwa m çn. Menurut perbagian algoritma, karena m £ n, maka tentu ada k, s Î Z sehinga n = km + s, 0 £ s < m

Untuk membuktikan m çn, harus ditunjukkan bahwa n = km, atau harus ditunjukkan bahwa s = 0.

Perhatikan bahwa n = km + s, maka s = n – km.

x çm dan y çm, maka x çam dan y çam

x çn dan x çam, maka x çn-am

y çn dan y çam, maka y çn – am

x çn – am dam y çn – am, maka n – am adalah kelipatan persekutuan x dan y.

s = n – km, x çn – km, dan y çn – km, maka x çs dan y çs

x çs dan y çs, maka s kelipatan persekutuan x dan y.

Karena s dan m adalah kelipatan-kelipatan persekutuan x dan y, dan m adalah yang terkecil, serta 0 £ s < m, maka jelas bahwa s = 0, sehingga n = km, atau m çn.

(¬)

Ambil m > 0, x çm, y çm, dan untuk sebarang kelipatan persekutuan n dari x dan y berlaku m çn.

Ini berarti bahwa m adalah suatu kelipatan persekutuan dari x dan y yang membagi semua kelipatan persekutuan dari x dan y yang lain. Jadi m = [x, y]

Teorema 4.12

[mx, my] = m [x, y] untuk sebarang m Î N

Bukti:

Ambil K = [mx, my] dan k = [x, y]

K = [mx, my], maka sesuai definisi 2.4, mx çk dan my çk

k = [x, y], maka sesuai definisi 2.4, x çk dan y çk

x çk, maka menurut teorema 2.8, mx çmk.

y çk, maka menurut teorema 2.8, my çmk

mx ç mk dan my çmk, maka menurut definisi 2.4, mk adalah kelipatan persekutuan dari mx dan my.

Karena K adalah kelipatan persekutuan terkecil dari mx dan my, dan mk adalah kelipatan persekutuan mx dan my, maka menurut teorema 2.22, K ç mk.

Jadi: [mx, my] çm [x, y]

Selanjutnya, karena mx çk dan my ç K, maka sesuai definisi 2.1, K = amx dan

K = bmy untuk suatu a, b Î Z, berarti = ax dan = by, atau x ç dan y ç .

Karena x ç dan y ç , maka menurut definisi 2.4, adalah kelipatan persekutuan x dan y.

Akibatnya, sesuai dengan teorema 2.22, [x, y] membagi , yaitu [x, y] ç .

Karena [x, y] ç , maka menurut teorema 2.8, m [x, y] çm . , atau m [x, y] çK.

Jadi: m [x, y] ç[mx, my]

Akhirnya, karena [mx, my] > 0, m [x, y] > 0, [mx, my] çm [x, y], dan m [x, y] ç[mx, my], maka menurut teorema 2.7, [mx, my] = m [x, y].

Teorema 4.13

Jika x, y Î N dan [x, y] = 1, maka [x, y] = xy

Bukti: [x, y] = 1, maka menurut teorema 4.1, mx + ny = 1 untuk suatu m, n Î Z,

sehingga [x, y] [mx + my] = [x, y], atau [x, y] mx + [x, y] ny = [x, y]

[x, y] adalah kelipatan persekutuan terkecil x dan y, maka sesuai definisi 3.4,

x ç[x, y], y ç[x, y], berarti sesuai dengan teorema 3.8

xy ç[x, y] y dan xy ç[x, y]x. Dengan demikian, sesuai teorema 3.1, xy ç[x, y] ny

dan xy ç[x, y] mx, dan sesuai teorema 3.5, xy ç[x, y] mx + [x, y] ny.

Jadi xy ç[x, y] [x, y] adalah kelipatan persekutuan terkecil x dan y, dan xy adalah kelipatan x dan y, maka menurut teorema 4.11,[x, y] ç xy.

Dari xy ç[x, y] dan [x, y] çxy, maka teorema 3.7, xy = [x, y], atau [x, y] = [x, y]

Contoh 4.16

a. (2, 3) = 1, maka [2, 3] = 2 . 3 = 6

b. (7, 11) = 1, maka [7, 11] = 7 . 11 = 77

c. (16, 13) = 1, maka [16, 13] = 16 . 13 = 208

Teorema 4.14

Jika x, y Î Z, maka (x, y) [x, y] = xy

Bukti:

Ambil d = (x, y), maka sesuai teorema 2.14, = 1

Sesuai teorema 2.24, karena = 1, maka:

akibatnya

= 1 . =

d² = d² .

d . d = xy,

dan sesuai teorema 4.2 serta teorema 4.12, diperoleh

. = xy

(x, y) [x, y] = xy

Contoh 4.17

a. (6, 9) [6, 9] = 6 . 9 = 54

b. (12, 18) = maka 6 [12, 18] = 12.18, sehingga [12, 18] = . 12 . 18 = 36

c. (24, 16) = 8, maka 8 [24, 16] = 24 . 16, sehingga [24, 16] = .24.16 = 48

d. [36, 48] = = = 144

Tugas dan Latihan

Agar Anda lebih memahami dan menguasai materi tentang FPB, KPK, dan Keprimaan, kerjakanlah dengan sungguh-sungguh Tugas dan Latihan berikut.

Tugas

Carilah buku bacaan tentang Teori Bilangan, misalnya Elementary Number Theory and Its Applications yang ditulis oleh Kenneth H. Rosen, dan diterbitkan oleh Addison-Wesley Publishing Company.

1. Jelaskan dan buktikan Teorema Dasar Aritmetika

2. Buktikan [p,q](p,q) = pq dengan menggunakan Teorema Dasar Aritmetika

3. Nyatakan bentuk umum (p,q) dan [p,q] dengan menggunakan pemfaktoran prima, dan berilah

masing-masing dua contoh.

Latihan

1. Nyatakan (2345)₁₀ dalam notasi lambing bilangan

(a) basis 7

(b) basis 8

2. Diketahui p,q Z dan (p,q) = 1

Carilah semua kemugkinan nilai d = (p + q , p – q )

3. Tunjukkan bahwa (3t + 2) dan (5t + 3) adalah relative prima, t {0, 1, 2, 3, …}

4. Carilah m dan n jika :

(a) 67815m + 21480n = (67815,21480)

(b) 30745m + 17446n = (30745,17446)

5. Buktikan : jika (x,y) = 1 dan z x + y, maka (x,z) = (y,z) = 1

6. Buktikan : (r + ts , s) = (r,s)

7. Diketahui : (4,p) = 2 dan (4,q) = 2. Carilah (4,p+q)

8. Diketahui p adalah suatu bilangan prima, (p²,m) p dan (p³,n) = p²

Carilah (p⁴,mn)

9. Carilah (x²,108) jika diketahui (x,18) = 6

Teori Bilangan

Sabtu, 15 November 2014

Bahan Kuliah Teori Bilangan