Dowód poprawności Lemat: Aby to wykazać, należy udowodnić, że wspólny podzielnik liczb i jest również podzielnikiem liczby
Przyjmijmy:
gdzie są liczbami całkowitymi.
Wtedy:
zatem jest również podzielnikiem
Z lematu wynika przez indukcję, że jeśli algorytm się zakończy, to da poprawny wynik. Pozostaje udowodnić, że się zakończy. Wystarczy w tym celu zauważyć, że więc w każdym kroku algorytmu wartość zmniejsza się przynajmniej o 1. Ponieważ nie może nigdy być ujemna, algorytm musi się zakończyć.
Złożoność czasowa Dla dowolnych liczb algorytm Euklidesa zwraca wartość NWD(m, n) po co najwyżej przebiegach pętli.
Dowód Lemat: Jeśli to
jest równoważne Podstawiając
otrzymuje się:
i ponieważ to oraz ponadto z własności modulo otrzymujemy:
Przy pierwszej iteracji mamy po k-tym przebiegu pętli:
Ponieważ po ostatnim, l-tym przebiegu pętli będzie:
Największej liczby kroków algorytmu wymagają takie liczby m i n, które są kolejnymi elementami ciągu Fibonacciego.
Rozszerzony algorytm Euklidesa Jeśli przechowywana będzie informacja o kolejnych ilorazach, to będzie też można wyznaczyć liczby całkowite w równaniu Ta metoda nazywana jest rozszerzonym algorytmem Euklidesa.
Na przykład dla liczb 174 i 18 w algorytmie Euklidesa uzyskuje się wyniki pośrednie: