Pengantar Teori Bilangan

Pengantar Teori Bilangan Kuliah 2

2/2/2014

Yanita, FMIPA Matematika Unand

1

Materi Kuliah 2 Teori Pembagian dalam Bilangan Bulat Algoritma Pembagian Pembagi Persekutuan Terbesar

2/2/2014

2

Algoritma Pembagian Teorema Algoritma Pembagian Jika 𝑎, 𝑏 ∈ ℤ, dengan 𝑏 > 0, maka terdapat dengan tunggal 𝑞, 𝑟 ∈ ℤ yang memenuhi 𝑎 = 𝑞𝑏 + 𝑟, 0 ≤ 𝑟 < 𝑏 Bilangan 𝑞 disebut pembagi dan 𝑟 disebut sisa dalam pembagian 𝑎 dan 𝑏.

2/2/2014


3

Bukti Teorema Algoritma Pembagian Diketahui 𝑎, 𝑏 ∈ ℤ, dengan 𝑏 > 0. Akan ditunjukkan ∃! 𝑞, 𝑟 ∈ ℤ yang memenuhi 𝑎 = 𝑞𝑏 + 𝑟, 0 ≤ 𝑟 < 𝑏. Bentuk himpunan 𝑆 = 𝑎 − 𝑥𝑏 𝑥 ∈ ℤ, 𝑎 − 𝑥𝑏 ≥ 0 . Untuk menunjukkan 𝑆 ≠ ∅, cukup ditunjukkan nilai 𝑥 yang membuat 𝑎 − 𝑥𝑏 nonnegative. Karena 𝑏 ≥ 1, diperoleh 𝑎 𝑏 ≥ 𝑎 , sehingga 𝑎 − − 𝑎 𝑏 = 𝑎 + 𝑎 𝑏 ≥ 𝑎 + 𝑎 ≥ 0. Dengan memilih 𝑥 = − 𝑎 , maka 𝑎 − 𝑥𝑏 ∈ 𝑆. Jadi 𝑆 ≠ ∅. Dengan menggunakan sifat Well-Ordering Principle, maka 𝑆 memuat bilangan terkecil, misalkan 𝑟. Berdasarkan definisi 𝑆, terdapat bilangan bulat 𝑞 yang memenuhi 𝑟 = 𝑎 − 𝑞𝑏, 0 ≤ 𝑟. Andaikan 𝑟 < 𝑏. Jika tidak berlaku ini maka 𝑟 ≥ 𝑏 dan 𝑎 − 𝑞 + 1 𝑏 = 𝑎 − 𝑞𝑏 − 𝑏 = 𝑟 − 𝑏 ≥ 0 Akibatnya bahwa 𝑎 − 𝑞 + 1 𝑏 adalah bentuk yang ada dalam 𝑆. Tetapi 𝑎 − 𝑞 + 1 𝑏 = 𝑟 − 𝑏 < 𝑟, hal ini kontrakdiksi dengan pemilihan 𝑟 adalah unsur terkecil di 𝑆. Oleh karena itu 𝑟 < 𝑏.

2/2/2014


4

Selanjutnya ditunjukkan ketunggalan 𝑞 dan 𝑟. Andaikan tidak tunggal, berarti 𝑎 = 𝑞𝑏 + 𝑟 = 𝑞 ′ 𝑏 + 𝑟′ dengan 0 ≤ 𝑟 < 𝑏, 0 ≤ 𝑟′ < 𝑏. Maka 𝑟 ′ − 𝑟 = 𝑏 𝑞 − 𝑞 ′ dan karena nilai absolut dari hasilkali adalah sama dengan hasil kali dari nilai absolutnya, maka 𝑟 ′ − 𝑟 = 𝑏 𝑞 − 𝑞′ = 𝑏 𝑞 − 𝑞′ Setelah menambahkan dua ketidaksamaan −𝑏 < −𝑟 ≤ 0 dan 0 ≤ 𝑟′ < 𝑏, diperoleh − 𝑏 < 𝑟 ′ − 𝑟 < 𝑏 atau ekivalen dengan bentuk 𝑟 ′ − 𝑟 < 𝑏. Dengan demikian 𝑏 𝑞 − 𝑞 ′ < 𝑏, yang menghasilkan 0 ≤ 𝑞 − 𝑞 ′ < 1. Karena 𝑞 − 𝑞 ′ ≥ 0, maka satu-satunya nilai yang mungkin adalah 𝑞 − 𝑞 ′ = 0, artinya 𝑞 = 𝑞′, dan ini mengakibatkan 𝑟 = 𝑟′. Jadi terbukti 𝑞 dan 𝑟 adalah tunggal. ∎

2/2/2014


5

