Algoritme Euklidean

Dengan mencatat hasil bagi (yang merupakan bilangan bulat) selama menjalankan algoritme,
kita juga dapat menentukan bilangan bulat "p" dan "q" di mana "ap" + "bq" = fpb("a", "b"). Hal ini dikenal sebagai Ekstensi Algoritme Euklidean.