Алгоритм Евкліда

Спосіб знаходження НСД запропонований Евклідом ще в VI ст. до н.е.

Замінюємо більше з двох чисел різницею більшого і меншого доти, поки вони не стануть рівні. Це і є НСД.

НСД (14, 21) = НСД (14, 21-14) = НСД (14, 7)= НСД (7, 7) = 7

Приклад,

НСД ( 517, 141 ) = НСД ( 517-141, 141 ) = НСД ( 376, 141 ) = НСД ( 376-141, 141 ) = НСД ( 235, 141 ) = НСД ( 235-141, 141 ) = НСД ( 94, 141 ) = НСД ( 94, 141-94 ) = НСД ( 94, 47 ) = НСД ( 94-47, 47 ) = НСД ( 47, 47 ) = 47

Модифікований алгоритм Евкліда

Замінюємо більше з двох чисел залишком від ділення більшого на менше доти, поки менше не стане дорівнює нулю. Тоді більше це НСД. 

НСД (14, 21) = НСД (14, 7) = НСД (0, 7) = 7

Приклад,

НСД ( 517, 141 ) = 47, а саме:

1) 517 : 141 = 3 ( остача 94 )

2) 141 : 94 = 1 ( остача 47 )

3) 94 : 47 = 2 ( остача 0 )

остання відмінна від 0 остача – шуканий НСД.