Contoh 1. Untuk bilangan bulat 7 dan 2, maka terdapat bilangan bulat 3 dan 1 sehingga 7 = 3 × 2 + 1. 2. Untuk bilangan bulat −9 dan 4, maka terdapat bilangan bulat − 3 dan 3 sehingga −9 = −3 × 4 + 3. 3. Untuk bilangan bulat 20 dan 5, maka terdapat bilangan bulat …

2/2/2014


6

Akibat Teorema Algoritma Pembagian Jika 𝑎, 𝑏 ∈ ℤ , dengan 𝑏 ≠ 0 , maka terdapat dengan tunggal 𝑞, 𝑟 ∈ ℤ yang memenuhi 𝑎 = 𝑞𝑏 + 𝑟, 0 ≤ 𝑟 < 𝑏

2/2/2014


7

Bukti Akibat Teorema Algoritma Pembagian Untuk membuktikan akibat ini, cukup ditunjukkan untuk kasus 𝑏 < 0. Selanjutnya dari 𝑏 > 0 dan dengan Teorema algoritma pembagian diperoleh bilangan 𝑞′ dan 𝑟 yang tunggal, dimana 𝑎 = 𝑞 ′ 𝑏 + 𝑟, 0 ≤ 𝑟 < 𝑏 Ingat bahwa karena 𝑏 < 0, maka 𝑏 = −𝑏, maka dapat diambil 𝑞 = −𝑞′ agar diperoleh 𝑎 = 𝑞𝑏 + 𝑟 dengan 0 ≤ 𝑟 < 𝑏 . ∎

2/2/2014


8

Contoh 1. Untuk bilangan bulat −59 dan −7, maka terdapat bilangan bulat 9 dan 4 sehingga −59 = 9 × −7 + 4 2. Untuk bilangan bulat 1 dan −7, maka terdapat bilangan bulat sehingga 1 = 0 × −7 + 1.

0 dan 1

3. Untuk bilangan bulat −2 dan −7, maka terdapat bilangan bulat … 4. Untuk bilangan bulat 61 dan −7, maka terdapat bilangan bulat …

2/2/2014


9

Teori Pembagi Persekutuan Terbesar (FPB) Definisi: Suatu bilangan bulat 𝑏 dikatakan habis dibagi oleh bilangan bulat 𝑎 ≠ 0, jika terdapat bilangan bulat 𝑐 sedemikian hingga 𝑏 = 𝑎𝑐. (𝑎 membagi habis 𝑏 jika 𝑏 = 𝑎𝑐 untuk suatu 𝑐) Simbol:  Jika 𝑏 habis dibagi 𝑎 maka ditulis dengan 𝑎 𝑏.  Jika 𝑏 tidak habis dibagi oleh 𝑎, maka ditulis 𝑎 ∤ 𝑏. 2/2/2014


10

Sifat-Sifat Teorema Untuk setiap 𝑎, 𝑏, 𝑐 ∈ ℤ, berlaku: a. 𝑎 0, 1 𝑎, 𝑎 𝑎 b. 𝑎 1 jika dan hanya jika 𝑎 = ±1 c. Jika 𝑎 𝑏 dan 𝑐 𝑑, maka 𝑎𝑐 𝑏𝑑 d. Jika 𝑎 𝑏 dan 𝑏 𝑐, maka 𝑎 𝑐 e. 𝑎 𝑏 dan 𝑏 𝑎 jika dan hanya jika 𝑎 = ±𝑏 f. Jika 𝑎 𝑏 dan 𝑏 ≠ 0, maka 𝑎 ≤ 𝑏 g. Jika 𝑎 𝑏 dan 𝑎 𝑐, maka 𝑎 (𝑏𝑥 + 𝑐𝑦) untuk sebarang 𝑥, 𝑦 ∈ ℤ

2/2/2014


11

Pembagi Persekutuan Terbesar atau FPB Review pelajaran SD kelas V tentang FPB Untuk mencari FPB dari dua buah bilangan bulat, maka langkah-langkah yang diperlukan adalah: 1. Tentukan factor pembagi yang merupakan bilangan prima (faktorisasi prima) dari masing-masing bilangan. 2. Setelah seluruh kemungkinan factor pembagi prima dilakukan, maka tentukan factor pembagi prima yang sama-sama dimiliki oleh kedua bilangan tersebut. 3. Perhatikan pangkat terkecil untuk masing-masing factor prima yang diperoleh. 4. FPB dari bilangan tersebut adalah perkalian factor prima yang sama dengan pangkat yang terkecil.

2/2/2014


12

Contoh FPB dari 36 dan 90 1.

Faktorisasi prima dari 36 = 2 × 2 × 3 × 3 = 22 × 32 Faktorisasi prima dari 90 = 2 × 3 × 3 × 5 = 2 × 32 × 5 2. Faktor prima yang sama untuk 36 dan 90 adalah 2 dan 3 3. Pangkat terkecil untuk factor prima 2 adalah 1, dan pangkat terkecil untuk factor prima 3 adalah 2

