Pengertian Algoritma Euclid - Teori Bilangan

Algoritma euclid merupakan suatu algoritma yang digunakan untuk mencari Greatest Common Divisor (GCD) atau biasa dikenal dengan Faktor Persekutuan Terbesar (FPB) dari dua bilangan, khususnya untuk bilangan-bilangan yang sangat besar sehingga tidak perlu mencari faktorisasi prima dari kedua bilangan tersebut. Algoritma euclid ini biasanya diperkenalkan kepada mahasiswa yang sedang mempelajari mata kuliah teori bilangan tetapi tidak jarang juga soal-soal olimpiade matematika dan ujian universitas membutuhkan cara ini untuk menyelesaikan soal yang diberikan. Oleh karena itu Istana Matematika ingin menjelaskan tentang pengertian dari algoritma yang menarik ini - Algoritma Euclid.

Pengertian Algoritma Euclid - Teori Bilangan

Teorema Algoritma Euclid
Misalkan a dan b adalah dua bilangan bulat dengan syarat b > 0. Jika a dibagi dengan b maka terdapat dua buah bilangan bulat lainnya, yaitu h (hasil bagi) dan s (sisa), sedemikian sehingga:

a = h \times b + s

dengan 0 \leqslant s < b.

Contoh: Jika 16 dibagi dengan 7 akan memberikan hasil bagi 2 dan sisa 2, sedemikian sehingga:

16 = 2 \left(7 \right) + 2

Teorema Algoritma Euclid atau Teorema Algoritma Euclidean ini yang digunakan untuk membentuk rumus umum dari Polinomial (Suku Banyak). Kalian bisa tonton video dibawah ini:

Klik tautan ini jika video di atas tidak muncul.

Tetapi kita tidak sedang membahas polinomial ya. Kita kembali lagi ke algoritma euclid untuk mencari faktor persekutuan terbesar.

Mencari Faktor Persekutuan Terbesar (FPB) menggunakan Algoritma Euclid

Dari teorema 1, diperoleh sifat dari FPB, yaitu FPB \left( {a,b} \right) = FPB \left( {b,s} \right) atau bisa ditulis \left( {a,b} \right) = \left( {b,s} \right). Untuk pembuktiannya kalian bisa cari FPB dari 16 dan 7 serta FPB dari 7 dan 2 dengan cara sederhana yaitu faktorisasi prima. Diperoleh \left( {16,7} \right) = \left( {7,2} \right) = 1.

Dengan sifat FPB tersebut, kita bisa terapkan algortima euclid berulang, yaitu:
a=hb+{s_1}                                        0 \leqslant s_{1} < b

b={h_1}{s_1}+{s_2}                                    0 \leqslant s_{2} < s_{1}

{s_1}={h_2}{s_2}+{s_3}                                 0 \leqslant s_{3} < s_{2}

 \vdots

{s_\left(n-2 \right)}={h_\left(n-1 \right)}{s_\left(n-1 \right)}+{s_n}         0 \leqslant s_n < {s_\left(n-1 \right)}

{s_\left(n-1 \right)}={h_n}{s_n}+0

Maka, \left( {a,b} \right) = \left( {b,s_1} \right)= \left( {s_1,s_2} \right) = \ldots = \left( {s_\left(n-2 \right),s_\left(n-1 \right)} \right) = \left( {s_\left(n-1 \right),s_n } \right) = {s_n} .

Jadi FPB dari dan adalah sisa terakhir yang bernilai tidak nol atau sama dengan hasil bagi terakhir yang bersisa nol.

Catatan: Variabel s pada persamaan a=hb+s diubah menjadi s_{1} agar memudahkan pemahaman tentang algoritma berulang di atas.

Untuk lebih mudahnya perhatikan contoh berikut:

  1. Carilah FPB dari 16 dan 7 menggunakan algoritma euclid
    Jawab:
    16 = 2 \left( 7 \right) + 2 .... (1)
    7 = 3 \left( 2 \right) + 1 .... (2)
    2 = 2 \left( 1 \right) + 0 ..... (3)

    Dari persamaan (3), diperoleh sisa 0, maka FPB dari 16 dan 7 adalah hasil baginya, yaitu 1 atau bisa ditulis \left( {16,7} \right) = 1.

  2. Carilah FPB dari 272 dan 119 menggunakan algoritma euclid
    Jawab:
    272 = 2 \left( 119 \right) + 34 .... (1)
    119 = 3 \left( 34 \right) + 17 .... (2)
    34 = 2 \left( 17 \right) + 0 ..... (3)

    Dari persamaan (3), diperoleh sisa 0, maka FPB dari 272 dan 119 adalah hasil baginya, yaitu 17 atau bisa ditulis \left( {272,119} \right) = 17.

  3. Carilah FPB dari 3456 dan 246 menggunakan algoritma euclid
    Jawab:
    3456 = 14 \left( 246 \right) + 12 .... (1)
    246 = 20 \left( 12 \right) + 6 .... (2)
    12 = 2 \left( 6 \right) + 0 ..... (3)

    Dari persamaan (3), diperoleh sisa 0, maka FPB dari 3456 dan 246 adalah hasil baginya, yaitu 6 atau bisa ditulis \left( {3456,246} \right) = 6.

Selain untuk mencari FPB, algoritma euclid juga bisa digunakan untuk menyelesaikan soal-soal seperti ini:

  • Tentukan bilangan bulat x, y yang memenuhi persamaan 16x + 7y = 1
  • Tentukan bilangan bulat x, y yang memenuhi persamaan 272x + 119y= 17
  • Tentukan bilangan bulat x, y yang memenuhi persamaan 272x + 119y = 2006

Bagaimana cara menentukannya? Ketiga bentuk persamaan di atas adalah bentuk persamaan diophantine linier. Persamaan diophantine linier ini yang sering diselipkan pada soal ujian universitas. Contohnya:
Soal Matematika Dasar SIMAK UI 2013 - Kode 331 dan 435
(null)
Persamaan diophantine linier yang dimaksud adalah 13x + 11y = 700.

Dapatkan solusi Soal Matematika Dasar SIMAK UI 2013 - Kode 331 dan 435 di Buku Matematika SIMAK UI.

Baca Juga: Pengertian Persamaan Diophantine - Teori Bilangan

Salam,

@isranurhadi

Isra Nurhadi

I am a Math teacher with over 10 years of teaching experience | Founder @IstanaMatematik and @IstanaMengajar | Follow me @isranurhadi

You may also like...