3624815695

Działanie powyższego algorytmu sprawdźmy na przykładzie:

-    szukamy: NWD(1675,3752), czyli a = 1675, b = 3752

-    dzielimy większą liczbę przez mniejszą: b/a = 3752/1675 = 2 reszta 402;

za b podstawiamy resztę z dzielenia, czyli teraz: a = 1675, b = 402

-    dzielimy większą liczbę przez mniejszą:

a/b = 1675/402 = 4 reszta 67; za a podstawiamy resztę z dzielenia, czyli teraz: a = 67, b = 402

-    dzielimy większą liczbę przez mniejszą: b/a = 402/67 = 6 reszta 0; za b podstawiamy resztę z dzielenia, czyli teraz: a = 67, b = 0

-    za NWD przyjmujemy tę z liczb a i b, która jest większa od zera, czyli: NWD(1675,3752) = 67