Algorytm Euklidesa

Zadanie polega na znalezieniu największego wspólnego dzielnika dwóch liczb całkowitych

Rys. 1. Przykład formularza

Zakładamy, ze

to

gdzie,

a – liczba pierwsza (dzielnik)

b – liczba druga (wielokrotność)

q - iloraz

r – reszta z dzielenia

Postępowanie (iteracyjnie)

W kroku pierwszym badamy (a,b), jeżeli r=0 wtenczas największym wspólnym dzielnikiem jest b w przeciwnym razie zakładamy, iż i badamy (b,r₁). Poszukiwania prowadzimy do momentu w którym r=0