Faktor Persekutuan Terbesar (FPB) dan Algoritma Euclid

1. Faktor Persekutuan dan Faktor Persekutuan Terbesar

A. Faktor Persekutuan

Suatu bilangan bulat d adalah factor persekutuan dari a dan b bila dan hanya bila d | a dan d | b.

B. Faktor Persekutuan Terbesar (FPB)

Bila a dan b bilangan-bilangan bulat yang tidak nol. d adalah factor persekutuan terbesar (FPB) dari a dan b, dituliskan (a, b) bila dan hanya bila:

(i) d > 0

(ii) d | a dan d | b

(iii) Jika c | a dan c | b maka c ≤ d

Syarat (i) & (ii) menyatakan bahwa d adalah faktor persekutuan dari a dan b.

Syarat (iii) menyatakan bahwa d adalah faktor persekutuan terbesar (FPB).

C. Simbol Untuk FPB

Misal FPB dari a dan b adalah d, dapat dituliskan (a, b) = d.

2. Relatif Prima (Koprim)

A. Relatif Prima

Jika (a, b) = 1 maka a dan b adalah dua bilangan bulat prima relatif (saling koprim).

Contoh:

Faktor dari 9 dan 14 adalah {1, 3, 9} ∩ {1, 2, 7, 14} = {1}

Sehingga (9, 14) = 1, dengan kata lain, 9 dan 14 koprim.

B. Membuat koprim

Jika (a, b) = d maka (a/d, b/d) = 1

Bukti:

Misalkan (a/d, b/d) = c maka c ≥ 1 dan c | (a/d) dan c | (b/d)

c | (a/d) maka ada bilangan bulat m sehingga (a/d) = mc atau a = mcd

c | (b/d) maka ada bilangan bulat n sehingga (b/d)= nc atau b = ncd

Karena a = mcd dan b = ncd maka cd adalah faktor persekutuan dari a dan b.

Karena (a, b) = d maka cd ≤ d yaitu c ≤1, sebab d suatu bilangan bulat positif

Karena c ≥ 1 dan c ≤ 1 maka c = 1 ∎

3. Algoritma Euclid

Algoritma Euclid dirumuskan sebagai berikut: 

Misalkan akan dicari faktor persekutuan terbesar (FPB) dari bilangan bulat a dan b. Karena (|a|, |b|) =  (a, b) dan misalkan a ≥ b > 0.

Langkah pertama menerapkan algoritma pembagian terhadap a dan b diperoleh:

a = q₁b + r₁,     0 ≤ r₁ < b

Jika terjadi r₁ = 0. maka b | a dan  (a, b) = b. Jika r₁ ≠ 0, bagilah b oleh r₁ dan diperoleh q₂ dan r₂ yang memenuhi:

b = q₂r₁ + r₂,    0  ≤ r₂ < r₁ 

Jika r₂ = 0, maka berhenti, sebaliknya jika r₂  ≠ 0 dengan cara yang sama diperoleh, 

r₁ = q₃r₂ + r₃,    0 ≤ r₃ < r₂ 

Proses pembagian ini dilanjutkan sampai sisa pembagian nol, katakanlah pada langkah ke (n + 1) yang mana r_n-1 dibagi r_n dengan b >  r₁  >  r₂  > … ≥ 0. 

Proses di atas menghasilkan sistem persamaan berikut:

a = q₁b + r₁                                               0  ≤  r₁ < b 

b = q₂r₁ + r₂                                              0  ≤  r₂ < r₁ 

r₁ = q₃r₂ + r₃                                             0  ≤  r₃ < r₂ 

⋮

r_n-2 = q_nr_n-1 + r_n                                       0 ≤  r_n < r_n-1 

r_n-1 = q_n+1r_n + 0 

Sisa pembagian yang terakhir yang bukan nol r_n = (a, b).

4. Substitusi Balik Algoritma Euclid

