�ݺ�ߣ

1
SIFAT KETERBAGIAN, FAKTOR PRIMA, FAKTOR
PERSEKUTUAN TERBESAR DAN KELIPATAN
PERSEKUTUAN TERKECIL
2.3 Sifat Keterbagian
Sekarang kita beralih mempelajari sifat keterbagian bilangan bulat. Tujuan
utama kita pada bagian ini adalah untuk mendapatkan algoritma pembagian
(teorema 2.10). untuk mencapai ini, kita membutuhkan konsekuensi penting sifat
induksi , dikenal sebagai sifat terurut baik.
Teorema 2.7 Sifat Terurut Baik
Setiap himpunan tak kosong S dari bilangan bulat positif memiliki satu elemen
terkecil. Artinya ada m S sehingga m ≤ x untuk semua x S.
qp Bukti: Misalkan S himpunan tak kosong bilangan bulat positif. Jika 1 S,
maka 1 ≤ x untuk semua x S, dari teorema 2.6. Dalam kasus ini m = 1
adalah anggota terkecil dari S.
Perhatikan pada kasus dimana 1 S. dan misalkan L adalah himpunan
semua bilangan bulat positif sehingga p < x untuk semua x S, artinya
L = { p Z+
: p < x untuk semua x S},
Karena 1 S, teorema 2.6 menyakinkan kita bahwa 1 L. Kita akan
tunjukkan bahwa ada suatu bilangan positif po sehingga po L dan po + 1
L. Seandainya bukan dalam kasus ini. Kita punya p L maka p + 1 L,
dan L = Z+
dengan sifat induksi. Ini kontradiksi dengan fakta bahwa S
adalah tak kosong (Catatan bahwa L S = ). untuk itu ada po
sedemikian sehinga po L dan po + 1 L.
Kita harus menunjukkan bahwa po + 1 S. Karena po L, maka po < x
untuk semua x S, jadi po + 1 x untuk semua x S (lihat latihan 28 di
akhir bagian ini). Jika po + 1 < x adalah selalu benar, maka po + 1 akan
ada di L. Sehingga po + 1 = x untuk suatu x S, dan m = po + 1 adalah
unsur terkecil yang diinginkan di S.
Definisi 2.8 Pembagi dan Kelipatan
Misalkan a dan b adalah bilangan bulat. Kita menyebut a membagi b jika ada
bilangan bulat c sedemikian hingga b = ac.

2
Jika a membagi b, kita menulis a|b. Kita menyebut bahwa b adalah kelipatan dari
a. atau a adalah faktor/pembagi dari b. Jika a tidak membagi b, kita tulis a b.
Contoh :
1. 3|12 karena ada bilangan bulat 4 sedemikian hingga 12 = 3.4
2. karena tidak ada bilangan bulat c yang menyebabkan 7 = 2.c
3. Misal b adalah bilangan bulat tak nol maka b|0
4. Misal b adalah sebarang bilangan bulat maka
Ini dapat menjadi sebuah kejutan bahwa kita dapat menggunakan hasil untuk
membuktikan 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 a Z+
atau -a Z+
.
Kasus 1 dimana a Z+
. Ini mengakibatkan c Z+
(lihat latihan 32
bagian 2.1), jadi kita memiliki 1 ≤ a dan 1 ≤ c, dengan teorema 2.6.
Sekarang,
Andaikan 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 a
Z+
.
Kasus 2 dimana -a Z+
. Dari latihan 5 bagian 2.1, kita memiliki
(-a)(-c) = ac = 1,
Dan -a Z+
mengakibatkan –c Z+
dari latihan 32 bagian 2.1.
Karena itu, 1 ≤ -a dan 1 ≤ -c dari teorema 2.6. Sekarang
Andaikan 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 = -a
hanya mungkin ketika -a Z+
, dan kita memiliki
a = - ( -a) dari latihan 3 bagian 2.1
= - 1 karena – a = 1

