Algoritma Eucledian

• Tujuan: algoritma untuk mencari PBB dari dua buah bilangan bulat.
• Penemu: Euclides, seorang matematikawan Yunani yang menuliskan algoritmanya tersebut dalam buku, Element.

Kombinasi Lanjar

• PBB(a,b) dapat dinyatakan sebagai kombinasi lanjar (linear combination) a dan b dengan koefisien-koefisennya.
• Contoh 6: PBB(80, 12) = 4 ,

4 = (-1) × 80 + 7 × 12.

Teorema 3. Misalkan a dan b bilangan bulat positif, maka terdapat bilangan bulat m dan n sedemikian sehingga PBB(a, b) = ma + nb.

Contoh 7: Nyatakan PBB(45, 21) sebagai kombinasi lanjar dari 45 dan 21.

Solusi:

        45 = 2 (21) + 3

        21 = 7 (3) + 0

    Sisa pembagian terakhir sebelum 0 adalah 3, maka PBB(45, 21) = 3

    Substitusi dengan persamaan–persamaan di atas menghasilkan:

        3 = 45 – 2 (21)

    yang merupakan kombinasi lanjar dari 45 dan 21

Contoh 8: Nyatakan PBB (312, 70) sebagai kombinasi lanjar 312 dan 70.

Solusi: Terapkan algoritma Euclidean untuk memperoleh PBB(312, 70):

312 = 4 × 70 + 32        (i)

70 = 2 × 32 + 6        (ii)

32 = 5 × 6 + 2        (iii)

6 = 3 × 2 + 0        (iv)

Sisa pembagian terakhir sebelum 0 adalah 2, maka PBB(312, 70) = 2

Susun pembagian nomor (iii) dan (ii) masing-masing menjadi

(iii) 32 = 5.6 + 2

2 = 32 – 5 × 6    (v)

(ii) 70 = 2 . 32 + 6

6 = 70 – 2 × 32 (vi)

Sulihkan (vi) ke dalam (v) menjadi

2 = 32 – 5×(70 – 2×32)

2 = 1×32 – 5×70 + 10×32

2 = 11 × 32 – 5 × 70     (vii)

Susun pembagian nomor (i) menjadi

(i) 312 = 4 × 70 + 32

32 = 312 – 4 × 70    (viii)

Sulihkan (viii) ke dalam (vii) menjadi

2 = 11 × 32 – 5 × 70

2 = 11 × (312 – 4 × 70) – 5 × 70

2 = 11 . 312 – 49 × 70

Jadi, PBB(312, 70) = 2 = 11 × 312 – 49 × 70

Sehingga diperoleh P(a,b) = ma + n b

dimana m = 11, n = – 49 à Kombinasi Lanjar

PBB(312, 70) = 11 × 312 – 49 × 70

Contoh 9: Nyatakan PBB (128, 13) sebagai kombinasi lanjar 128 dan 13.

Solusi: Terapkan algoritma Euclidean untuk memperoleh PBB (128, 13):

128 = 9 . 13 + 11 (i)

13 = 1 . 11 + 2 (ii)

11 = 5 . 2 + 1      (iii)

2 = 2 . 1 + 0 (iv)

PBB(128, 13) = 1

Susun pembagian nomor (iii) dan (ii) masing-masing menjadi

(iii) 11 = 5 . 2 + 1

1 = 11 – 5 . 2    (v)

(ii) 13 = 1 . 11 + 2

2 = 13 – 1 . 11 (vi)

Sulihkan (vi) ke dalam (v) menjadi

1 = 11 – 5 . 2

1 = 11 – 5 (13 – 1 . 11)

1 = 1 . 11 – 5 . 13 + 5 . 11

1 = 6 . 11 – 5 . 13 (vii)

Susun pembagian nomor (i) menjadi

(i) 128 = 9 . 13 + 11

11 = 128 – 9 . 13     (viii)

Sulihkan (viii) ke dalam (vii) menjadi

(vii) 1 = 6 . 11 – 5 . 13

1 = 6 . (128 – 9 .13) – 5 . 13

1 = 6 . 128 – 54 . 13 – 5 . 13

1 = 6 . 128 – 59 . 13

Jadi, PBB (128, 13) = 1 = 6 . 128 – 59 . 13

Sehingga diperoleh P(a,b) = ma + n b

dimana m = 6, n = – 59 à Kombinasi Lanjar

PBB (128, 13) = 6 . 128 – 59 . 13

TUGAS:

Nyatakan PBB (80, 12) sebagai kombinasi lanjar 80 dan 12.

Solusi: Terapkan algoritma Euclidean untuk memperoleh PBB(80, 12):

Untuk lebih jelasnya silahkan download link berikut ini:

Terimakasih atas perhatiannya.

 

Untuk materi sebelumnya tentang Kombinatorial, silahkan Klik Disini.

Untuk materi selanjutnya tentang Kriptografi, silahkan Klik Disini.