Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas algoritma Euclid yang membantu menghitung FPB atau GCD dari dua bilangan bulat secara efisien. Dengan contoh perhitungan FPB antara 81 dan 187, algoritma ini menggunakan pembagian berulang untuk mencari hasil akhirnya. Langkah demi langkah, akhirnya ditemukan bahwa GCD dari 81 dan 187 adalah 3. Algoritma Euclid ini efektif dalam menyelesaikan permasalahan teori bilangan dan kriptografi.

Kita sampai pada bagian terakhir dari bilangan prima yaitu algoritma Euclid.

Sama ya, ini ada namanya berarti algoritmanya itu sangat membantu kita untuk menghitung

dan biasanya kita berikan penghargaan pada penemunya yaitu Pak Euclid.

Kita sudah belajar bahwa mencari FPB atau GCD dari dua bilangan bulat itu kita cari faktor-faktor primanya.

Tapi ternyata cara yang kita pakai itu kurang efisien.

Jadi ada yang lebih efisien yaitu kita akan menggunakan si algoritma Euclid ini.

Jadi kalau kita mau mencari misalnya FPB atau GCD dari 81 dan 187

maka yang kita lakukan adalah 187 itu dituliskan dalam 81 kali sekian tambah sisanya.

Jadi masih ingat nggak ini algoritma apa namanya?

Pembagian, jadi 187 itu kita bisa tuliskan dalam 81 kali 2 ditambah 15.

Artinya 187 dikurangin 81 kali 2 itu sama dengan 15.

Kalau kita lihat pembagi dari 81 dan 187 itu nanti juga akan membagi si 15.

Sehingga FPB atau GCD dari 81 dan 187 akan sama dengan GCD dari 15 dengan 81.

Tapi kita kan dapat bilangan yang lebih kecil untuk mencari FPB atau GCDnya.

Sehingga kita lanjutkan dengan GCD 15 dan 81.

Jadi 81nya kita tuliskan sebagai 15 kali sesuatu ditambah sisanya.

Hal dalam hal ini 81 itu sama dengan 15 kali 5 tambah 6.

Dengan cara yang sama kita bisa dapatkan bahwa GCD 15 81 itu akan sama dengan GCD dari 6 15.

Jadi kalau kita tarik ke depan pertanyaan tadi adalah GCD 81 dengan 187 akan sama dengan GCD dari 6 dengan 15.

Kita ulangi lagi langkahnya antara 15 dengan 6 karena tadi sisanya 6.

Jadi 15 itu bisa dituliskan dalam 6 kali 2 tambah 3.

Sehingga GCDnya itu si 6 15 akan sama dengan GCD 3 dan 6.

Nanti kita dapat 6 itu sama dengan 2 kali 3 ditambah 0.

Karena sisanya sudah 0 berarti langkah kita sudah selesai.

Kemudian kita simpulkan dari langkah pertama GCD 81 187 akan sama dengan GCD 36 sama dengan 3.