3
Mengkombinasikan kasus-kasus dimana a Z+
dan -a Z+
, kita dapat
menunjukkan bahwa a = 1 atau a = -1 jika a adalah pembagi 1.
Hasil berikutnya adalah teorema dasar untuk keterbagian.
Lemma
Jika dan maka
Bukti : Misal ada c sehingga artinya dan artinya
Subtitusikan 2 persamaan tersebut sehingga
Kita ambil
karena maka
Sehingga maka atau maka
Jika maka , dan
jika maka ,
Jadi atau
Contoh Teorema 2.9
2 1 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 q
dan r yang tunggal sehingga
a = bq + r dengan 0 ≤ r < b

4
Eksistensi Bukti: Misalkan S himpunan semua bilangan bulat x yang dapat ditulis
dalam bentuk x = a – bn untuk n Z. dan misalkan lambang
himpunan semua bilangan bulat tak negatif di S atau
. himpunan S’ tak kosong. Jika 0 S’, kita memiliki a – bq = 0
untuk suatu q dan a = bq + 0. Jika 0 maka 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 dan r – b <
r, pasti benar bahwa r -b adalah negatif. berarti r – b < 0, dan r < b.
Gabungan dua kasus (dimana 0 dan dimana 0 S’), kita
memiliki
a = bq + r dan 0 ≤ r < b
Ketunggalan Untuk membuktikan q dan r adalah tunggal, misalkan a = bq1 + r1
dan a = bq2 + r2 dimana 0 ≤ r1 < b dan 0 ≤ r2 < b. Kita dapat
mengasumsikan bahwa r1 ≤ r2 tanpa kehilangan sifat umum. Ini
berarti 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 mana
kurang dari b. Untuk sebarang bilangan bulat positif n, 1 ≤ n
mengakibatkan b ≤ bn. Untuk itu, r2 - r1 = 0 dan r2 = r1. Jadi
berlaku 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 adalah
tunggal.
Secara umum, untuk sebarang a,b Z dengan 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 pembuktian
dapat ditemukan dengan mengulang pengurangan b:

5
a – b, a – 2b, a – 3b,
dan seterusnya.
Pada algoritma pembagian, bilangan bulat q disebut hasil bagi dan r
disebut sisa dalam pembagian dari a oleh b. Kesimpulan teorema mungkin lebih
dikenal dalam bentuk
b
r
q
b
a
,
Tetapi kita membatasi kerja kita disini jadi hanya bilangan bulat yang dilibatkan.
Contoh
Jika a dan b adalah dua bilangan bulat positif maka
20 = (4)(6) + (-4) tidak sesuai dengan teorema algoritma pembagian, karena
sisa (r) merupakan bilangan negatif
20 = (3)(6) + 2 sesuai dengan teorema algoritma pembagian
20 = (2)(6) + 8 tidak sesuai dengan teorema algoritma pembagian, karena
b<r
Contoh 1
Jika a dan b adalah dua bilangan bulat positif, hasil bagi q dan sisa r dapat dicari
dengan kebiasaan umum pembagian panjang (kebawah) sebagai contoh, jika a =
357 dan b = 13, dengan pembagian panjang
6
91
97
26
27
35713
Jadi q = 27 dan r = 6 pada a = bq + r, dengan 0 ≤ r < b:
357 = (13)(27) + 6
Jika a adalah negatif, sedikit penyesuaian minor dapat dibuat untuk mendapatkan
hasil pada algoritma pembagian. Dengan a = -357 dan b = 13, persamaan
sebelumnya dapat dikalikan dengan -1 untuk mendapat
-357 = (13)(-27) + (-6)

6
Untuk mendapatkan hasil dengan sisa positif, kita hanya perlu mengurangi dan
menjumlahkan 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
Perhatikan untuk bilangan -3 dan 7 terdapat bilangan -1 dan 4 sehingga
-3 = (-1)(7) + 4
dimana
Soal
1. Hal 85 no. 17
Buktikan jika ,b dan c bilangan bulat sehingga dan maka
Jawab
artinya
artinya + untuk suatu x dan y bilangan bulat
artinya
Terbukti.
2. Nomor 4 dan 8
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
-27 = q.7 + r
-27 = (-4).7 + 1 dengan
Jadi q = -4 dan r = 1

