faktor persekutuan terbesar
Post on 04-Jan-2016
856 Views
Preview:
TRANSCRIPT
Kuliah 4: Faktor Persekutuan Terbesar
Y. Hartono
FKIP Unsri
10 Oktober 2011
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Definisi dan Notasi
DefinisiBilangan bulat d disebut faktor persekutuan terbesar (fpb) dari a
dan b apabila
1 d |a dan d |b,
2 jika c |a dan c |b, maka c ≤ d .
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Definisi dan Notasi
DefinisiBilangan bulat d disebut faktor persekutuan terbesar (fpb) dari a
dan b apabila
1 d |a dan d |b,
2 jika c |a dan c |b, maka c ≤ d .
Dengan kata lain, fpb dari dua bilangan bulat adalah bilanganbulat terbesar yang dapat membagi kedua bilangan tersebut.
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Definisi dan Notasi
DefinisiBilangan bulat d disebut faktor persekutuan terbesar (fpb) dari a
dan b apabila
1 d |a dan d |b,
2 jika c |a dan c |b, maka c ≤ d .
Dengan kata lain, fpb dari dua bilangan bulat adalah bilanganbulat terbesar yang dapat membagi kedua bilangan tersebut.
Kita menggunakan notasi (a, b) untuk fpb dari a dan b.Jadi, jika d adalah fpb dari a dan b, maka d = (a, b).
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Contoh
Faktor dari 12 adalah {±1, ±2, ±3, ±4, ±6, ±12}.
Faktor dari 30 adalah{±1, ±2, ±3, ±5, ±6, ±10, ±15, ±30}.
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Contoh
Faktor dari 12 adalah {±1, ±2, ±3, ±4, ±6, ±12}.
Faktor dari 30 adalah{±1, ±2, ±3, ±5, ±6, ±10, ±15, ±30}.
Faktor persekutuan dari 12 dan 30 adalah {±1, ±2, ±3, ±6}.
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Contoh
Faktor dari 12 adalah {±1, ±2, ±3, ±4, ±6, ±12}.
Faktor dari 30 adalah{±1, ±2, ±3, ±5, ±6, ±10, ±15, ±30}.
Faktor persekutuan dari 12 dan 30 adalah {±1, ±2, ±3, ±6}.
Jadi (12, 30) = 6
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Sifat-sifat FPB
Kira akan membuktikan tiga sifat berikut:
1 (a, b) = d → (a/d , b/d) = 1.
2 (a, b) = d → ∃m, n ∈ Z ∋ am + bn = d .
3 a = bq + r → (a, b) = (b, r).
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Sifat-sifat FPB
Teorema 1(a, b) = d → (a/d , b/d) = 1.
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Sifat-sifat FPB
Teorema 1(a, b) = d → (a/d , b/d) = 1.
Bukti. Misalkan a dan b adalah bilangan bulat dengan (a, b) = d .Kita akan menunjukkan bahwa a/d dan b/d tidak memiliki faktorpersekutuan lain kecuali 1. Misalkan e ∈ Z
+ adakah faktorpersekutuan dari a/d dan b/d , yaitu e|(a/d) dan e|(b/d) sehinggaada k, ℓ ∈ Z sehingga a/d = ke dan b/d = ℓe, atau a = dek danb = deℓ. Jadi kita lihat bahwa de adalah faktor persekutuan dari a
dan b. Tetapi, karena d adalah faktor persekutuan terbesar, makade ≤ d sehingga e = 1. �
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Sifat-sifat FPB
Teorema 2 [Bezout](a, b) = d → ∃m, n ∈ Z ∋ am + bn = d .
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Sifat-sifat FPB
Teorema 2 [Bezout](a, b) = d → ∃m, n ∈ Z ∋ am + bn = d .
Bukti. Misalkan S adalah himpunan semua kombinasi linier dari a
dan b; yaituS = {am + bn|m, n ∈ Z}.
S tak kosong sebab a = a × 1 + b × 0 dan b = a × 0 + b × 1 dankarenanya a, b ∈ S . Jadi S berisi bilangan bulat positif elementerkecil, sebut saja d = ax + by . Akan dibuktikan bahwad = (a, b). Menurut algoritma pembagian,
a = dq + r , 0 ≤ r < d ,
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
sehingga diperoleh
r = d − dq
= a − (ax + by)q
= a(1 − qx) + b(−qy).
Ini menunjukkan bahwa r ∈ S sedangkan 0 ≤ r < d dan d adalahbilangan bulat positif terkecil dalam S . Jadi r = 0 dan d |a.Dengan cara yang sama dapat pula ditunjukkan bahwa d |b.Selanjutnya, jika c |a dan c |b, maka c |ax + by = d . Hal inimembuktikan bahwa d = (a, b). �
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Sifat-sifat FPB
Teorema 3a = bq + r → (a, b) = (b, r).
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Sifat-sifat FPB
Teorema 3a = bq + r → (a, b) = (b, r).
Bukti.Di sini cukup ditunjukkan bahwa a, b, dan r memiliki faktorpersekutuan yang sama. Untuk itu, misalkan k|a dan k|b, makak|a − bq = r . Selanjutnya, misalkan ℓ|b dan ℓ|r , makaℓ|bq + r = a. Ini berarti, semua faktor persekutuan dari a dan b
juga merupakan faktor persekkutuan dari b dan r , termasuk faktorpersekutuan terbesarnya, yaitu (a, b) = (b, r). �
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Tentukan fpb dari 252 dan 198
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Algoritma Euclid
Misalkan r0 = a dan r1 = b dengan a ≥ b > 0. Jika penggunaanalgoritma pembagian secara beruntun menghasilkanrj = rj+1qj+1 + rj+2 dengan 0 < rj+2 < rj+1 untukj = 0, 1, 2, . . . n − 2 dan rn+1 = 0, maka (a, b) = rn, sisa terakhiryang tidak nol.
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Bukti Algoritma Euclid
Misalkan r0 = a dan r1 = b dengan a ≥ b, algoritma pembagianmemberikan
r0 = r1q1 + r2, 0 ≤ r2 < r1,
r1 = r2q2 + r3, 0 ≤ r3 < r2,...
rj−2 = rj−1qj−1 + rj , 0 ≤ rj < rj−1,
...
rn−3 = rn−2qn−2 + rn−1, 0 ≤ rn−1 < rn−2,
rn−2 = rn−1qn−1 + rn, 0 ≤ rn < rn−1,
rn−1 = rnqn.
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Dengan Teorema 3, kita peroleh
(a, b) = (r0, r1) = (r1, r2) = · · · = (rn−1, rn) = (rn, 0) = rn
yang membuktikan algoritma. �
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Contoh
Faktor persekutuan terbesar dari 252 dan 198 dapat dicari dengancara berikut.
252 = 1 × 198 + 54
198 = 3 × 54 + 36
54 = 1 × 36 + 18
36 = 2 × 18 + 0.
Jadi (252,198)=18.
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Menurut teorema Bezout, ada bilangan bulat x dan y sehingga252x + 198y = 18. Perhatikan bahwa
18 = 54 − 1 × 36
= 54 − 1 × (198 − 3 × 54)
= 4 × 54 − 1 × 198
= 4 × (252 − 1 × 198) − 1 × 198
= 4 × 252 − 5 × 198
= 252 × 4 + 198 × (−5).
Jadi, x = 4 dan y = −5.
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
Latihan
Gunakan algoritma Euclid untuk mencari fpb dari pasanganbilangan berikut:
1 666 dan 1414
2 20758 dan 44350
Carilah bilangan bulat x dan y sehingga
1 666x + 1414y = (666, 1414)
2 20758x + 44350y = (20758, 44350)
Y. Hartono FKIP Unsri
Kuliah 4: Faktor Persekutuan Terbesar
top related