faktor persekutuan terbesar

Kuliah 4: Faktor Persekutuan Terbesar

Y. Hartono

FKIP Unsri

10 Oktober 2011

Y. Hartono FKIP Unsri


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 .



Definisi dan Notasi


dan b apabila

1 d |a dan d |b,


Dengan kata lain, fpb dari dua bilangan bulat adalah bilanganbulat terbesar yang dapat membagi kedua bilangan tersebut.



Definisi dan Notasi


dan b apabila

1 d |a dan d |b,


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



Contoh

Faktor dari 12 adalah {±1, ±2, ±3, ±4, ±6, ±12}.

Faktor dari 30 adalah{±1, ±2, ±3, ±5, ±6, ±10, ±15, ±30}.



Contoh



Faktor persekutuan dari 12 dan 30 adalah {±1, ±2, ±3, ±6}.



Contoh



Faktor persekutuan dari 12 dan 30 adalah {±1, ±2, ±3, ±6}.

Jadi (12, 30) = 6



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



Sifat-sifat FPB

Teorema 1(a, b) = d → (a/d , b/d) = 1.



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



Sifat-sifat FPB

Teorema 2 [Bezout](a, b) = d → ∃m, n ∈ Z ∋ am + bn = d .



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 ,



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). �



Sifat-sifat FPB

Teorema 3a = bq + r → (a, b) = (b, r).



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). �



Tentukan fpb dari 252 dan 198



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.



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.



Dengan Teorema 3, kita peroleh

(a, b) = (r0, r1) = (r1, r2) = · · · = (rn−1, rn) = (rn, 0) = rn

yang membuktikan algoritma. �



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.



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.



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)



faktor persekutuan terbesar

Documents