7
b. a = 512 dan b = 15
Jawab
Algoritma pembagian harus memenuhi a = bq + r dengan
512 = q.15 + r
512 = 34. 15 + 2 dengan
Jadi q = 34 dan r = 2
2.4 Faktor Prima dan Faktor Persekutuan Terbesar
Pada bagian ini, kita menetapkan adanya faktor persekutuan terbesar dari dua
bilangan bulat jika paling sedikit satu dari bilangan itu tidak nol. Teorema
Tunggal Faktorisasi, juga dikenal sebagai Teorema Fundamental dari Aritmatika.
Definisi 2.11 ■ Faktor Persekutuan Terbesar (FPB)
Sebuah bilangan bulat d adalah faktor persekutuan terbesar (FPB)dari a dan b jika
semua 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 d
dari a dan b ada ketika setidaknya salah satu dari mereka tidak nol. Bukti kita juga
menunjukkan bahwa d adalah kombinasi linear dari a dan b, yaitu, d = ma + nb
untuk bilangan bulat m dan n.
Strategi ■ Teknik pembuktian dengan menggunakan Teorema Terurut Baik
dalam Teorema 2.12 harus dibandingkan dengan yang digunakan dalam bukti
Algoritma Pembagian (Teorema 2.10).
Teorema 2.12 ■ Faktor Persekutuan Terbesar (FPB)
Misalkan a dan b bilangan bulat, paling sedikit satu dari mereka tidak 0. maka
terdapat faktor persekutuan terbesar yang tunggal d dari a dan b. Selanjutnya, d
dapat ditulis sebagai
d = am + bn
untuk bilangan bulat m dan n, dan d adalah bilangan bulat positif terkecil yang
dapat ditulis dalam bentuk ini.

8
Eksistensi Bukti:Misalkan a dan b bilangan bulat, paling sedikit satu dari mereka
tidak 0. Jika b = 0, maka a 0, sehingga > 0 . Sangat mudah untuk
melihat bahwa d = adalah faktor persekutuan terbesar dari a dan b
dalam kasus ini, dan tepat salah satu d = a (1) + b (0) atau d = a (-
1) + b (0).
Misalkan sekarang bahwa b 0. Perhatikan himpunan S adalah
himpunan semua bilangan bulat yang dapat ditulis dalam bentuk
ax + by untuk suatu x dan y bilangan bulat, dan misalkan S+
adalah
himpunan semua bilangan bulat positif dalam S. Himpunan S memuat
b = a (0) + b (1) dan - b = a (0) + b (-1), sehingga S+
tidak kosong.
Dengan Teorema Terurut Baik, S+
memiliki unsur terkecil d,
d = am + bn
Kita memiliki d positif, dan kita akan menunjukkan bahwa d adalah
faktor persekutuan terbesar dari a dan b.
Dengan Algoritma Pembagian, terdapat bilangan bulat q dan r
sehingga.
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 d
sebagai 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 + bn
adalah faktor persekutuan terbesar dari a dan b. Ini berlaku dari pilihan
d sebagai elemen terkecil S+
dimana d adalah bilangan bulat positif
terkecil yang dapat ditulis dalam bentuk ini.

9
Ketunggalan Untuk menunjukkan bahwa faktor persekutuan terbesar dari a dan b
adalah tunggal, menganggap bahwa d1 dan d2 adalah faktor persekutuan
terbesar 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 21
Bagian 2.3).
Setiap faktor persekutuan terbesar dari a dan b ada, kita akan menulis (a,
b) atau fpb(a, b) untuk menunjukkan faktor persekutuan terbesar yang tunggal
dari a dan b.
Ketika setidaknya satu dari a dan b tidak 0, bukti dari teorema terakhir
menetapkan keberadaan dari (a, b), tetapi mencari bilangan bulat positif terkecil di
S ={ax + by} bukanlah metode yang sangat mudah untuk menemukan faktor
persekutuan terbesar ini. Sebuah prosedur yang dikenal sebagai Algoritma Euclid
memoles suatu metode sistematis untuk menemukan (a, b) di mana b > 0. Hal ini
dapat juga digunakan untuk menemukan bilangan bulat m dan n sehingga (a, b) =
am + bn. Prosedur ini terdiri dari aplikasi berulang dari Algoritma Pembagian
menurut pola berikut, dimana a dan b adalah bilangan bulat dengan b > 0.
Algoritma Euclid
a = bq0 + r1, 0 r1 < b
b = 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 bilangan
bulat 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 menjadi
faktor persekutuan terbesar dari a dan b. Bukti dari pernyataan ini yang tersisa
sebagai latihan.
Sebagai contoh, kita akan menemukan faktor persekutuan terbesar dari
1492 dan 1776.
Contoh 1
Dengan Melakukan aritmatika untuk Algoritma Euclid, kita memperoleh

