Фантазии о Вселенной и мой личный сайт
Алгоритм Евклида для НОД

Алгоритм Евклида для НОД

Разбор алгоритма Евклида для поиска наибольшего общего делителя. Поиск наибольшего общего делителя.

Этот волшебный алгоритм я узнал еще давно, наверное, где-то в 3-4 классе начальной школы, и был потрясен до глубины души его простотой. Он описывался вот таким образом:

int NOD(int a, int b) {
    return b == 0 ? a : NOD(b, a % b);
}

Сказать то, что я был в шоке – мало. Я был в ступоре! Я не мог понять, каким именно таким образом с помощью всего лишь, можно сказать, одной строки высчитывается наибольший общий делитель! Как так? Я думал, что нужно перебирать все числа подряд, чтобы найти, а тут такой простой алгоритм это делает без проблем. Это была настоящая магия, понять которую можно только лишь магам, или богам.

И совершенно недавно, в возрасте 31 года, я понял. Я понял только лишь в этом возрасте. И попытаюсь объяснить, как именно это работает.

Итак, начнем с самого-самого простого, с разложения числа. Нам нужно найти НОД от a, b, это пишется так НОД(a, b) = d, где a и b - это числа, которые мы ищем, а "d" - это и есть наибольший общий делитель. Давайте слелаем так. Мы число "a" представим в виде вот такой формулы:

$$ a = bq + r $$

Почему именно такой? Ответ простой – просто так нужно, если мы не сделаем такое представление, то ничего не докажем и не выведем. И это будет работать, спросите вы? Конечно! Абсолютно любое целое число "a" можно разложить в эту формулу.

Пример: возьмем числа a = 10, b = 3, просто для проверки. Чтобы найти q и r, требуется сделать очень простые вещи:

$$ q = [\frac{a}{b}], \\ r = a - bq = a - b[\frac{a}{b}] $$

Все, что находится вот в таких скобках [ ] в математике означает, что мы берем ЦЕЛОЕ число от результата, например \( [12.421] = 12 \). Итак: разделить нацело мы можем всегда, и результат этого деления будет в "q" (quotient), а остаток окажется в "r" (remainder). Значит, что формула выше абсолютно справедлива и возможна.

Что дальше? А дальше важно доказать вот что. Возьмем то же самое отношение, просто поменяем вместо "q" и "r" на g, s. Не знаю, зачем. Наверное, для смеха ради.

$$ a = bg + s $$

Самое смешное вот в чем. Оказывается НОД от чисел a, b будет в точности равен НОД от b, s! Это как? Да вот я сам в начале не понял, как это так, пока не разобрал далее... Давайте докажем, что НОД(a, b) = НОД(b, s). Как видно, число g тут просто так, чтобы было и ни на что не влияет сейчас.

Итак. Допустим, у нас нашелся НОД(a, b) и он равен d1. Это означает то, что есть такие целые числа u, v, умножая на которые, мы получим значения a и b:

$$ a = d_1u \\ b = d_1v $$

И причем тут u, v? Давайте сразу к примеру. Вот есть у нас a=18, b=12, какой у них наибольший делитель? НОД(18,12) = 6, т.е. d1 = 6. Проверим:

$$ \frac{a}{d1} = \frac{18}{6} = 3, u = 3 \\ \frac{b}{d1} = \frac{12}{6} = 2, v = 2 $$

Вот тут u = 3, v = 2, то есть если умножить u на d1, то мы получим "a", и если v на d1 - то "b". Это означает, что если есть НОД(a, b), то u, v будут точно целыми числами.

Поехали дальше. Давайте теперь поставим вот сюда "a = bg + s" наши предполагаемые a, b, выраженные через u, v:

$$ d_1u = d_1vg + s \\ s = d_1u - d_1vg \\ s = d_1(u - vg) $$

Что видим? Видим, что справа у нас (u - vg), которое является целым числом. И что слева у нас "s", которое тоже целое число, мы это вначале доказали. Ну и d1 тоже целое. Какой вывод? Вывод такой, что "s" делится на d1 без остатка.

Важный вывод: и "a", и "b" и "s" у нас делятся без остатка на тот же самый НОД(a, b). Это получается, что у них один и тот же делитель, что у "a, b" что у "b, s", что и у "a, s", так что НОД(a, b) = НОД(a,s) = НОД(b,s), все делятся на одно и тоже число d1.

Вот теперь происходит самый большой в мире фокус. Вот мы видим такую формулу:

$$ a = bq + r $$

Тут мы видим, что НОД(a, b) на самом деле (смотри выше доказательство) равен НОД(b, r). Теперь давайте попробуем что-нибудь поискать, например НОД(18,12). Тут у нас a=18, b=12. Раскладываем:

$$ 18 = 12q + r \\ q = [\frac{18}{12}] = 1 \\ r = 18 - 12*1 = 6 $$

Вот мы нашли q=1, и r = 6. Но нам q не нужен. Мы доподлинно знаем, что НОД(b, r) = НОД(a, b), и что это значит? Это значит, что нам пора искать НОД(12, 6) - потому что r = 6. Ну что же, поищем:

$$ 12 = 6*q + r \\ q = [\frac{12}{6}] = 2 \\ r = 12 - 6*2 = 0 $$

Отлично! У нас остаток r = 0, то есть, мы все-таки да поделили так, что нашли что-то без остатка. И поделили в последний раз мы на число 6. Значит, что \( НОД(18,12) = НОД(12,6) = 6 \), поскольку остатка при делении нет, а значит, НОД был найден.

Вся магия поиска НОД заключается в том, что \( НОД(a, b) = НОД(b, s) \), и что можно разложить число "a" через число "b" по формуле a = bq + r. В итоге у нас получается, что при поиске НОД мы делаем вот такие вот запросы: $$ d = НОД(a, b) = НОД(b, a \ mod \ b) $$ где a mod b - это поиск остатка (числа r). Все доказано!