Algoritma Eucledian

Posted on Updated on

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

 

 

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google+

You are commenting using your Google+ account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s