10
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) + 0 (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 untuk
menemukan bilangan bulat m dan n sehingga
(a, b) = am + bn
Kita dapat memperoleh bilangan bulat dengan menyelesaikan untuk sisa tidak nol
terakhir dan mengganti sisanya dari persamaan sebelumnya berturut-turut sampai
a dan b yang hadir dalam persamaan. Sebagai contoh, sisanya dalam contoh 1
dapat dinyatakan sebagai
284 = (1776)(1) + (1492)(-1)
72 = (1492)(1) + (284)(-5)
68 = (284)(1) + (72)(-3)
4 = (72)(1) + (68)(-1).
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, dan
kami dengan hati-hati menghindari melakukan perkalian yang melibatkan sisanya.

11
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 sedemikian
sehingga
(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.
Lemma
Misalkan a dan b bilangan bulat, (a, b) = 1 , .
Bukti : (a, b) = 1 berdasarkan teorema 2.12 maka sehingga
misalkan , dan
dan
Karena dan maka dan sehingga
Karena dan maka , dan
maka sehingga
Definisi 2.13 ■ Bilangan Bulat Relatif Prima
Dua bilangan bulat a dan b adalah relatif prima jika faktor persekutuan
terbesarnya adalah 1.
Dalam dua bagian berikutnya dari bab ini, kita membuktikan beberapa
hasil yang menarik tentang bilangan bulat yang relatif prima dengan bilangan
bulat 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.
(p Bukti: Asumsikan bahwa (a, b) = 1 dan a|bc. karena (a, b) = 1,
terdapat bilangan bulat m dan n sehingga 1 = am + bn, berdasarkan

12
Teorema 2.12. karena a|bc, maka 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 sejumlah faktor paling sedikit
yang mungkin. 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 bahwa
p 1. Pengecualian 1, dari himpunan bilangan prima memungkinkan pernyataan
Teorema Faktorisasi Ketunggalan. Sebelum menggali itu, kita membuktikan sifat
penting 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" Pernyataan
seperti ini adalah dengan mengasumsikan bahwa satu bagian (seperti r) tidak
diperoleh, dan menggunakan asumsi ini untuk membantu membuktikan bahwa
bagian lain kemudian harus diperoleh.
Teorema 2.16 ■ Lemma Euclid †
Jika p adalah prima dan p|ab, maka 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 dan
p. Kemudian Teorema 2.14 mengakibatkan bahwa p|b. Jadi p|b
jika p tidak membagi a, dan teorema adalah benar dalam kasus
apapun.
Akibat generalisasi Teorema 2.16 untuk hasil dengan lebih dari dua
faktor. Buktinya diminta dalam latihan. Sebuah akibat langsung dari konsekuensi
ini adalah bahwa jika p prima dan p|an
, maka p|a.
Corollary 2.17 ■
Jika p prima dan p|(a1a2...an), maka p membagi suatu aj.

13
Hal ini membawa kita ke Teorema Faktorisasi Ketunggalan, berakibat
penting sehingga itu sering disebut Teorema Dasar Aritmatika.
Strategi ■ Perhatikan bukti bagian ketunggalan Teorema 2.18: Dua faktorisasi
diasumsikan, dan kemudian dibuktikan bahwa keduanya adalah sama.
Teorema 2.18 ■ Teorema Faktorisasi Ketunggalan
Setiap bilangan bulat positif n adalah salah satu yaitu 1 atau yang dapat
dinyatakan sebagai perkalian dari bilangan bulat prima, dan faktorisasi ini adalah
tunggal kecuali untuk urutan factor-faktornya.
Menyelesaikan dengan Induksi
Bukti:
Dalam pernyataan dari teorema, perkalian digunakan dalam arti diperluas:
perkalian mungkin hanya memiliki satu faktor.
Misalkan Pn adalah pernyataan yg berlaku salah satu yaitu n = 1 atau n
dapat dinyatakan sebagai perkalian dari bilangan prima. Kita akan
membuktikan bahwa Pn adalah benar untuk semua n Z+
oleh Prinsip
Kedua Induksi Terbatas (Finite).
Sekarang jelas bahwa P1 benar. Asumsikan bahwa Pm benar untuk semua
bilangan bulat positif m < k. Jika k adalah prima, maka k merupakan
perkalian dengan satu faktor prima, dan Pk benar. Misalkan k bukan prima.
Maka k = ab, di mana a atau b kedua-duanya bukanlah 1. Oleh karena itu,
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. Faktorisasi ini memberikan
k = 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 positif
n.
Ketunggalan
Untuk 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,

14
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 adalah
bilangan 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 menghapus
satu faktor pi dengan masing-masing penerapan hukum kanselasi, sampai
kita memperoleh
pt = qt ... qv.
Karena faktor positif dari pt hanyalah 1 dan pt, dan karena setiap qj adalah
prima, ini berarti bahwa harus ada hanya satu qj di sebelah kanan
persamaan, dan itu adalah qt. Artinya, v = t dan qt = pt. Ini melengkapi
bukti.
Teorema Faktorisasi Ketunggalan dapat digunakan untuk menggambarkan
bentuk standar dari bilangan bulat positif n. Misalkan p1, p2, ... , pr adalah faktor
prima yang berbeda dari n, diatur dalam urutan besarnya sehingga
p1 < p2 < ... < pr.
Kemudian semua faktor berulang dapat dikumpulkan bersama dan diekspresikan
dengan menggunakan eksponen untuk menghasilkan
n = ...
dimana mi adalah bilangan bulat positif. Setiap mi disebut multiplisitas dari pi,
dan faktorisasi ini dikenal sebagai bentuk standar untuk n.
Contoh 3 Bentuk standar untuk dua bilangan bulat positif a dan b dapat
digunakan untuk menemukan faktor persekutuan terbesar (a, b) dan beberapa
faktor persekutuan. 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 prima
yang sama, dengan masing-masing faktor persekutuan pangkat paling kecil yang
muncul dalam faktorisasi:
(a, b) = 23
32
7 = 504.
■

15
Dari satu sudut pandang, Teorema Faktorisasi Ketunggalan mengatakan
bahwa bilangan bulat prima sedang membangun blok untuk bilangan bulat,
dimana "bangunan" yang dilakukan dengan menggunakan perkalian dan
membentuk hasil. Sebuah pertanyaan alami, yaitu: Berapa banyak blok? dari
Teorema berikutnya menyatakan jawaban yang diberikan oleh ahli matematika
Yunani kuno Euclid-yang jumlah bilangan prima adalah tak terhingga. Bukti ini
adalah penghargaan ke Euclid.
Teorema 2.19 ■ Teorema Euclid pada Bilangan Prima
Banyaknya bilangan prima adalah tak terhingga
Kontradiksi Bukti:Andai ada sejumlah n bilangan-bilangan prima. Misalkan n
bilangan prima ini yang dapat dilambangkan oleh p1, p2, ..., pn,
dengan memperhatikan bilangan bulat
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. Dengan
demikian ada dua kemungkinan: Salah satu m itu sendiri merupakan
prima, atau memiliki faktor prima yang berbeda dari setiap satu pi
tersebut. Dalam kedua kasus, kita memiliki sebuah bilangan bulat
prima yang tidak berada dalam daftar p1, p2, ... , pn. Oleh karena itu,
ada lebih 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)| b, maka (a,b)| a + b.
Selanjutnya (a,b)|a dan (a,b)|a+ b maka (a,b) adalah faktor persekutuan
dari a dan 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 faktor
persekutuan dari a dan b dengan demikian (a, a + b)|(a,b).
Terbukti.

18
Jadi
3. Misal dengan dengan . Pada konsep FPB
berlaku namun hal ini tidak berlaku pada KPK.
Jadi .
Sebagai contoh ambil maka
sehingga
dan
Jadi
Latihan Soal 2.3 dan 2.4
1. Halaman 85 no. 6,10 dan 12
Temukan q dan r sehingga memenuhi kondisi Algoritma Pembagian
a.
b.
c.
Jawab :
Algoritma pembagian harus memenuhi dengan
a. 1205 = (37)q+ r
1205 = (37)(32)+ 21 dengan
b. -921 = (18)q+ r
921 = (18)(51)+ 3
-921 = (18)(-51)+ (-3)
-921 = (18)(-51)+(-18)+ 18 + (-3)
-921 = (18)(-52)+ 15 dengan
c. 15 = (512)q+ r
15 = (512)(-1)+ 497 dengan
Jadi q = -1 dan r = 497

19
2. Hal 85 no.19
Misal dan n adalah bilangan bulat maka dan . Buktikan
Jawab :
Karena dan maka dan
Karena dan maka )
Karena dan maka ) = )
Terbukti.
3. Hal 85 no.20
Misal dan d adalah bilangan bulat maka dan . Buktikan
.
Jawab :
Karena , dan karena
Karena
Terbukti.
4. Hal 85 no.22
Buktikan jika adalah bilangan bulat sedemikian hingga dan
maka
Jawab :
Karena sehingga
Karena maka
Sehingga diperoleh
Karena c maka
Sehingga
Jadi terbukti.
5. Hal 93 no.2
Untuk setiap pasangan berikut, tulislah a dan b dalam bentuk standar dan
menggunakan faktorisasi untuk menemukan (a, b).
a.
b.
c.
Jawab :
a.
(1400,980) =
(1400,980) = 140

