keterbagian, kpk & fpb

1

Bab 2Bilangan Bulat

Sifat Keterbagian, Faktor Prima, Faktor Persekutuan Terbesar (FPB) danKelipatan Persekutuan Terbesar (KPK)

Hyronimus Lado, S.Pd

Elements of Modern Algebra 7th ed(Gilbert, J. and Gilbert, L. 2009. hal. 81-95)

2.3 Sifat Keterbagian

Sekarang kita beralih mempelajari sifat keterbagian bilangan bulat. Tujuanutama kita pada bagian ini adalah untuk mendapatkan algoritma pembagian(teorema 2.10). untuk mencapai ini, kita membutuhkan konsekuensi penting sifatinduksi , dikenal sebagai sifat terurut baik.

Teorema 2.7 Sifat Terurut Baik

Setiap himpunan tak kosong S dari bilangan bulat positif memiliki satu elementerkecil. Artinya ada m S sehingga m ≤ x untuk semua x elemen S.

qp Bukti: Misalkan S himpunan tak kosong bilangan bulat positif. Jika 1S,

maka 1 ≤ x untuk semua xS, dari teorema 2.6. Dalam kasus ini m = 1adalah anggota terkecil dari S.

Perhatikan pada kasus dimana 1S. dan misalkan L menjadi himpunansemua bilangan bulat positif sehingga p < x untuk semua x S, artinya

L = { p ∈ Z+ : p < x untuk semua x ∈ S},

Karena 1S, teorema 2.6 menyakinkan kita bahwa 1L. Kita akantunjukkan bahwa ada suatu bilangan positif po sehingga po L dan po + 1L. Seandainya bukan dalam kasus ini. Kita punya p L maka p + 1L,dan L = Z+ dengan sifat induksi. Ini kontradiksi dengan fakta bahwa Sadalah tak kosong (Catatan bahwa L ∩ S = ∅ ). untuk itu ada po

sedemikian sehinga po∈ L dan po + 1L.

Kita harus menunjukkan bahwa po + 1 S. Kita memiliki po < x untuksemua xS, jadi po + 1 ≤ x untuk semua xS (Lihat latihan 28 diakhirbagian ini) Jika po + 1 < x adalah selalu benar, maka po + 1 akan ada di L.Sehingga po + 1 = x untuk suatu xS, dan m = po + 1 adalah suatu unsurterkecil yang diinginkan di S.

2

Definisi 2.8 Pembagi dan Kelipatan

Misalkan a dan b adalah bilangan bulat. Kita menyebut a membagi b jika adabilangan bulat c sedemikian hingga b = ac.

Jika a membagi b, kila menulis a|b. Kita menyebut bahwa b adalah kelipatan daria. atau a adalah faktor/pembagi dari b. Jika a bukan membagi b, kita tulis a | b.

Contoh :

1. 3|12 karena ada bilangan bulat 4 sedemikian hingga 12 = 3.4

2. 2 ∤ 7 karena tidak ada bilangan bulat c yang menyebabkan 7 = 2.c

3. Misal b adalah bilangan bulat tak non maka b|0

4. Misal b adalah sebarang bilangan bulat maka 0 ∤5. Jika | dan | maka =

Ini dapat menjadi sebuah kejutan bahwa kita dapat menggunakan hasil untukmembuktikan teorema sederhana berikut.

Teorema 2.9 Pembagi 1

Pembagi 1 hanya 1 dan -1

rqp Bukti : Misalkan a adalah membagi habis 1. Maka 1 = ac untuk

suatu bilangan bulat c. Persamaan 1 = ac mengharuskan a ≠ 0,sehingga aZ+ atau -aZ+.

Kasus 1 dimana aZ+. Ini mengakibatkan cZ+ sehingga a 1 danc 1 (lihat latihan 32 bagian 2.1), jadi kita memiliki 1 ≤ a dan 1 ≤ c,dengan teorema 2.6. Sekarang

1 < a 1 . c < a . c dari latihan 18 bagian 2.1

c < 1 karena ac = 1

Dan ini kontradiksi dengan 1 ≤ c. jadi 1 = a hanya mungkin ketika aZ+

.

Kasus 1 dimana -aZ+. Dari latihan 5 bagian 2.1, kita memiliki

(-a)(-c) = ac = 1,

3

Dan -aZ+ mengakibatkan –c Z+ dari latihan 32 bagian 2.1.Karena itu, 1 ≤ -a dan 1 ≤ -c dari teorema 2.6. Sekarang

1 < -a (1)(-c) < (-a)(-c) dari latihan 18 bagian 2.1

-c < 1 karena (-a)(-c) = 1

Dan -c < 1 adalah kontradiksi dengan 1 ≤ -c . oleh karena itu, 1 = -ahanya mungkin ketika -aZ+, dan kita memiliki

a = - ( -a) dari latihan 3 bagian 2.1

= - 1 karena – a = 1

Mengkombinasikan kasus-kasus dimana aZ+ dan -aZ+, kita dapatmenunjukkan bahwa a = 1 atau a = -1 jika a adalah pembagi 1.

