Hva er Euklids algoritme?

Euklids algoritme er en metode for å finne største felles faktor til to heltall.

Algoritmen bygger på sammenhengen

I algoritmen erstattes tallparet $(a,b)$ med $(b,a\mmod b)$ inntil resten $(a \mmod b) = 0$. Den største felles faktoren er den siste resten som ikke er null.