20
b.
(4950,10500) =
(4950,10500) = 150
c.
(3780,16200) =
(4950,10500) = 540
6. Halaman 93 no.3
Tentukan faktor persekutuan terbesar (a, b) dan bilangan bulat m dan n
sedemikian sehingga (a, b) = am + bn
a.
Jawab :
Dengan menggunakan algoritma Euclid
Jadi (124,52) = 4
Dengan mengganti sisanya dari persamaan sebelumnya berturut-turut
diperoleh
Jadi sedemikian sehingga

21
b.
Jawab :
Jadi (252,-180) = 36
diperoleh
c.
Jawab :
Jadi (414,-33) = 3
diperoleh

22
7. Latihan Halaman 94 no.8
Misalkan a, b, dan c bilangan bulat sedemikian rupa sehingga a 0.
Buktikan bahwa jika maka
Jawab
Misalkan maka atau
i) Jika maka sedemikian hingga
Karena maka
ii) Jika maka
Dari i) dan ii) terbukti jika maka
Misalkan a|c dan b|c, dan (a, b) = 1, buktikan bahwa ab membagi c
Jawab
Karena maka sedemikian hingga
Karena maka
Terbukti.
Buktikan bahwa jika dan , maka
Jawab :
(terbukti)

24
Latihan 2.4
Benar atau Salah
Labeli setiap pernyataan berikut sebagai benar atau salah.
1. Himpunan bilangan prima tertutup terhadap perkalian.
2. Himpunan bilangan prima tertutup terhadap 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, jika 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, tulislah a dan b dalam bentuk standar dan
menggunakan faktorisasi untuk menemukan (a, b).
a. a = 1400, b = 980
b. a = 4950, b = 10.500
c. a = 3780, b = 16.200
d. a = 52.920, b = 25.200

25
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.
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.

26
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
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.
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.

27
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 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 bukan bilangan rasional.

28
KETERBAGIAN, FAKTOR PRIMA, FAKTOR
PERSEKUTUAN TERBESAR (FPB) DAN KELIPATAN
PERSEKUTUAN TERBESAR (KPK)
Makalah
Untuk Memenuhi Tugas Mata Kuliah Matematika 2
Dosen Pengampu: Dr. Santi Irawati, M.Si
Oleh:
Abd Gafur NIM 130311818899
Erna Gunawati NIM 130311818882
Eva Maryana NIM 130311818884
UNIVERSITAS NEGERI MALANG
PASCASARJANA
PROGRAM STUDI PENDIDIKAN MATEMATIKA
MARET 2014

�ݺ�ߣ

Kel 1 bilangan

Convert to study guideBETA

More Related Content

Kel 1 bilangan