Hasil berikutnya adalah teorema dasar untuk keterbagian.

Contoh Theorema 2.9

2|1 tidak mungkin karena tidak ada bilangan bulat c yang memenuhi 1 = 2c

Teorema 2.10 Algoritma Pembagian

Misalkan a dan b bilangan bulat dengan b > 0. Maka ada bilangan bulat qdan r yang tunggal sehingga

a = bq + r dengan 0 ≤ r < b

Eksistensi Bukti: Misalkan S himpunan semua bilangan bulat x yang dapat ditulisdalam bentuk x = a – bn untuk nZ. dan misalkan S’ lambanghimpunan semua bilangan bulat tak negatif di S. himpunan S’ takkosong.(lihat latihan 29 pada bagian akhir). Jika 0 S’, kita memilikia – bq = 0 untuk beberapa q dan a = bq + 0. Jika 0S’maka S’memiliki elemen terkecil r = a - bq dengan teorema sifat terurut, dan

a = bq + r

dimana r adalah positif. Sekarang

r – b = a – bq - b = a –b(q + 1),

jadi r – b S. karena r adalah unsur terkecil elemen di S’ dan r – b <r, pasti benar bahwa r -b adalah negatif. berarti r – b < 0, dan r < b.Gabungan dua kasus (dimana 0 S’ dan dimana 0 S’), kitamemiliki

4

a = bq + r dan 0 ≤ r < b

Ketunggalan Untuk membuktikan q dan r adalah tunggal, andaikan a = bq1 + r1

dan a = bq2 + r2 dimana 0 ≤ r1 < b dan 0 ≤ r2 < b. Kita dapatmengasumsikan bahwa r1 ≤ r2 tanpa kehilangan sifat umum. Iniberarti bahwa

0 ≤ r2 - r1 ≤ r2 < b.

Bagaimanapun, kita selalu memiliki

0 ≤ r2 - r1 = (a - bq2) – (a - bq1)= b(q1 – q2).

Itu berarti, r2 - r1 adalah kelipatan nonnegatif dari b yang manakurang dari b. Untuk sebarang bilangan bulat positif n, 1 ≤ nmengakibatkan b ≤ bn. Untuk itu, r2 - r1 = 0 dan r2 = r1. Jadiberlaku oleh bq1 = bq2, dimana b ≠ 0. Ini mengakibatkan bahwa q2

= q1 (lihat latihan 26 bagian 2.1). Kita telah menunjukkan bahwa r2

= r1 dan q2 = q1, dan ini membuktikan bahwa q dan r adalahtunggal.

Secara umum, untuk sebarang a,b Z ; b 0 maka terdapat secara tunggal q, r

Z sehingga a = bq + r dengan r0 < b

Kata algoritma dalam pengertian teorema 2.10 mungkin sepintas kelihatan aneh,karena algoritma bisa menggunakan prosedur berulang untuk memperoleh hasil.Kegunaan kata itu adalah fakta bahwa anggota a – bn dari S’ dalam pembuktiandapat ditemukan dengan mengulang pengurangan b:

a – b, a – 2b, a – 3b,

dan seterusnya.

Pada algoritma pembagian, bilangan bulat q disebut hasil bagi dan rdisebut sisa dalam pembagian dari a oleh b. Kesimpulan teorema mungkin lebihdikenal dalam bentuk

b

rq

b

a ,

Tetapi kita membatasi kerja kita disini jadi hanya bilangan bulat yang dilibatkan.

Contoh 1

Ketika a dan b adalah dua bilangan bulat positif, hasil bagi q dan sisa r dapatdiperoleh dengan kebiasaan umum pembagian panjang (kebawah) sebagai contoh,jika a = 357 dan b = 13, dengan pembagian panjang

5

6

91

97

26

2735713

Jadi q = 27 dan r = 6 pada a = bq + r, dengan 0 ≤ r < b:

375 = (13)(27) + 6

Jika a adalah negatif, sedikit penyesuaian minor (lihat latihan 30 bagian ini) dapatdibuat untuk mendapatkan hasil pada algoritma pembagian. Dengan a = -357 danb = 13, persamaan sebelumnya dapat dikalikan dengan -1 untuk mendapat

-357 = (13)(-27) + (-6)

Untuk mendapatkan hasil dengan sisa positif, kita hanya perlu mengurangi danmenjumlahkan 13 pada ruas kanan persamaan :

-357 = (13)(-27) + (13)(-1) + (-6) + 13

= (13)(-28) + 7

Jadi q = -28 dan r = 7 dalam algoritma pembagian, dengan a = -357 dan b = 13.

Contoh Teorema 2. 10 Algoritma Pembagian

1. Perhatikan bilangan -3 dan 7 terdapat bilangan -1 dan 4 sehingga

-3 = (-1)(7) + 4

Dimana 0 ≤ 4 < 7Soal

1. Hal 85 no. 17

Buktikan jika ,b dan c bilangan bulat sehingga | dan | maka|( + )Jawab| artinya =| artinya = + dengan x dan y bilangan bulat+ = ++ = ( + ) artinya | ( + )Terbukti.

6

2. hal 85 no 21

Buktikan jika dan b bilangan bulat sehingga | dan | maka = b

atau b=

Jawab

Misal ada c sehingga | artinya = dan| artinya =Subtitusikan 2 persamaan tersebut sehingga== ( )== 1 sehingga = ±1Jika c = 1 maka = . 1 sehingga =Jika c = -1 maka = . (−1) sehingga = −Terbukti.

3. Nomor 4 dan 7

Tentukan q dan r sehingga memenuhi kondisi algoritma pembagian jika

a. a =-27 dan b=7

Jawab

Algoritma pembagian harus memenuhi a = bq + r dengan 0 ≤ <-27 = q.7 + r

-27 = (-4).7 + 1 dengan 0 ≤ 1 < 7Jadi q = -4 dan r = 1

b. a = 512 dan b = 15

Jawab

Algoritma pembagian harus memenuhi a = bq + r dengan 0 ≤ <512 = q.15 + r

512 = 34. 15 + 2 dengan 0 ≤ 2 < 15Jadi q = 34 dan r = 2

7

2.4 Faktor Prima dan Faktor Persekutuan Terbesar

Pada bagian ini, kita menetapkan adanya faktor persekutuan terbesar dari duabilangan bulat jika paling sedikit satu dari bilangan itu tidak nol. TeoremaTunggal Faktorisasi, juga dikenal sebagai Teorema Fundamental dari Aritmatika.

Definisi 2.11 ■ Faktor Persekutuan Terbesar

Sebuah bilangan bulat d adalah faktor persekutuan terbesar dari a dan b jikasemua syarat terpenuhi:

1. d adalah bilangan bulat positif.2. d|a dan d|b.3. c|a dan c|b maka c|d.

Teorema berikutnya menunjukkan bahwa faktor persekutuan terbesar ddari a dan b ada ketika setidaknya salah satu dari mereka tidak nol. Bukti kita jugamenunjukkan bahwa d adalah kombinasi linear dari a dan b, yaitu, d = ma + nbuntuk bilangan bulat m dan n.

Strategi ■ Teknik pembuktian dengan menggunakan Teorema Terurut Baikdalam Teorema 2.12 harus dibandingkan dengan yang digunakan dalam buktiAlgoritma Pembagian (Teorema 2.10).

Teorema 2.12 ■ Faktor Persekutuan Terbesar

Misalkan a dan b bilangan bulat, paling sedikit satu dari mereka tidak 0.Kemudian terdapat faktor persekutuan terbesar yang tunggal d dari a dan b. Selainitu, d dapat ditulis sebagai

d = am + bn

untuk bilangan bulat m dan n, dan d adalah bilangan bulat positif terkecil yangdapat ditulis dalam bentuk ini.

Eksistensi Bukti:Misalkan a dan b bilangan bulat, paling sedikit satu dari merekatidak 0. Jika b = 0, maka a ≠ 0, sehingga | | > 0 . Sangat mudah untukmelihat bahwa d = | | adalah faktor persekutuan terbesar dari a dan bdalam kasus ini, dan tepat salah satu d = a ∙ (1) + b ∙ (0) atau d = a ∙ (-1) + b ∙ (0).

Misalkan sekarang bahwa b ≠ 0. Dengan pertimbangan himpunan Sadalah semua bilangan bulat yang dapat ditulis dalam bentuk ax + byuntuk beberapa x dan y bilangan bulat, dan misalkan S+ adalahhimpunan semua bilangan bulat positif dalam S. Himpunan Smengandung b = a ∙ (0) + b ∙ (1) dan - b = a ∙ (0) + b ∙ (-1), sehingga S+

8

tidak kosong. Dengan Teorema Terurut Baik, S+ memiliki unsurterkecil d,

d = am + bn

Kita memiliki d positif, dan kita akan menunjukkan bahwa d adalahfaktor persekutuan terbesar dari a dan b.

Dengan Algoritma Pembagian, terdapat bilangan bulat q dan rsehingga.

a = dq + r dengan 0 ≤ r < d.

Dari persamaan ini,r = a – dq= a – (am + bn)q= a – amq – bnq= a(1 – mq) + b (- nq).

Jadi r ada didalam S = {ax + by}, dan 0 ≤ r < d. Dengan pilihan dsebagai unsur terkecil di S+, itu harus benar bahwa r = 0, dan d|a.Demikian pula, dapat ditunjukkan bahwa d|b.

Jika c|a dan c|b, maka a = ch dan b = ck untuk bilangan bulat h dan k.Oleh karena itu,

d = am + bn= chm + ckn= c(hm + kn),

dan ini menunjukkan bahwa c|d. Dengan Definisi 2.11, d = am + bnadalah faktor persekutuan terbesar dari a dan b. Ini mengikuti daripilihan d sebagai elemen terkecil S+ dimana d adalah bilangan bulatpositif terkecil yang dapat ditulis dalam bentuk ini.

