Question

Opisz algorytm Euklidesa wykorzystujący dzielenie modulo.

Answer 1

Jednym z najstarszych, do dziś stosowanych algorytmów, jest tzw. algorytm Euklidesa znajdowania największego wspólnego podzielnika (NWD) dwóch liczb naturalnych m oraz n. Działanie tego algorytmu opiera się na następującej obserwacji: jeśli liczba naturalna k jest jednocześnie dzielnikiem liczb m i n, wtedy jest ona także dzielnikiem ich różnicy |m−n|. Dotyczy to również przypadku, kiedy k jest największym wspólnym podzielnikiem obu liczb.

Załóżmy, że liczba m jest większa od n. Wtedy zamiast pary (m, n) możemy wziąć parę (m−n, n), która będzie miała ten sam największy dzielnik. Jednak w wyniku odejmowania zmniejszyliśmy jedną z rozważanych liczb (a druga z nich pozostała niezmieniona).

Opisaną powyżej operację powtarzamy z nową parą liczb − i tak dalej, aż do momentu, kiedy obydwie liczby się zrównają. Oczywiście, jeśli obydwie liczby m i n są sobie równe, wtedy największym ich wspólnych dzielnikiem jest dowolna z tych liczb.