Есть довольно много способов найти НОД, сегодня мы разберем довольно простой и, на первый взгляд, магический способ: алгоритм Евклида.

Работает этот алгоритм так:
1) Пусть есть два числа, a и b, причем a<b, и мы хотим посчитать НОД(a, b). Посчитаем значение b-a, пусть оно равняется числу r. Алгоритм утверждает, что НОД(a, b) = НОД(a, r).
2) Дальше поступаем аналогичным образом: из большего числа вычитаем меньшее, и заменяем большее число на эту разность.
3) Остановиться нужно в тот момент, когда одно из чисел будет нацело делиться на другое — вот меньшее из этих двух и будет являться НОДом для исходной пары чисел.

На словах сложновато, давайте рассмотрим пример. Каждый раз заменяем большее число на разность.
НОД(1955, 714) = НОД(1241, 714) = НОД(527, 714) = НОД(527, 187) = НОД(340, 187) = НОД(153, 187) = НОД(153, 34) = НОД(119, 34) = НОД(85, 34) = НОД(51, 34) = НОД(17, 34) = 17. И действительно, 1955 = 5*17*23, а 714 = 2*3*7*17.

Но как же это работает? У каждого числа существует разложение на простые множители. Мы его тут явно не используем, но оно есть. Давайте скажем, что у чисел a и b наибольший общий делитель равен k. Тогда пусть a=k*x, b=k*y. Если b-a=r, то можно выразить r так: r = k*y - k*x = k*(y-x). Получается, при такой операции мы сохраняем НОД чисел в качестве одного из множителей на каждом шаге. А вот разность y-x дойдёт до нуля, просто мы заканчиваем алгоритм раньше.

Этот алгоритм работает не только для пар чисел: если их больше, то можно вычислить НОД первых двух, а потом НОД первого НОДа и третьего числа — и так далее.
На прикладном уровне это нужно, к примеру, для решения диофантовых уравнений, а также для цепных дробей. А они используются в криптографических алгоритмах: защищают данные вашей банковской карты и фотографии в смартфоне. Про цепные дроби мы ещё расскажем подробнее.

Задачка для вас — посчитать НОД(3105, 2254). Ответы пишите в комментарии под скрытым текстом.