Ketunggalan Untuk menunjukkan bahwa faktor persekutuan terbesar dari a dan badalah tunggal, menganggap bahwa d1 dan d2 adalah faktor persekutuanterbesar dari a dan b. Maka harus benar bahwa d1|d2 dan d2|d1. d1 dan d2

adalah bilangan bulat positif, ini berarti bahwa d1 = d2 (lihat Latihan 21Bagian 2.3).

Setiap faktor persekutuan terbesar dari a dan b ada, kita akan menulis (a,b) atau gcd(a, b) untuk menunjukkan faktor persekutuan terbesar yang tunggaldari a dan b.

Ketika setidaknya satu dari a dan b tidak 0, bukti dari teorema terakhirmenetapkan keberadaan dari (a, b), tetapi mencari bilangan bulat positif terkecil di

9

S ={ax + by} bukanlah metode yang sangat mudah untuk menemukan faktorpersekutuan terbesar ini. Sebuah prosedur yang dikenal sebagai Algoritma Euclidmemoles suatu metode sistematis untuk menemukan (a, b) di mana b > 0. Hal inidapat juga digunakan untuk menemukan bilangan bulat m dan n sehingga (a, b) =am + bn. Prosedur ini terdiri dari aplikasi berulang dari Algoritma Pembagianmenurut pola berikut, dimana a dan b adalah bilangan bulat dengan b > 0.

Algoritma Euclida = bq0 + r1, 0 ≤ r1 < bb = r1q1 + r2, 0 ≤ r2 < r1

r1 = r2q2 + r3, 0 ≤ r3 < r2⋮ ⋮rk = rk+1qk+1 + rk+2, 0≤rk+2 < rk+1

Karena bilangan bulat r1, r2, ..., rk+2 menurun dan nonnegatif semua, ada bilanganbulat terkecil n sehingga rn+1 = 0:

rn-1 = rnqn + rn+1, 0 = rn+1.Jika kita menempatkan r0 = b, rn sisa terakhir yang bukan nol selalu menjadifaktor persekutuan terbesar dari a dan b. Bukti dari pernyataan ini yang tersisasebagai latihan.

Sebagai contoh, kita akan menemukan faktor persekutuan terbesar dari1492 dan 1776.Contoh 1 Dengan Melakukan aritmatika untuk Algoritma Euclid, kitamemperoleh

1776 = (1)(1492) + 284 (q0 = 1, r1 = 284)1492 = (5)(284) + 72 (q1 = 5, r2 = 72)284 = (3)(72) + 68 (q2 = 3, r3 = 68)72 = (1)(68) + 4 (q3 = 1, r4 = 4)68 = (4)(17) (q4 = 4, r5 = 0)

Dengan demikian sisa nol terakhir adalah rn = r4 = 4, dan (1776, 1492) = 4. ■Seperti disebutkan sebelumnya, Algoritma Euclid juga dapat digunakan untukmenemukan bilangan bulat m dan n sehingga

(a, b) = am + bnKita dapat memperoleh bilangan bulat dengan memecahkan untuk sisa tidak nolterakhir dan mengganti sisanya dari persamaan sebelumnya berturut-turut sampaia dan b yang hadir dalam persamaan. Sebagai contoh, sisanya dalam contoh 1dapat dinyatakan sebagai

284 = (1776)(1) + (1492)(-1)72 = (1492)(1) + (284)(-5)68 = (284)(1) + (72)(-3)4 = (72)(1) + (68)(-1).

10

Dengan Mengganti sisanya dari persamaan sebelumnya berturut-turut, di peroleh

4 = (72)(1) + [(284)(1) + 72 (-3)](-1)= (72)(1) + (284)(-1) + 72 (3)= (72)(4) + (284)(-1) setelah subtitusi pertama= [(1492)(1) + (284)(-5)](4) + (284)(-1)= (1492)(4) + (284)(-20) + (284)(-1)= (1492)(4) + (284)(-21) setelah subtitusi kedua= (1492)(4) + [(1776)(1) + (1492)(-1)](-21)= (1492)(4) + (1776)(-21) + (1492)(21)= (1776)(-21) + (1492)(25) setelah subtitusi ketiga.

Jadi m = -21 dan n = 25 adalah bilangan bulat sedemikian sehingga

4 = 1776m + 1492n.

Sisanya dicetak dalam huruf tebal di setiap langkah-langkah sebelumnya, dankami dengan hati-hati menghindari melakukan perkalian yang melibatkan sisanya.

m dan n tidak tunggal dalam persamaan

(a, b) = am + bn

Untuk melihat ini, hanya menambah dan mengurangi perkalian ab:

(a, b) = am + ab + bn – ab= a(m + b) + b(n – a).

Jadi m’ = m + b dan n’ = n - a adalah sepasang bilangan bulat sedemikiansehingga

(a, b) = am’ + bn’.

