Algorytm Euklidesa
- Sprawdzamy, czy b0, jeśli tak, to następne czynności wykonujemy aż do momentu gdy b=0
c = (b, a mod b)
a = b
b = c
- mod - kongruencja modulo n (b, a mod b) – zapis oznacza, że różnica a - b dzieli się bez reszty przez n
- wynik jest w zmiennej a
Przykład
NWD(1071, 1029) = NWD(1029, 1071 mod 1029 = 42) = NWD(1029, 42) = NWD(42, 1029 mod 42 = 21) = NWD(42, 21) = NWD(21, 42 mod 21 = 0)
Stąd: NWD(1071, 1029) = 21
|