4. FPB dari 36 dan 90 adalah 2 × 32 = 18

2/2/2014


13

Cara lain FPB dari 36 dan 90 adalah Faktor dari 36 adalah 1, 2, 3, 4, 6, 9, 12, 𝟏𝟖, 36 Faktor dari 90 adalah 1, 2, 3, 5, 6, 9, 10, 15, 𝟏𝟖, 30, 45, 90 Maka FPB dari 36 dan 90 adalah 18

2/2/2014


14

Definisi Pembagi Persekutuan Terbesar Definisi Misalkan 𝑎, 𝑏 ∈ ℤ, dengan salah satu dari 𝑎 atau 𝑏 tidak sama dengan nol. Pembagi persekutuan terbesar (greatest common divisor) dari 𝑎 dan 𝑏, adalah 𝑑 yang memenuhi sifat berikut: 1. 𝑑 𝑎 dan 𝑑 𝑏 2. Jika 𝑐 𝑎 dan 𝑐 𝑏 maka 𝑐 ≤ 𝑑 (Jika 𝑑 pembagi persekutuan terbesar dari 𝑎 dan 𝑏, maka disimbolkan dengan 𝑝𝑝𝑏(𝑎, 𝑏) atau gcd(𝑎, 𝑏)) (SD FPB)

2/2/2014


15

Perhatikan contoh 𝑝𝑝𝑏 36,90 = 18 18 adalah pembagi persekutuan terbesar dari 36 dan 90. Dengan definisi pembagi persekutuan terbesar, perhatikan bahwa  18 36 karena 36 = 2 × 18  18 90 karena 90 = 5 × 18  Bilangan lain yang membagi habis 36 dan 90 adalah 9, yaitu 9 36 dan 9 90 dan perhatikan bahwa 9 < 18

2/2/2014


16

Contoh lain • 𝑝𝑝𝑏 −5,5 = 5 • 𝑝𝑝𝑏 8,17 = 1 • 𝑝𝑝𝑏 −8, −36 = 4

2/2/2014


17

Sifat 𝑝𝑝𝑏(𝑎, 𝑏) Teorema Misalkan 𝑎, 𝑏 ∈ ℤ dengan 𝑎 ≠ 0 dan 𝑏 ≠ 0, maka terdapat 𝑥, 𝑦 ∈ ℤ sedemikian sehingga 𝑝𝑝𝑏 𝑎, 𝑏 = 𝑎𝑥 + 𝑏𝑦 Contoh: • 𝑝𝑝𝑏 36,90 = 36 −12 + 90(5) • 𝑝𝑝𝑏 8,17 = 8 −2 + 17(1) • 𝑝𝑝𝑏 −5,5 = −5 5 + 5 6 • 𝑝𝑝𝑏 −8, −36 = −8 4 ± 36 1 2/2/2014


18

Akibat dari 𝑝𝑝𝑏 𝑎, 𝑏 = 𝑎𝑥 + 𝑏𝑦 Oleh karena nilai 𝑥 dan 𝑦 tidak tunggal, maka ada banyak kemungkinan penyelesaian untuk persamaan 𝑎𝑥 + 𝑏𝑦. Maka diperoleh Akibat 1. Misalkan 𝑎, 𝑏 ∈ ℤ dengan 𝑎 ≠ 0 dan 𝑏 ≠ 0 , maka himpunan 𝑇 = 𝑎𝑥 + 𝑏𝑦 𝑥, 𝑦 ∈ ℤ adalah himpunan semua perkalian dari 𝑑 = 𝑝𝑝𝑏(𝑎, 𝑏). Akibat 2 Jika 𝑎 𝑐 dan 𝑏 𝑐, dengan 𝑝𝑝𝑏 𝑎, 𝑏 = 1, maka 𝑎𝑏 𝑐 2/2/2014


19

Sifat-sifat lain Teorema (Lemma Euclid) Jika 𝑎 𝑏𝑐, dengan 𝑝𝑝𝑏 𝑎, 𝑏 = 1, maka 𝑎 𝑐. Teorema Misalkan 𝑎, 𝑏 ∈ ℤ dengan 𝑎 ≠ 0 dan 𝑏 ≠ 0. 𝑑 = 𝑝𝑝𝑏(𝑎, 𝑏) jika dan hanya jika a. 𝑑 𝑎 dan 𝑑 𝑏 b. Jika 𝑐 𝑎 dan 𝑐 𝑏, maka 𝑐 𝑑

2/2/2014

Selesai 7 Februari 2014

20

Pengantar Teori Bilangan

Recommend Documents