Keterangan kondisi d = am + bn tidak selalu mengakibatkan (a,b) =d.

sebagai contoh penyangkal 4 = 6 (2) + 4 (-2) tetapi (6, 4) ≠ 4.

Definisi 2.13 ■ Relatif Prima Bilangan Bulat

Dua bilangan bulat a dan b adalah relatif prima jika faktor persekutuanterbesarnya adalah 1.

Dalam dua bagian berikutnya dari bab ini, kami membuktikan beberapahasil yang menarik tentang bilangan bulat yang relatif prima dengan bilanganbulat n yang diberikan. Teorema 2.14 berguna dalam bukti dari hasil tersebut.

Teorema 2.14 ■

Jika a dan b relatif prima dan a|bc maka a|c.

11

(p ⋁ ) ⇒ Bukti: Asumsikan bahwa (a, b) = 1 dan a|bc. karena (a, b) = 1,terdapat bilangan bulat m dan n sehingga 1 = am + bn, berdasarkanTeorema 2.12. karena a|bc, ada suatu bilangan bulat q sehingga bc =aq. Sekarang,

1 = am + bn ⇒ c = acm + bcn⇒ c = acm + aqn karena bc = aq⇒ c = a(cm + qn)⇒ a|c.Jadi teorema tersebut terbukti.

Di antara bilangan bulat, ada yang memiliki faktor bilangan yang palingsedikit. Beberapa di antaranya adalah bilangan bulat prima.

Definisi 2.15 ■ Bilangan Bulat Prima

Sebuah bilangan bulat p adalah bilangan bulat prima jika p > 1 dan pembagi-pembagi/factor-faktor dari p hanyalah ±1 dan ±p.

Perhatikan bahwa kondisi p > 1 membuat p positif dan memastikan bahwap ≠ 1. Pengecualian 1, dari himpunan bilangan prima memungkinkan pernyataanTeorema Faktorisasi Ketunggalan. Sebelum menggali itu, kita membuktikan sifatpenting dari bilangan prima dalam Teorema 2.16.

Strategi ■ Kesimpulan dalam teorema berikutnya memiliki bentuk “r atau s”.Salah satu teknik yang dapat digunakan untuk membuktikan "atau" Pernyataanseperti ini adalah dengan mengasumsikan bahwa satu bagian (seperti r) tidakdiperoleh, dan menggunakan asumsi ini untuk membantu membuktikan bahwabagian lain kemudian harus diperoleh.

Teorema 2.16 ■ Lemma Euclid †

Jika p adalah prima dan p|ab, maka tepat salah satu p|a atau p|b.

(p ⋀ ) ⇒ ( ⋁ ) Bukti: Asumsikan p adalah prima dan p|ab. Jika p|a,kesimpulan dari teorema tersebut cukup.Misalkan, p tidak membagi a. Ini mengakibatkan bahwa 1 =(p, a), karena satu-satunya pembagi positif dari p adalah 1 danp. Kemudian Teorema 2.14 mengakibatkan bahwa p|b. Jadi p|bjika p tidak tidak membagi a, dan teorema adalah benar dalamkasus apapun.

Akibat generalisasi Teorema 2.16 untuk hasil dengan lebih dari duafaktor. Buktinya diminta dalam latihan. Sebuah akibat langsung dari konsekuensiini adalah bahwa jika p prima dan p|an, maka p|a.

12

Corollary 2.17 ■

Jika p prima dan p|(a1a2...an), maka p membagi suatu aj.

Hal ini membawa kita ke Teorema Faktorisasi Ketunggalan, berakibatpenting sehingga itu sering disebut Teorema Dasar Aritmatika.

Strategi ■ Perhatikan bukti bagian ketunggalan Teorema 2.18: Dua faktorisasidiasumsikan, dan kemudian dibuktikan bahwa keduanya adalah sama.

Teorema 2.18 ■ Teorema Faktorisasi KetunggalanSetiap bilangan bulat positif n tepat salah satu dari 1 atau yang dapat dinyatakansebagai perkalian dari bilangan bulat prima, dan faktorisasi ini adalah tunggalkecuali untuk faktor terurut.Menyelesaikan dengan Induksi

Bukti:Dalam pernyataan dari teorema, perkalian digunakan dalam arti diperluas:perkalian mungkin hanya memiliki satu faktor.Misalkan Pn menjadi pernyataan tepat salah satu n = 1 atau n dapatdinyatakan sebagai perkalian dari bilangan prima. Kita akan membuktikanbahwa Pn adalah benar untuk semua n Z+ oleh Prinsip Kedua InduksiTerbatas (Finite).Sekarang P1 benar. Asumsikan bahwa Pm benar untuk semua bilanganbulat positif m < k. Jika k adalah prima, maka k merupakan perkaliandengan satu faktor utama, dan Pk benar. Misalkan k bukan prima.Kemudian k = ab, di mana a atau b kedua-duanya bukanlah 1. Oleh karenaitu, 1 < a < k dan 1< b < k. Dengan hipotesis induksi, Pa benar dan Pb

