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

Video ini membahas tentang Algoritma Euclid dalam Teori Bilangan dan Kriptografi. Algoritma ini digunakan untuk mencari Greatest Common Divisor (GCD) atau Faktor Persekutuan Terbesar dari dua bilangan bulat A dan B. Langkah-langkahnya melibatkan pembagian berulang hingga diperoleh sisa 0, di mana sisa terakhir adalah GCD dari A dan B. Algoritma dapat direpresentasikan dalam prosedur GCD AB dengan iterasi pembagian dan pengecekan sisa. Dengan demikian, Algoritma Euclid efektif dalam menemukan GCD dari dua bilangan secara sistematis.

Kalau kita punya 2 bilangan bulat dengan A lebih besar sama dengan B, 2 bilangan bulatnya itu A dan B

dan kita misalkan, ini kita pakai algoritma ya caranya sekarang, kita misalkan R0 nya itu A, R1 nya itu B.

terus kita tuliskan R0 itu sama dengan R1 kali Q1 ditambah R2 dimana R2 nya lebih besar sama dengan 0,

jadi harus positif dan lebih kecil dari R1.

Kemudian yang berikutnya kita turunkan, jadi tadi si faktornya R1 tadi itu kita cari persamaannya dari R1 itu sama dengan R2 Q2 ditambah R3

dengan R3 itu sisa yang harus lebih kecil R2 dan dia harus positif.

Langkah ini kita teruskan sampai kita dapat sisanya sama dengan 0, tadi yang kita sudah lakukan.

Kalau misalnya kita sudah dapat 0, nanti kita bisa mendapatkan remindernya itu,

A nya sama dengan R0 itu pasti lebih besar dari R1, lebih besar dari R2 dan yang terakhir itu 0.

Itu tidak bisa lebih dari A suku karena A nya itu bilangan yang tadi kita sudah sebutkan lebih besar sama dengan B.

Dari lema kita tahu bahwa GCD AB itu sama dengan GCD R0 R1 karena R0 nya itu kita ambil A, R1 nya kita ambil B,

kemudian dari persamaan yang kedua kita tahu bahwa GCD nya akan sama dengan R1 R2,

maksud saya GCD dari R1 R2 dan selanjutnya sampai kita dapatkan si Rn.

Jadi pembagi persekutan terbesar adalah reminder 0 terakhir dalam barisan pembagian ini,

jadi kita teruskan sampai hasilnya reminder nya 0.

Reminder yang langkah sebelumnya itu adalah GCD atau FPB nya.

Jadi algoritmanya itu kalau kita bikin secara prosedural algoritma,

jadi prosedur GCD AB integer positif, di awal kita tentukan X sama dengan A, Y nya B,

selama Y nya tidak 0 kita cari R nya itu X mod Y.

Jadi masih ingat ya definisi X mod Y itu kan adalah dimana kita cari reminder dari X kalau dibagi oleh Y,

nanti kita bikin X nya yang baru itu akan sama dengan Y, kemudian Y yang baru akan sama dengan R.

Sekarang kita cek apakah Y nya sudah 0 belum reminder nya,

kalau belum langkah ini kita lanjutkan lagi terus sampai stopping kriteriannya disini Y nya sama dengan 0.

Kalau sudah nanti kita akan dapat si GCD dari AB itu adalah X yang terakhir.