Apabila a dan b bilangan-bilangan bulat tidak nol, maka ada bilangan-bilangan bulat x dan y sedemikian sehingga  ax + by =  (a, b)

Untuk menentukan x dan y yang memenuhi (a, b) = ax + by adalah dengan substitusi balik algoritma Euclid.

r_n =  (a, b) dinyatakan sebagai kombinasi linear dari a dan b. 

Contoh Soal

1. Buktikan bahwa: Jika a | b dan a > 0 maka (a, b) = a

Bukti :

Misalkan (a, b) = c, berarti c | a dan c | b (c ≤ a dan c ≤ b)

a | a dan a | b maka a ∈ factor dari a dan b, ditulis a ∈ F(a, b), dengan c ≤ a

Karena c ≤ a dan a ∈ F(a, b), FPB dari a dan b atau (a, b) = a. ∎

2. Buktikan bahwa (a, b) = (a + b, b)

Bukti:

Misalkan (a, b) = d maka d | a dan d | b. 

Berdasarkan sifat linearitas pembagian habis, yaitu: d | a dan d | b maka d | (a + b)

karena:  d | (a + b) maka d adalah faktor dari a + b dan b

              d ∈ F(a + b, b).

Ambil sebarang c ∈ F(a + b, b) maka c | (a + b) dan c | b.

Berdasarkan sifat linearitas pembagi habis, yaitu :

c | (a + b) dan c | b maka  c | a

Karena c | a dan c | b maka  c ∈ F (a, b) dan (a, b) = d  maka  c ≤ d. 

Sedangkan, c ∈ F(a +b, b) maka d = (a + b, b) ∎

Tambahan:

Teorema ini dapat diperluas menjadi (a, b) = (a + kb, b), ∀k ∈ Z

Untuk k positif: (a, b) = (a + b, b) = (a + 2b, b) = ... = (a + kb, b)

Untuk k negatif: (a, b) = (a − b, b) = (a − 2b, b) = ... = (a + kb, b)

Dari teorema inilah, diperoleh ide Algoritma Euclid, dimana:

Jika b = aq + r maka (b, a) = (a, r)

(a, b) = (b, r₁) = (r₁, r₂) = … = (r_n-1, r_n) = (r_n, 0) = r_n 

3. Buktikan bahwa ((a, b), b) = (a, b)

Bukti :

Misalkan ((a, b), b) = c, berarti c | (a, b) dan c | b (c ≤ (a, b) dan c ≤ b)

(a, b) | (a, b) dan (a, b) | b maka (a, b) ∈ factor dari a dan b, ditulis (a, b) ∈ F((a, b), b), dengan c ≤ (a, b)

Karena c ≤ (a, b) dan (a, b) ∈ F((a, b), b), FPB dari (a, b) dan b atau ((a, b), b) = (a, b). ∎

4. Tentukan (10587, 534) dan tentukan kombinasi linear 10587x + 534y = (10587, 534)

10587 = 534.19 + 441

534 = 441.1 + 93

441 = 93.4 + 69

93 = 69.1 + 24

69 = 24.2 + 21

24 = 21.1 + 3

21 = 3.7 + 0

Sehingga diperoleh (10587, 534) = 3

Selanjutnya,

3 = 24 − 21.1

= 24 − (69 − 24.2)

= 24.3 − 69

= (93 − 69).3 − 69

= 93.3 − 69.4

= 93.3 − (441 − 93.4).4

= 93.19 − 441.4

= (534 − 441.1).19 − 441.4

= 534.19 − 441.23

= 534.19 − (10587 − 534.19).23

= 534.456 − 10587.23

Jadi, FPB dari 10587 dan 534 adalah 3, sedangkan nilai x dan y yang memenuhi 10587x + 534y = 3 adalah x = −23 dan y = 456.

5. Tentukan FPB dari 1587645 dan 6755

1587645 = 6755.235 + 220

6755 = 220.30 + 155

220 = 155.1 + 65

155 = 65.2 + 25

65 = 25.2 + 15