benar. Artinya,a = p1p2 ... pr dan b = q1q2 ... qs

untuk bilangan prima pi dan qj. Ini memberikan faktorisasik = ab = p1p2 ... prq1q2 ... qs

,

dan k dengan demikian dinyatakan sebagai perkalian dari bilangan prima.Jadi Pk benar, dan karena itu Pn benar untuk semua bilangan bulat positifn.

KetunggalanUntuk membuktikan bahwa faktorisasi adalah tunggal, misalkan

n = p1p2 ... pt dan n = q1q2 ... qv

adalah faktorisasi dari n sebagai hasil kali dari faktor prima pi dan qj.Kemudian

p1p2 ... pt = q1q2 ... qv,

13

sehingga p1|(q1q2 ... qv). Dengan Corollary 2.17, p1| qj untuk beberapa j,dan tidak ada salahnya jika kita asumsikan j = 1. Namun, p1 dan q1 adalahbilangan prima, sehingga p1|q1 mengakibatkan q1 = p1. Ini memberikan

p1p2 ... pt = p1q2 ... qv,dan karena itu

p2 ... pt = q2 ... qv

oleh hukum kanselisasi. Argumen ini dapat diulang, dengan menghapussatu faktor pi dengan masing-masing penerapan hukum pembatalan,sampai kita memperoleh

pt = qt ... qv.

Karena hanya faktor positif dari pt adalah 1 dan pt, dan karena setiap qj

adalah prima, ini berarti bahwa harus ada hanya satu qj di sebelah kananpersamaan, dan itu adalah qt. Artinya, v = t dan qt = pt. Ini melengkapibukti.Teorema Faktorisasi Ketunggalan dapat digunakan untuk menggambarkan

bentuk standar dari bilangan bulat positif n. Misalkan p1, p2, ... , pr adalah faktorprima yang berbeda dari n, diatur dalam urutan besarnya sehingga

p1 < p2 < ... < pr.

Kemudian semua faktor berulang dapat dikumpulkan bersama dan diekspresikandengan menggunakan eksponen untuk menghasilkan

n = ...

dimana mi adalah bilangan bulat positif. Setiap mi disebut multiplisitas dari pi, danfaktorisasi ini dikenal sebagai bentuk standar untuk n.

Contoh 3 Bentuk standar untuk dua bilangan bulat positif a dan b dapatdigunakan untuk menemukan faktor persekutuan terbesar (a, b) dan beberapafaktor persekutuan (lihat Latihan 28 dan 29 pada akhir bagian ini). Misalnya, jika

a = 31.752 = 23 ∙ 34 ∙ 72 dan b = 126.000 = 24 ∙ 32 ∙ 53∙ 7,

maka (a, b) dapat ditemukan dengan membentuk hasil dari semua faktor primayang sama, dengan masing-masing faktor persekutuan pangkat paling rendah yangmuncul dalam faktorisasi:

(a, b) = 23 ∙ 32 ∙ 7 = 504.■

Dari satu sudut pandang, Teorema Faktorisasi Ketunggalan mengatakanbahwa bilangan bulat prima sedang membangun blok untuk bilangan bulat,

14

dimana "bangunan" yang dilakukan dengan menggunakan perkalian danmembentuk hasil. Sebuah pertanyaan alami, yaitu: Berapa banyak blok? dariTeorema berikutnya menyatakan jawaban yang diberikan oleh ahli matematikaYunani kuno Euclid-yang jumlah bilangan prima adalah tak terhingga. Bukti iniadalah penghargaan ke Euclid.

Teorema 2.19 ■ Teorema Euclid pada Bilangan Prima

Banyaknya bilangan prima adalah tak terhingga

Kontradiksi Bukti:Andai ada sejumlah hingga bilangan-bilangan prima n, daribilangan prima. Misalkan n ini bilangan prima yang dapatdilambangkan oleh p1, p2, ..., pn, dengan memperhatikan bilanganbulat

m = p1p2 ... pn + 1.

Hal ini jelas bahwa sisa dalam pembagian m oleh bilangan prima pi

adalah 1, sehingga masing-masing pi bukan faktor dari m. Dengandemikian ada dua kemungkinan: Salah satu m itu sendiri merupakanprima, atau memiliki faktor prima yang berbeda dari setiap satu pi

tersebut. Dalam kedua kasus, kita memiliki sebuah bilangan bulatprima yang tidak dalam daftar p1, p2, ... , pn. Oleh karena itu, adalebih dari n bilangan prima, dan ini kontradiksi dengan pengandaian.

Contoh soal Hal 94

9. Misal a adalah bilangan bulat bukan nol dan b adalah bilangan bulat positif.Terbukti atau tidak bahwa (a,b) = (a, a + b).

Jawab:

Harus dibuktikan (a,b)|(a, a + b) dan (a, a + b)|(a, b)

Karena (a,b)|a dan (a,b)| a + b, maka (a,b)|b.

