Bilangan

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 dan adalah dua bilangan bulat dengan syarat . Jika dibagi dengan maka terdapat dua buah bilangan bulat lainnya, yaitu (hasil bagi) dan (sisa), sedemikian sehingga:

dengan . Contoh: Jika dibagi dengan akan memberikan hasil bagi dan sisa , sedemikian sehingga:

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 tersebut, diperoleh sifat dari FPB, yaitu FPB FPB atau bisa ditulis . Untuk pembuktiannya kalian bisa cari FPB dari dan serta FPB dari dan dengan cara sederhana yaitu faktorisasi prima. Diperoleh .

Dengan sifat FPB tersebut, kita bisa terapkan algortima euclid berulang, yaitu:
                                                                                                                    Maka, . Jadi FPB dari dan adalah sisa terakhir yang bernilai tidak nol atau sama dengan hasil bagi terakhir yang bersisa nol. Catatan: Variabel pada persamaan diubah menjadi agar memudahkan pemahaman tentang algoritma berulang di atas.

Untuk lebih mudahnya perhatikan contoh berikut:

  1. Carilah FPB dari dan menggunakan algoritma euclid
    Jawab:
    .... (1)
    .... (2)
    ..... (3)

    Dari persamaan (3), diperoleh sisa , maka FPB dari dan adalah hasil baginya, yaitu atau bisa ditulis .

  2. Carilah FPB dari dan menggunakan algoritma euclid
    Jawab:
    .... (1)
    .... (2)
    ..... (3)

    Dari persamaan (3), diperoleh sisa , maka FPB dari dan adalah hasil baginya, yaitu atau bisa ditulis .

  3. Carilah FPB dari dan menggunakan algoritma euclid
    Jawab:
    .... (1)
    .... (2)
    ..... (3)

    Dari persamaan (3), diperoleh sisa , maka FPB dari dan adalah hasil baginya, yaitu atau bisa ditulis .

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

  • Tentukan bilangan bulat , yang memenuhi persamaan
  • Tentukan bilangan bulat , yang memenuhi persamaan
  • Tentukan bilangan bulat , yang memenuhi persamaan

Bagaimana cara menentukannya? Ketiga bentuk persamaan di atas adalah bentuk persamaan linier dua variabel atau bisa juga disebut persamaan diophantine linier dua variable jika variabel-varibelnya adalah bilangan bulat.

Persamaan diophantine linier sering diselipkan pada soal ujian universitas. Contohnya:
Soal Matematika Dasar SIMAK UI 2013 - Kode 331 dan 435
(null)
Persamaan diophantine linier yang dimaksud adalah .

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