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

Video ini membahas Teorema Bezout dalam Matematika Diskrit, yang menjelaskan bahwa GCD atau HPB dari dua bilangan bulat positif, A dan B, dapat dituliskan sebagai kombinasi linear dari A dan B. Dengan menggunakan algoritma Euclidean, kita dapat mencari koefisien S dan T sehingga nilai GCD AB bisa dituliskan sebagai S kali A ditambah T kali B. Contohnya, GCD dari 198 dan 252 adalah 18, yang dapat dituliskan sebagai 4 kali 252 dikurangi 5 kali 198. Dengan demikian, konsep ini memperlihatkan hubungan antara Teorema Bezout dan algoritma Euclidean dalam menyelesaikan masalah teori bilangan dan kriptografi.

GCD ini atau HPB dari AB bisa juga dituliskan dalam bentuk yang berbeda.

Kita katakan dia dapat dituliskan sebagai kombinasi linear dari A dan B.

Teoremanya kita sebut sebagai teorema biso.

Jadi kalau kita punya A dan B bilangan bulat positif,

maka kita bisa mencari bilangan bulat S dan T,

sehingga GCD AB atau HPB AB bisa dituliskan dalam S A ditambah T B.

kita tahu kalau dicari itu sama dengan 18,

maka 18 itu bisa dituliskan dalam kombinasi linear 198 dan 252.

Ingat disini AB itu bilangan bulat positif,

Jadi kalau kita cari contohnya misalnya saya cari tadi 252 sama 198,

maka caranya untuk mencari koefisien S dan T,

supaya 18 bisa dituliskan sebagai sekian kali 252 ditambah sekian kali 198

adalah kita mulai dengan algoritma Euclidean.

Kemudian kita lihat 198 dibandingkan dengan 54 dengan cara yang sama,

Kemudian 36 dengan 54 kita buat dengan cara yang sama,

sampai yang terakhir nanti kita dapat 36 itu 2x18 tidak ada sisanya.

kita akan dapat 18 itu adalah 54 dikurang 1x36,

Terus nanti 36 ini kita ambil dari yang langkah sebelumnya,

kita bisa tuliskan sebagai 198 dikurang 3x54,

akan sama dengan 36nya kita ganti dengan 198-3x54,

nanti kita akan dapat bentuk yang terakhir 4x54 dikurang 1x198,

54nya itu akan sama dengan 254 dikurang 1x198,

sehingga kita bisa mengatakan bahwa 18 itu adalah 4x252 dikurang 1x198 dikurang 1x198,

jadi kita tahu bahwa 18 itu bisa dituliskan dalam kombinasi linear ini,