Niech:
K – badany algorytm,
d – dane wejściowe,
α - warunek wejściowy (danych początkowych d)
β – warunek wyjściowy (danych wyjściowych)
Warunki α i β nazywamy specyfikacją algorytmu K. Aby algorytm K był poprawny muszą zostać spełnione następujące warunki:
Dla danych d spełniających α, jeżeli obliczenie algorytmu K dochodzi do punktu końcowego, to otrzymane wyniki spełniają β (poprawność częściowa)
Dla każdych danych d spełniających warunek α obliczanie K nie jest przerwane (określoność obliczeń)
Dla każdych danych d spełniających α obliczanie K nie jest nieskończone (własność stopu)
Jeżeli wszystkie warunki zostaną spełnione, to nazywamy to całkowitą poprawnością algorytmu K i algorytm K jest zgodny ze specyfikacją.
Warunek 1. został spełniony w zadaniu 1, w którym dowiedliśmy, że algorytm ma skończoną liczbę przebiegów. Dodatkowo, dla liczb naturalnych wynikiem będą też liczby naturalne, bo działania występujące w algorytmie (podstawienia, reszta z dzielenia modulo) nie zmienią zbioru rozwiązań.
Warunek 2. jest spełniony, ponieważ w funkcji nie występują warunki ani instrukcje przerywające działanie algorytmu, a ponieważ w zadaniu 1. dowiedliśmy, że dla każdych danych wejściowych spełniających specyfikację algorytm ma skończoną liczbę kroków, to algorytm będzie wykonywany dotąd, aż wykona wszystkie przewidziane operacje.
Warunek 3. jest spełniony, co udowodniliśmy w zadaniu 1. (Algorytm ma skończoną ilość przebiegów dla każdego zestawu danych)