Selanjutnya (a,b)|b dan (a,b)|a maka (a,b) adalah faktor persekutuan dari adan a + b dengan demikian (a,b)|(a, a + b)

Sebaliknya, karena (a, a + b)|a dan (a, a + b)|a + b maka (a, a + b)|b.

Selanjutnya (a, a + b)|b dan (a, a + b)|a maka (a, a + b) adalah faktorpersekutuan dari a dan b dengan demikian (a, a + b)|(a,b).

12. Jika b > 0 dan a = bq +r, buktikan bahwa (a,b) = (b,r).

17

4. Temukan gcd(a, b) dan bilangan bulat m dan n sedemikian sehingga (a, b)= am + bn.a. a =102, b = 66b. a = 414, b = -33

Latihan 2.4

Benar atau Salah

Label setiap pernyataan berikut sebagai benar atau salah.

1. Himpunan bilangan prima tertutup dalam perkalian.

2. Himpunan bilangan prima tertutup dalam pejumlahan.

3. Faktor persekutuan terbesar adalah operasi biner dari Z - {0} x Z ke Z+.

4. Kelipatan paling umum adalah operasi biner dari Z - {0} x Z - {0} untuk Z+.

5. faktor persekutuan terbesar adalah unik, ketika itu ada.

6. Misalkan a dan b bilangan bulat, tidak keduanya nol, sehingga 1 = (a, b).

Kemudian terdapat x bilangan bulat dan y sedemikian rupa sehingga 1 = ax +

by dan (x, y) = 1.

7. Misalkan a dan b bilangan bulat, tidak keduanya nol, sehingga d = ax + by

untuk bilangan bulat x dan y. Kemudian d = (a, b).

8. Misalkan a dan b bilangan bulat, tidak keduanya nol, sehingga d = (a, b).

Kemudian terdapat bilangan bulat unik x dan y sedemikian rupa sehingga d =

ax + by.

9. Misalkan a dan b bilangan bulat, tidak nol keduanya. Kemudian (a, b) = (-a, b).

10. Misalkan a bilangan bulat , maka (a, a + 1) = 1.

11. Misalkan a bilangan bulat, maka (a, a + 2) = 2.

12. Jika (a, b) = 1 dan (a, c) = 1, maka (b, c) = 1.

Latihan

Dalam latihan, semua variabel merupakan bilangan bulat.

1. Daftar semua bilangan prima kurang dari 100.

2. Untuk setiap pasangan berikut, menulis a dan b dalam bentuk standar dan

menggunakan faktorisasi untuk menemukan (a, b).

a. a = 1400, b = 980

b. a = 4950, b = 10.500

18

c. a = 3780, b = 16.200

d. a = 52.920, b = 25.200

3. Dalam setiap bagian, menemukan faktor persekutuan terbesar (a, b) dan

bilangan bulat m dan n sedemikian rupa sehingga (a, b) = am + bn

a. a = 0, b = -3 b. a = 65, b = -91

c. a = 102, b = 66 d. a = 52, b = 124

e. a = 414, b = -33 f. a = 252, b = -180

g. a = 414, b = 693 h. a = 382, b = 26

i. a = 1197, b = 312 j. a = 3780, b = 1200

k. a = 6420, b = 132 l. a = 602, b = 252

m. a = 5088, b = -156 n. a = 8767, b = 252

4. Cari bilangan bulat terkecil dalam himpunan.

a. {x Z | x > 0 dan x = 4s + 6t untuk beberapa, t dalam Z}

b. {x Z| x > 0 dan x = 6s +15T untuk beberapa s, t dalam Z}

5. Buktikan bahwa jika p dan q adalah bilangan prima yang berbeda, maka

terdapat bilangan bulat m dan n sedemikian rupa sehingga pm + qn = 1.

6. Tunjukkan bahwa n2 - n + 5 adalah bilangan bulat prima ketika n = 1, 2, 3, 4

tetapi itu tidak benar bahwa n2 - n + 5 selalu bilangan bulat prima. Tuliskan

satu himpunan sama pernyataan untuk polinomial n2 - n + 11.

7. Jika a > 0 dan a|b, kemudian buktikan atau menyangkal bahwa (a, b) = a.

8. Misalkan a, b, dan c bilangan bulat sedemikian rupa sehingga a ≠ 0. Buktikan

bahwa jika a|bc maka a|c ∙ (a, b).

9. Misalkan a bilangan bulat nol dan b bilangan bulat positif . Buktikan atau

menyangkal bahwa (a, b) = (a, a + b).

10. Misalkan a|c dan b|c, dan (a, b) = 1, buktikan bahwa ab membagi c.

11. Buktikan bahwa jika d = (a, b), a|c, dan b|c, maka ab|cd.

12. Jika b > 0 dan a = bq + r, buktikan bahwa (a, b) = (b, r).

13. Misalkan r0 = b > 0. Dengan notasi yang digunakan dalam deskripsi Euclidean

Algoritma, menggunakan hasil dalam Latihan 12 untuk membuktikan bahwa

(a, b) = rn, yang bukan nol terakhir sisanya.

14. Buktikan bahwa setiap sisanya rj di Algoritma Euclidean adalah "kombinasi

linear" dari a dan b: rj = sja + tjb, untuk bilangan bulat sj dan tj.

19

15. Misalkan a dan b bilangan bulat, setidaknya salah satu dari mereka tidak 0.

Buktikan bahwa c bilangan bulat yang dapat dinyatakan sebagai kombinasi

linear dari a dan b jika dan hanya jika (a, b)|c.

16. Buktikan Corollary 2.17: Jika p adalah prima dan p|(a1a2...an), maka p

membagi beberapa aj. Petunjuk: Gunakan induksi pada n.)

17. Buktikan bahwa jika n adalah bilangan bulat positif lebih besar dari 1

sehingga n bukan prima, maka n memiliki d pembagi sedemikian rupa

sehingga 1 < d ≤ √n.18. Buktikan bahwa (ab, c) = 1 jika dan hanya jika (a, c) = 1 dan (b, c) = 1.

19. Misalkan (a, b) = 1 dan (a, c) = 1. Buktikan atau menyangkal bahwa (ac, b) =

1.

20. Misalkan (a, b) = 1. Buktikan (a, bc) = (a, c), dimana c adalah sembarang

bilangan bulat.

21. Misalkan (a, b) = 1. Buktikan (a2, b2) = 1.

22. Misalkan (a, b) = 1. Buktikan bahwa (a, bn) = 1 untuk semua bilangan bulat

positif n.

23. Buktikan bahwa jika m > 0 dan (a, b) ada, maka (ma, mb) = m ∙ (a, b).

24. Buktikan bahwa jika d = (a, b), a = a0d, dan b = b0d, maka (a0, b0) = 1.

25. Beberapa paling umum dari dua bilangan bulat bukan nol a dan b adalah

bilangan bulat m yang memenuhi semua kondisi berikut:

1. m adalah bilangan bulat positif.

2. a|m dan b|m.

3. a|c dan b|c menyiratkan m|c.

Buktikan bahwa beberapa paling umum dari dua bilangan bulat nol ada dan

unik.

26. Misalkan a dan b bilangan bulat positif. Jika d = (a, b) dan m adalah paling

umum beberapa dari a dan b, buktikan bahwa dm = ab. Perhatikan bahwa

berikut ini yang paling umum beberapa dari dua bilangan bulat yang relatif

prima positif adalah produk mereka.

27. Misalkan a dan b bilangan bulat positif. Buktikan bahwa jika d = (a, b), a =

a0d, dan b = b0d, kemudian kelipatan paling umum a dan b adalah a0b0d.

20

28. Jelaskan prosedur untuk menggunakan bentuk standar dari dua bilangan bulat

positif untuk menemukan multiple paling umum.

29. Untuk setiap pasangan bilangan bulat a, b di Latihan 2, menemukan beberapa

paling umum dari a dan b dengan menggunakan formulir standar mereka.

30. Misalkan a, b, dan c menjadi tiga bilangan bulat tidak nol.

a. Gunakan Definisi 2.11 sebagai pola untuk menentukan faktor

persekutuan terbesar dari a, b, dan c.

b. Gunakan Teorema 2.12 dan bukti sebagai pola untuk membuktikan

adanya faktor persekutuan terbesar dari a, b, dan c.

c. Jika d adalah faktor persekutuan terbesar dari a, b, dan c,

menunjukkan bahwa d = ((a,b), c).

d. Buktikan ((a, b), c) = (a, (b, c)).

31. Menemukan faktor persekutuan terbesar dari a, b, dan c dan menuliskannya

dalam bentuk ax + by + cz untuk bilangan bulat x, y, dan z.

a. a = 14, b = 28, c = 35

b. a = 26, b = 52, c = 60

c. a = 143, b = 385, c = -65

d. a = 60, b = -84, c = 105

32. Gunakan Prinsip Kedua Induksi Finite untuk membuktikan bahwa setiap

bilangan bulat positif n dapat dinyatakan dalam bentuk

n = co + c1 ∙ 3 + c2 ∙ 32 + ... + cj-1 ∙ 3j-1 + cj ∙ 3j.

dimana j adalah bilangan bulat positif, ci ∈{0, 1, 2} untuk semua i < j dan cj∈{1, 2}.

33. Gunakan fakta bahwa 2 adalah prima untuk membuktikan bahwa tidak ada

bilangan bulat bukan nol a dan b sehingga a2 = 2b2. Jelaskan bagaimana hal ini

membuktikan bahwa √2 bukan bilangan rasional.

34. Gunakan fakta bahwa 3 adalah prima untuk membuktikan bahwa tidak ada

bilangan bulat bukan nol a dan b tersebut bahwa a2 = 3b2. Jelaskan bagaimana

hal ini membuktikan bahwa √3 bukan bilangan rasional.

keterbagian, kpk & fpb

Internet