Algoritme Euklidean

Tidaklah sulit untuk membuktikan bahwa algoritme itu benar. Misalkan "a" dan "b" adalah bilangan yang FPB-nya akan ditentukan. Dan misalkan sisa dari pembagian dari "a" oleh "b" adalah "t".
Maka "a" = "qb" + "t" di mana "q" adalah hasil bagi (yang merupakan bilangan bulat) dari pembagian tersebut. Sekarang, setiap pembagi dari "a" dan "b" juga dapat habis membagi "t" (karena "t" dapat ditulis sebagai "t" = "a" − "qb"); Dengan cara yang sama, setiap pembagi dari "b" dan "t" juga akan habis membagi "a". Maka faktor persekutuan terbesar dari "a" dan "b" adalah sama dengan FPB dari "b" dan "t". Oleh karena itu, kita cukup meneruskan proses tadi dengan "b" dan "t" saja. Karena "t" lebih kecil dalam nilai mutlak dari "b", kita akan mencapai "t" = 0 setelah sejumlah langkah.