Rozwiązane

3 Wyjaśnij przykładzie liczb 36 i 8, dlaczego warunkiem zakończenia algorytmu Euklidesa w wersji z odejmowaniem jest a = b. ​.

Odpowiedź :

Odpowiedź:

Warunkiem zakończenia algorytmu jest a = b, ponieważ NWD dwóch tych samych liczb jest równe właśnie tej liczbie tzn. NWD(a,a) = a
Dla a = 36 i b = 8 od a będziemy odejmować b aż do momentu gdy
a = 4 i b = 8 wtedy od b odejmiemy a czyli
a = 4 i b = 4 -> NWD(4,4) = 4

Wyjaśnienie:

NWD(a,a) = a

Viz Inne Pytanie