Algoritma Euclidean

·       Algoritma Euclidean adalah algoritma untuk mencari PBB dari dua buah bilangan bulat.

·       Euclid, penemu algoritma Euclidean, adalah seorang matematikawan Yunani yang menuliskan algoritmanya tersebut dalam bukunya yang terkenal, Element.

Misalkan m dan n adalah bilangan bulat tak negatif dengan

m ³ n. Misalkan r₀ = m dan r₁ = n.

Lakukan secara berturut-turut pembagian untuk memperoleh

          r₀ = r₁q₁ + r₂                 0 £ r₂ £ r₁,

          r₁ = r₂q₂ + r₃                 0 £ r₃ £ r₂,

          r_{n– 2} = r_n–1 q_n–1  + r_n      0 £ r_n £ r_n–1,

          r_n–1  = r_nq_n  + 0

Menurut Teorema 2,

          PBB(m, n) = PBB(r₀, r₁) = PBB(r₁, r₂) = … =

         PBB(r_{n– 2}, r_{n– 1})  = PBB(r_{n– 1}, r_n) = PBB(r_n, 0) = r_n

Jadi, PBB dari m dan n adalah sisa terakhir yang tidak nol dari runtunan pembagian tersebut

·       Diberikan dua buah bilangan bulat tak-negatif m dan n (m ³ n). Algoritma Euclidean berikut mencari  pembagi bersama terbesar dari m dan n.

Algoritma Euclidean

1. Jika n = 0 maka

       m adalah PBB(m, n);

       stop.

 tetapi jika n ¹ 0,

           lanjutkan ke langkah 2.

2.  Bagilah m dengan n dan misalkan r adalah sisanya.

3. Ganti nilai m dengan nilai n dan nilai n dengan nilai r, lalu ulang kembali ke langkah 1.

procedure Euclidean(input m, n : integer,                     output PBB : integer) { Mencari PBB(m, n) dengan syarat m dan n bilangan tak-negatif dan m ³ n   Masukan: m dan n, m ³ n dan m, n ³ 0   Keluaran: PBB(m, n) } Deklarasi    r : integer Algoritma:    while n ¹ 0 do       r¬m mod n       m¬n       n¬r    endwhile      { n = 0, maka PBB(m,n) = m }    PBB¬m

Contoh m = 80, n = 12 dan dipenuhi syarat m ³ n

           

Sisa pembagian terakhir sebelum 0 adalah 4, maka PBB(80, 12) = 4.                                               

·       PBB dua buah bilangan bulat a dan b dapat dinyatakan sebagai kombinasi lanjar (linear combination) a dan b dengan dengan koefisien-koefisennya.

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

Misalnya PBB(80, 12) = 4 , dan 4 = (-1) × 80 + 7 × 12.

Contoh  Nyatakan PBB(60, 18) = 6 sebagai kombinasi lanjar dari 60 dan 18.

Relatif Prima

·       Dua buah bilangan bulat a dan b dikatakan relatif prima jika PBB(a, b) = 1.

·       Contoh  20 dan 3 relatif prima sebab PBB(20, 3) = 1. Begitu juga 7 dan 11 relatif prima karena PBB(7, 11) = 1. Tetapi 20 dan 5 tidak relatif prima sebab PBB(20, 5) = 5 ¹ 1.

·       Jika a dan b relatif prima, maka terdapat bilangan bulat m dan n sedemikian sehingga

                             ma + nb = 1                                                        (2)

·       Contoh  Bilangan 20 dan 3 adalah relatif prima karena PBB(20, 3) =1, atau dapat ditulis

                             2 . 20 + (–13) . 3 = 1

dengan m = 2 dan n = –13. Tetapi 20 dan 5 tidak relatif prima karena PBB(20, 5) = 5 ¹ 1 sehingga 20 dan 5 tidak dapat dinyatakan dalam m . 20 + n . 5 = 1.