25 = 15.1 + 10

15 = 10.1 + 5

10 = 5.2 + 0

Jadi, FPB dari 1587645 dan 6755 adalah 5.

6. Buktikan bahwa: Jika (a, b) = 1 dan c | a, maka (c, b) = 1

Bukti:

Diket bahwa (a, b) = 1

Ingat kembali bahwa: Jika (a, b) = 1 maka (∃x, y ∈ Z) ∋ ax + by = 1 (i)

c | a berarti ∃k ∈ Z ∋ a = ck (ii)

Sehingga diperoleh:

ax + by = 1

(ck)x + by = 1

c.(kx) + by =1

Dkl (c, b) = 1 ∎

7. Buktikan bahwa ∀ bil bulat positif m, berlaku (ma,mb) = m(a,b)

Berdasarkan teorema bahwa bila a dan b adalah bil bulat tak nol maka ∃ bil bulat m dan n yg memenuhi am + bn = (a,b)

Misal (ma, mb) = d, maka

(ma)p + (mb)q = d, (∃p, q ∈ Z)

m(ap) + m(bq) = d

m(ap + bq) = d

Sehingga, d = m(ap + bq) = m(a, b)

Dkl (ma, mb) = m(a, b) ∎

8. Buktikan bhw setiap faktor persekutuan dari dua bil bulat mrp faktor dari FPB dua bil bulat tsb!

Misalkan dua bil bulat tsb a dan b, dengan (a, b) = d

Misalkan pula, m suatu faktor persekutuan dari a dan b, maka hrs dibuktikan bhw m | d

Krn (a, b) = d, maka ∃ bil bulat x dan y ∋ 𝑎𝑥 + 𝑏𝑦 = 𝑑

Dan krn m adl faktor persekutuan dari a dan b maka m | a dan m | b shg m | ax dan m | by

Hal ini berakibat, m | (ax + by) atau m | d ∎

9. Dengan Algoritma Euclides, tentukan (5767, 4453)

5767 = 4453.1 + 1314

4453 = 1314.3 + 511

1314 = 511.2 + 292

511 = 292.1 + 219

291 = 219.1 + 73

219 = 73.3 + 0

Jadi (5767, 4453) = 73

10. Buktikan bahwa jika (a, b) = 1 dan c | (a + b) maka (a, c) = (b, c) = 1

Misal:

(a, c) = d, berarti d | a dan d | c

(b, c) = e, berarti e | b dan e | c

Perhatikan

d | c dan c | (a + b), maka d | (a + b)

e | c dan c | (a + b), maka e | (a + b)

Perhatikan

d | a dan d | (a + b), maka d | b

e | b dan e | (a + b), maka e | a

Perhatikan

d | a dan d | b, sedangkan (a, b) = 1, sehingga diharuskan d = 1

e | a dan e | b, sedangkan (a, b) = 1, sehingga diharuskan e = 1

Ini berarti d = e = 1. Dengan kata lain, (a, c) = (b, c) = 1 ∎

11. Buktikan bahwa: Jika a | c dan b | c dan (a, b) = 1 maka ab | c

Bukti :

Karena (a, b) = 1, maka ada bilangan bulat x dan y sehingga ax + by = 1

Kedua ruas kita kalikan dengan c, diperoleh acx + bcy = c ...(i)

Karena a | c dan b | c maka terdapat bil bulat r dan t sehingga c = ar dan c = bt

Substitusi ke (i) diperoleh

abtx + abry = c

ab(tx + ry)  = c

Jadi, ab | c ∎

12. Buktikan bahwa: Jika a | bc dan (a, b) = 1 maka a | c

Bukti :

Karena (a, b) = 1, maka ada bilangan bulat x dan y sehingga ax + by = 1

Kedua ruas kita kalikan dengan c, diperoleh acx + bcy = c ...(i)

Karena a | bc dan a | ac  maka  a | (acx + bcy)

Dengan kata lain, a | c ∎