Jelaskan Bukti kebenaran dari Algoritme Euklides

Misalkan  dan  adalah bilangan yang FPB-nya akan ditentukan. Dan misalkan sisa dari pembagian dari  oleh  adalah . Maka  di mana  adalah hasil bagi (yang merupakan bilangan bulat) dari pembagian tersebut. Sekarang, setiap pembagi dari  dan  juga dapat habis membagi  (karena  dapat ditulis sebagai ). Dengan cara yang sama, setiap pembagi dari  dan  juga akan habis membagi . Maka faktor persekutuan terbesar dari  dan  adalah sama dengan FPB dari  dan . Oleh karena itu, kita cukup meneruskan proses tadi dengan  dan  saja. Karena  lebih kecil dalam nilai mutlak dari , kita akan mencapai setelah sejumlah langkah.