KATA PENGANTAR Puji syukur penulis panjatkan kepada Alloh SWT atas anugrah yang diberikan sehingga penulisan Buku Diktat yang dilengkapi dengan Rencana Program Kegiatan Pembelajaran Semester (RPKPS) dan Rencana Kegiatan Pembelajaran Mingguan ini dapat terselesaikan dengan baik. Tidak lupa penulis mengucapkan terima kasih kepada Rektor UGM, Kepala P3 UGM, Dekan FMIPA UGM dan Ketua Jurusan Matematika yang telah memberikan kesempatan kepada penulis untuk ikut andil dalam pengembangkan mutu proses pembelajaran, dengan kegiatan ini. Rencana Program Kegiatan Pembelajaran Semester (RPKPS) dan Buku Diktat ini ditulis dengan tujuan agar proses persiapan dan proses pembelajaran dalam bidang Teori Bilangan sebagai dasar matematika analisis dan matematika diskrit bisa lebih optimal, yang pada akhirnya dapat menghasilkan lulusan matematika yang lebih berkualitas dan mampu berpikir sistematis dalam menyelesaikan masalah di dunia nyata. Untuk lebih menyempurnakan RPKPS dan Diktat ini penulis sangat mengharapkan kritik dan masukan dari sesama tenaga pengajar matematika dan para pembaca.
Yogyakarta, November 2013 Penulis
DAFTAR ISI
BAB
BAB
BAB
BAB
BAB
BAB
BAB
KATA PENGANTAR RENCANA KEGIATAN PEMBELAJARAN MINGGUAN DAFTAR ISI I HIMPUNAN BILANGAN BULAT 1.1 Pendahuluan 1.2 Sistem Bilangan Asli 1.3 Relasi Urutab 1.4 Himpunan Bilangan Bulat II KETERBAGIAN 2.1 Pendahuluan 2.2 Keterbagian 2.3 Algoritma Pembagian 2.4 Bilangan Prima III FAKTORISASI PRIMA 3.1 Pendahuluan 3.2 Teorema Fundamental Aritmatik 3.3 Banyak Faktor 3.4 Jumlah Faktor IV FAKTOR PERSEKUTUAN DAN KELIPATAN PERSEKUTUAN 4.1 Pendahuluan 4.2 Faktor Persekutuan Terbesar 4.3 Algoritma Euclid 4.4 Identitas Bezout 4.5 Kelipatan Persekutuan Terkecil V KEKONGRUENAN 5.1 Pendahuluan 5.2 Kekongruenan 5.3 Kelas Residu 5.4 Teorema Kecil Fermat dan Teorema Euler VI PERSAMAAN LINEAR DIOPHANTINE 6.1 Pendahuluan 6.2 Persamaan Linear Diophantine 6.3 Teorema Frobenius VII SISTEM NUMERIK DAN FUNGSI TANGGA 7.1 Pendahuluan 7.2 Sistem Numerik 7.3 Kriteria Keterbagian pada Sistem Desimal 7.4 Fungsi Tangga 7.5 Pangkat Tertingi
halaman i ii ix 1 1 1 4 8 11 11 11 17 17 24 24 24 29 31 34 34 34 37 38 40 44 44 44 48 51 34 57 57 62 66 66 66 72 78 84
BAB VIII HHIMPUNAN BILANGAN RASIONAL 8.1 Pendahuluan 8.2 Konstruksi Sistem Bilangan Rasional 8.3 Relasi Urutan CONTOH SOAL UJIAN TENGAH SEMESTER DAN UJIAN AKHIR DAFTAR PUSTAKA
97 97 97 103 108 116
BAB I HIMPUNAN BILANGAN BULAT 1.1
Pendahuluan Seiring dengan perkembangan budaya masyarakat dibutuhkan alat komunikasi
yang bisa menjelaskan ”banyaknya” benda-benda di kehidupan sehari-hari. Alat komunikasi tersebut tersimbolkan dalam bentuk angka-angka, yang menjabarkan konsep bilangan. Topik ini sangat bermanfaat bagi mahasiswa untuk mengenal salah satu dasar matematika yaitu bilangan dan ladasan pengkonstruksiannya. Setelah mempelajari topik bahasan pada pertemuan minggu ke-1 dan 2 yang meliputi 1. Konstruksi sistem bilangan asli 2. Sifat-sifat bilangan asli 3. Kontruksi sistem bilangan bulat ini secara tuntas diharapkan memiliki learning Outcomes berupa: 1. Mahasiswa mampu menjelaskan pengertian sistem bilangan asli 2. Mahasiswa mampu membuktikan sifat-sifat bilangan asli 3, Mahasiswa mampu mengkonstruksi sistem bilangan bulat sebagai perluasan sistem bilangan asli
1.2
Sistem Bilangan Asli
Sebelum membicarakan sistem bilangan bulat, sebagai langkah awal terlebih dulu akan dipaparkan konsep bilangan asli. Definisi 1.2.1 Diketahui N himpunan yang memuat 1 dan dilengkapi operasi biner ”+” pada N. Jika (N, +) memenuhi: 1. (∀n ∈ N)n + 1 ̸= 1 2. (∀n, m ∈ N)(m + 1 = n + 1 ⇒ m = n) 3. (∀n, m ∈ N)(m + n) + 1 = m + (n + 1) 1
4. Untuk setiap G ⊆ N, jika 4.1 1 ∈ G dan 4.2 n ∈ G ⇒ n + 1 ∈ G, maka G = N, maka N disebut sistem bilangan asli (himpunan bilangan asli). Selanjutnya setiap n ∈ N disebut bilangan asli. Dari sistem aksioma di atas dapat dikonstruksi: 1 +N 1 := 2, (1+N ) +N 1 := 3, ((1 +N 1) +N 1) +N 1 := 4, . . . . Teorema 1.1 3 ̸= 2 Bukti: Dari definisi 3 3 = (1 + 1) + 1 1 + (1 + 1) = (1 + 1) + 1 Aksioma3 1+2 = 3
Definisi”2”dan”3”
Latihan 1.1 Buktikan pernyataan-pernyataan berikut ini! 1. 4 ̸= 2 2. 2 ̸= 5 3. 3 + 1 = 4 4. 2 + 1 = 1 + 2 Berdasarkan aksiomatika dapat diturunkan teorema berikut ini. Teorema 1.2 Untuk setiap n ∈ N berlaku n + 1 ̸= n. Bukti: Dibentuk G = {n|n ∈ N, n + 1 ̸= n}. jelas G ⊆ N. Berdasar A (Aksioma) 1, 1+1 ̸= 1, sehingga 1 ∈ G. Misalkan n ∈ G, yaitu n+1 ̸= n. Namun berdasarkan A2, (n + 1) + 1 ̸= n + 1, sehingga n + 1 ∈ G; dan sesuai A4, G = N. Akibatnya untuk semua n ∈ N berlaku n ∈ G. Jadi n + 1 ̸= n untuk setiap n ∈ N.
.
Sifat berikutnya yang dapat diturunkan berdasarkan sistem aksiomatika himpunan N beserta operasi ”+” adalah sifat asosiatif. 2
Teorema 1.3 Untuk setiap x, y, z ∈ N memenuhi (x + y) + z = x + (y + z). Bukti: Diambil sebarang x, y ∈ N. Pembuktian dengan induksi matematika dikenakan pada z dengan membentuk G = {z|z ∈ N, (x + y) + z = x + (y + z)} Berdasarkan A3, diperoleh z = 1 ∈ G. Dimisalkan benar untuk z ∈ G, yaitu x + (y + z) = (x + y) + z. x + (y + (n + 1)) = x + ((y + n) + 1) x + ((y + n) + 1) = (x + (y + n)) + 1 (x + (y + n)) + 1 = ((x + y) + n) + 1 x + (y + (n + 1)) = ((x + y) + n) + 1 ((x + y) + n) + 1 = (x + y) + (n + 1) x + (y + (n + 1)) = (x + y) + (n + 1) Akibatnya n+1 ∈ G. Sesuai A4, G = N, sehingga untuk setiap z ∈ N, (x+y)+z =
x + (y + z)
Sifat berikut yang berlaku terhadap operasi ”+” adalah komutatif. Untuk itu diperlukan lemma berikut ini sebagai landasar. Lemma 1.4 Untuk setiap n ∈ N, n + 1 = i + n. Bukti: Dibentuk G = {n|n ∈ N, n+1 = n+1}. Jelas G ⊆ N. Karena 1+1 = 1+1, maka 1 ∈ G. Selanjutnya dimisalkan n ∈ G, yang berarti n + 1 = 1 + n. Akibatnya (n + 1) + 1 = (1 + n) + 1, sehingga n + 1 ∈ G; dan berdasarkan A4, G = N.
Teorema 1.5 Untuk setiap n, m ∈ N berlaku n + m = m + n. Bukti: Diambil sebarang n ∈ N. Dibentuk G = {m|m ∈ N, n + m = m + n}. Jelas G ⊆ N. Selain itu menurut Lemma1.2.1, 1 ∈ G. Selanjutnya dimisalkan m ∈ G. Berarti n + m = m + n. (n + m) + 1 = (m + n) + 1 n + (m + 1) = m + (n + 1) = m + (1 + n) = (m + 1) + n 3
Akibatnya m + 1 ∈ G, sehingga menurut A4, G = N. Dengan kata lain untuk setiap m ∈ N, n + m = m + n.
.
Teorema 1.6 (Sifat Kanselatif ) Dalam sistem bilangan N berlaku sifat kanselatif kiri dan kanan: 1. Untuk setiap x, y, z ∈ N, (x + z = y + z) ⇒ (x = y) 2. Untuk setiap x, y, z ∈ N, (x + z = x + y) ⇒ (z = y) Bukti: Hanya dibuktikan untuk 1. Sifat 2 dijadikan latihan. Bukti menggunakan kontraposisinya, yaitu x ̸= y ⇒ x + z ̸= y + z Diambil sebarang x dan y ∈ N, dengan x ̸= y. Dibentuk G = {z|z ∈ N, x + z ̸= y + z}. Karena x ̸= y jelas x + 1 ̸= y + 1 Dimisalkan z ∈ G, dengan kata lain x + z ̸= y + z. Akibatnya x + (z + 1) = (x + z) + 1 ̸= (y + z) + 1 = y + (z + 1) sehingga z + 1 ∈ G. Sesuai A4, dapat disimpulkan G = N, sehingga untuk setiap x, y ∈ N , jika x ̸= y, maka x + z ̸= y + z untuk setiap z ∈ N.
Latihan 1.2 Untuk setiap x, y, z, w ∈ N buktikan: 1. x + y ̸= y 2. Teorema 1.6, bagian 2 3. (x + z) + (y + u) = (y + (x + u)) + z
1.3
Relasi Urutan
Dalam sistem bilangan asli N dapat dikonstruksi relari urutan dengan menggunakan sifat-sifat operasi ”+”. Untuk itu perlu dikaji terlebih dulu sifat elementer berikut ini. Teorema 1.7 Untuk masing-masing n ∈ N − {1}, dapat ditemukan m ∈ N yang memenuhi n = m + 1.
4
Bukti: Dibentuk G = {1, n|n ∈ N, (∃m ∈ N)n = m + 1}. Jelas 1 ∈ G ⊆ N. Dimisalkan n ∈ G, berarti n = 1 atau n = m + 1 untuk suatu m ∈ N. Jika n = 1, maka n + 1 = 1 + 1. Akibatnya n + 1 ∈ G, karena terdapat m = 1 sehingga n + 1 = m + 1. Jika n = m + 1 untuk suatu m ∈ N , maka n + 1 = (m + 1) + 1 Jelas m + 1 ∈ N, akibatnya n + 1 ∈ G. Sesuai A4, maka G = N. Teorema 1.8 Untuk setiap x, y ∈ N, berlaku tepat satu pernyataan: 1. x = y 2. (∃u ∈ N)x + u = y 3. (∃u ∈ N)y + v = x Bukti: Untuk Latihan Berdasarkan Teorema 1.8 dapat diturunkan relasi urutan pada N. Definisi 1.3.1 Untuk setiap x, y ∈ N didefinisikan x < y ⇔ (∃u ∈ N)x + u = y Selanjutnya didefinisikan x > y jika dan hanya jika y < y. Contoh 1.3.2 2 < 2 + 1 = 3, 4 < 4 + 3 = 7,
1<1+n
Teorema 1.9 Untuk setiap x, y ∈ N berlaku tepat hanya satu x = y atau x < y atau x > y. Bukti: Langsung Teorema 1.8 Teorema 1.10 Untuk setiap x, y ∈ N berlaku 1. Jika x < y dan y < z, maka x < z 2. x ̸< x 5
.
3. x = 1 atau 1 < x 4. x < x + y 5. Jika x < y, maka x < y + z 1. Jika x + z < y, maka x < y Bukti: Hanya akan dibuktikan untuk 1. Diketahui x < y dan y < z. Maka dapat ditemukan u, v ∈ N, sehingga y = x + u dan z = y + v sehingga z = y + v = (x + u) + v = x + (u + v), dengan u + v ∈ N. Akibatnya .
x < z.
Sifat berikutnya yang dihasilkan dari relasi urutan pada N dinyatakan dalam teorema berikut ini. Teorema 1.11 Untuk setiap x, y, z ∈ N berlaku 1. Jika x < y, maka x + z < y + z 2. Jika x < y, maka z + x < z + y 3. Jika x + z < y + z, maka x < y 4. Jika z + x < z + y, maka x < y Bukti: Hanya akan dibuktikan untuk 1. No 2, 3, dan 4 dibuktikan di kelas menjadi bahan presentasi. Karena x < y, maka dapat ditemukan u ∈ N sehingga x + u = y. Akibatnya (x + z) + u = x + (z + u) = x + (u + z) = (x + u) + z = y + z
Dengan kata lain x + z < y + z.
Selanjutnya, dengan memanfaatka relasi ”<” dapat didefinisikan operasi pengurangan antara dua bilangan asli yang berbeda. Meskipun operasi ini tidak berlaku untuk semua pasangan bilangan asli, namun fenomena yang muncul dari operasi tersebut sangat berperan dalam sistem yang lebih luas.
6
Definisi 1.3.3 Untuk setiap x < y di N terdapat dengan tunggal u ∈ N yang memenuhi x + u = y. Elemen tunggal yang memenuhi kondisi tersebut ditulis dengan u = y − x. Contoh 1.3.4 Karena 4 < 6, dan 4 + 2 = 6, maka sesuai definisi 2 = 6 − 4. Sebaliknya karena 6 ̸< 4, maka tidak dapat didefinisikan 4 − 6 di N. Teorema 1.12 Untuk setiap x, y ∈ N, 1. Jika x < y, maka y = x + (y − x) 2. Jika z + y = x, maka y = x − z 3. Jika z < x dan y = x − z, maka y + z = x 4. Jika y < x, maka untuk setiap z < y berlaku y − z < x Bukti: Hanya untuk 2. Untuk 1, 3, dan 4 digunakan untuk latihan. Karena z + y = x, berarti y < x. Menggunakan sifat 1, diperoleh x = z + (x − z). Namun karena bilangan u ∈ N yang memenuhi z + u = x tunggal, maka y = x − z.
Selanjutnya akan dibahas operasi perkalian dua buah bilangan asli. Definisi 1.3.5 Pada himpunan bilangan asli N terdapat dengan tunggal pemetaan α : N × N → N yang memenuhi α(1, x) = x, α(x + 1, y) = f (x, y) + y untuk setiap x, y ∈ N. Untuk selanjutnya ditulis α(x, y) = xy. Contoh 1.3.6 Sebagai contoh diambil 4 · 5 = α(3 + 1, 5) = α(3, 5) + 5 = α(2, 5) + 5 + 5 = 5 + 5 + 5 + 5. Secara umum m · n = n + n + ··· + n sebanyak m suku. Teorema 1.13 Untuk setiap x, y ∈ N berlaku 1 · y = y dan (x + 1)y = (xy) + y. 7
Bukti: Langsung dari definisi. Dengan mendasarkan pada sifat-sifat jumlahan dan perkalian bilangan asli, dapat diturunkan sifat-sifat bilangan asli yang selama ini telah dikenal baik mulai dari tingkat SD, SMP, dan SMA. Bebarapa sifat di antaranya sifat distributif kiri dan kanan antara jumlahan dan perkalian, sifat asosiatif dan komutatif terhadap perkalian, sifat kanselatif perkalian, compatible perkalian pada relasi urutan dan distributifitas perkalian terhadap pengurangan. Latihan 1.3 Dengan menggunakan sifat-sifat yang sudah dibuktikan dan pengetahuan SMA selesaikan soal-soal berikut ini 1. Buktikan Teorema 1.8 2. Buktikan Teorema 1.10 3. Buktikan Teorema 1.9 4. Buktikan sifat komutatif, asosiatif, dan kanselatif bilangan asli terhadap perkalian 5. Buktikan bahwa operasi perkalian compatible terhadap relasi urutan.
1.4
Himpunan Bilangan Bulat Solusi dari persamaan x + n = y untuk x, y ∈ N yang diberikan, belum tentu
bisa diperoleh di N. Solusi n ∈ N, hanya bisa diperoleh untuk y > x. Untuk persamaan 5 + n = 3, solusi n bukan elemen N. Untuk itu diperlukan himpunan X yang merupakan perluasan N, sehingga persamaan tersebut selalu bisa ditemukan solusinya. Definisi 1.4.1 Diketahui N himpunan semua bilangan asli. Diambil N− sebarang himpunan yang berbeda semua elementnya sehingga N ∩ N− = ∅
dan
σ : N → N−
pemetaan bijektif. Jadi N− = {σ(n)|n ∈ N}. Selanjutnya diambil 0 ̸∈ N ∪ N− . Himpunan Z = {0} ∪ N ∪ N− yang dilengkapi dengan operasi biner ”+Z ” dan ”·Z ”: 8
1. Untuk semua u, v ∈ Z, didefinisikan u +Z v salah satu dari; untuk masingmasing a, b ∈ N: 1.1 a +Z b = a +N b 1.2 σ(a) +Z σ(b) = σ(a +N b) 1.3 a +Z σ(b) = a −N b, jika a > b, = σ(b −N a), jika b > a = 0, jika b = a 1.4 σ(a) +Z b = b +Z σ(a) 1.5 u +Z 0 = u = 0 +Z u 2. Untuk semua u, v ∈ Z, didefinisikan u ·Z v salah satu dari; untuk masingmasing a, b ∈ N: 1.1 a ·Z b = a ·N b 1.2 σ(a) ·Z σ(b) = σ(a ·N b) 1.3 a ·Z σ(b) = σ(a ·N b) 1.4 σ(a) ·Z b = σ(a ·Z b) 1.5 u ·Z 0 = 0 = 0 ·Z u Berdasarkan definisi di atas dapat dipastikan bahwa (Z, +Z , ·Z ) merupakan perluasan dari sistem bilangan asli (N, +N , ·N ). Struktur Z merupakan struktur bilangan bulat yang sudah dikenal baik, sehingga semua sifat yang melekat pada sistem bilangan bulat menggunakan asiomatika tersebut di atas ekuvalen dengan sifat-sifat himpunan bilangan bulat yang klasik. Termasuk semua terminologi, seperti habis membagi, faktor persekutuan, algoritma pembagian, dan kongruensi. Latihan 1.4 Dengan menggunakan sistem aksiomatika bilangan bulat dan sifatsifat yang sudah di kenal dalam teori bilangan biasa selesaikanlah beberapa masalah berikut ini: 1. Buktikan sifat komutatif terhadap jumlahan dan perkalian berlaku. 2. Buktikan, bahwa sifat asositif berlaku untuk operasi jumlahan maupun perkalian 9
3. Terhadap operasi perkalian, buktikan bahwa operasi jumlahan bersifat distributi, 4. Jika didefinisikan relasi ”≺” pada Z dengan definisi untuk setiap a, b ∈ Z, a ≺ b, jika dan hanya jika terdapat u ∈ N sehingga a + u = b, buktikan bahwa ”≺” merupakan relasi urutan, yang memenuhi (∀, y ∈ Z)(x ≺ y ∨ x = y ∨ y ≺ x) berlaku tepat satu keadaan.
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
10
