Алгоритм знаходження НСД двох натуральних чисел

1. Взяти два числа. Якщо вони рівні, то перше є НСД, інакше перейти до пункту 2.
2. Визначити більше з цих двох чисел.
3. Більше число замінити різницею більшого і меншого.
4. Перейти до пункту 1.

НСД (105; 15)

1) 105 ≠ 15

2) 105 ≻ 15

3) 90 15

1) 90 ≠ 15

2) 90 ≻ 15

3) 75 15

1) 75 ≠ 15

2) 75 ≻ 15

3) 60 15

1) 60 ≠ 15

2) 60 ≻ 15

3) 45 15

1) 45 ≠ 15

2) 45 ≻ 15

3) 30 15

1) 30 ≠ 15

2) 30 ≻ 15

3) 15 = 15