2.
2 Faktor 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 𝑎∤𝑏.
Teorema 2.2
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
𝑥, 𝑦 ∈ ℤ
Contoh
1. Jika 𝑎|𝑏, tunjukkan bahwa (−𝑎)|𝑏, 𝑎|(−𝑏) dan
(−𝑎)|(−𝑏)
2. Tunjukkan apakah jika 𝑎|𝑏,maka 𝑎|𝑏𝑐
3. 𝑎|𝑏 jika dan hanya jika 𝑎𝑐|𝑏𝑐,dengan 𝑐 ≠ 0
Review tentang FPB
Untuk mencari FPB dari dua bilangan bulat, maka
langkah- langkah yang diperlukan adalah:
1. Tentukan faktor pembagi yang merupakan bilangan
prima (faktorisasi prima) dari masing-masing bilangan.
2. Setelah seluruh kemungkinan faktor pembagi prima
dilakukan, maka tentukan faktor pembagi prima yang
sama-sama dimiliki oleh kedua bilangan tersebut.
3. Perhatikan pangkat terkecil untuk masing-masing
faktor prima yang diperoleh.
4. FPB dari bilangan tersebut adalah perkalian faktor
prima yang sama dengan pangkat yang terkecil.
Contoh
1. Tentukan FPB dari 36 dan 90
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 faktor prima 2 adalah 1, dan
pangkat
terkecil untuk faktor prima 3 adalah 2
4. FPB dari 36 dan 90 adalah 2×32 = 18
Definisi Faktor Persekutuan Terbesar
Misalkan 𝑎, 𝑏 ∈ ℤ, dengan salah satu dari 𝑎 atau 𝑏 tidak
sama dengan nol. Faktor 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
d = fp𝑏(𝑎,𝑏) atau d = gcd(𝑎,𝑏))
Perhatikan contoh f𝑝𝑏(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,
9|36 dan 9|90 dan perhatikan bahwa 9<18
Contoh lain : Tunjukkan fpb dari masing-masing
bentuk berikut.
1. f𝑝𝑏(−5, 5) = 5
2. f𝑝𝑏(8,17) = 1
3. f𝑝𝑏(−8,−36) = 4
Definisi Relatif prima
Misalkan 𝑎, 𝑏 ∈ ℤ dengan 𝑎 ≠ 0 dan 𝑏 ≠ 0, dikatakan
relatif prima apabila f𝑝𝑏(𝑎,𝑏) =1
Sifat fp𝑏(𝑎,𝑏)
Teorema
Misalkan 𝑎, 𝑏 ∈ ℤ dengan 𝑎 ≠ 0 dan 𝑏 ≠ 0, maka
terdapat 𝑥, 𝑦 ∈ ℤ sedemikian sehingga
f𝑝𝑏(𝑎,𝑏) = 𝑎𝑥 + 𝑏𝑦
Contoh:
1. f𝑝𝑏(36,90) = 36(−2)+ 90(1)
2. f𝑝𝑏(8,17) = 8(−2) + 17(1)
3. f𝑝𝑏(−5,5) =−5(5) + 5(6)
4. f𝑝𝑏(−8,−36)=−8(4) ± 36(1)
Akibat dari FPB (𝑎,𝑏) = 𝑎𝑥 + 𝑏𝑦
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 𝑑 = FPB(𝑎,𝑏).
Akibat 2
Jika 𝑎|𝑐 dan 𝑏|𝑐, dengan FPB(𝑎,𝑏) = 1, maka 𝑎𝑏|𝑐
Latihan
1. Jika 𝑎 bilangan bulat ganjil, maka 24|𝑎(𝑎2−1)
2. Jika FPB (𝑎,𝑏) = 1 dan 𝑐|𝑎, maka FPB (𝑏,𝑐) = 1
Tugas
3. Untuk setiap 𝑎,𝑏,𝑐,𝑑 ∈ ℤ, buktikan bahwa
a. Jika 𝑎|𝑏 dan 𝑎|𝑐, maka 𝑎2|𝑏𝑐
b. Jika 𝑎|𝑏 dan 𝑐|𝑑, maka 𝑎𝑐|𝑏𝑑
4. Untuk sebarang bilangan bulat 𝑎, buktikan bahwa
2|𝑎(𝑎+1)
Algoritma Euclid
Merupakan aplikasi dari algoritma pembagian untuk mencari 𝑝𝑝𝑏.
Ilustrasi dari algoritma ini:
Misalkan 𝑎 dan 𝑏 adalah dua bilangan bulat yang memiliki pembagi
persekutuan terbesar.
Karena 𝑝𝑝𝑏(|𝑎|,|𝑏|) = 𝑝𝑝𝑏(𝑎,𝑏), maka asumsikan 𝑎 ≥ 𝑏 > 0
Langkah1. Aplikasikan algoritma pembagian, maka terdapat
bilangan bulat 𝑞1 dan 𝑟1sehingga 𝑎=𝑞1𝑏+𝑟1 dengan 0 ≤ 𝑟1< 𝑏.
Langkah2. Jika 𝑟1= 0,maka 𝑏|𝑎 dan 𝑝𝑝𝑏(𝑎,𝑏)=𝑏. Jika 𝑟1 ≠ 0, bagi 𝑏
dengan 𝑟1 untuk mendapatkan bilangan bulat 𝑞2 dan 𝑟2 yang
memenuhi 𝑏 = 𝑞2𝑟1 + 𝑟2 dengan 0 ≤ 𝑟2 < 𝑟1.
Langkah3. Jika 𝑟2 = 0 maka berhenti; jika 𝑟2 ≠ 0 maka lakukan
seperti langkah sebelumnya untuk mendapatkan 𝑟1 = 𝑞3 𝑟2 + 𝑟3
dengan 0 ≤ 𝑟3< 𝑟2.
⋮
Langkah 𝑛+1. Jika 𝑟𝑛= 0 (Langkah ini berlanjut hingga diperoleh
sisa adalah 0,atau sampai diperoleh 𝑟 = 𝑞 𝑟 + 0)
Hasil Algoritma Euclid adalah sistem persamaan berikut:
𝑎 = 𝑞1𝑏 + 𝑟1 dengan 0 ≤ 𝑟1< 𝑏
𝑏 = 𝑞2 𝑟1+𝑟2 dengan 0 ≤ 𝑟2<𝑟1
𝑟1 = 𝑞3𝑟2+ 𝑟3 dengan 0 ≤ 𝑟3< 𝑟2
⋮
𝑟𝑛−2= 𝑞𝑟𝑛−1+𝑟n dengan 0 ≤ 𝑟𝑛< 𝑟𝑛−1
𝑟𝑛−1= 𝑞𝑛+1𝑟𝑛 + 0
Dalam hal ini, 𝑟𝑛 adalah sisa terakhir yang tidak nol. Karena
itu 𝑝𝑝𝑏(𝑎,𝑏) adalah 𝑟𝑛.
Contoh1:
Gunakan algoritma Euclid untuk mencari 𝑝𝑝𝑏 dari 90 dan 36
Jawab :
Menggunakan algoritma Euclid, maka 𝑏 = 36 dan 𝑎 = 90.
Langkah1. Dengan algoritma pembagian sisa, terdapat 𝑞1 dan 𝑟1
Sehingga 90=36𝑞1+𝑟1, diperoleh 𝑞1 =2 dan 𝑟1 =18
atau 90 = (36 × 2) +18 dan 0< 18 < 36.
Langkah2. Karena 𝑟1=18, maka langkah dilanjutkan.
Bagi 36 dengan 18 untuk mendapatkan nilai 𝑞2 dan 𝑟2
yang memenuhi 36 =18𝑞2+𝑟2. Diperoleh 𝑞2 = 2 dan 𝑟2 =0.
Langkah3. Karena 𝑟2=0, berarti18|36 dan 𝑝𝑝𝑏(18, 36) =18