§ Разложение числа

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

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

Сказать то, что я был в шоке — мало. Я был в ступоре! Я не мог понять, каким именно таким образом с помощью всего лишь, можно сказать, одной строки высчитывается наибольший общий делитель! Как так? Я думал, что нужно перебирать все числа подряд, чтобы найти, а тут такой простой алгоритм это делает без проблем. Это была настоящая магия, понять которую можно только лишь магам, или богам.
И совершенно недавно, в возрасте 31 года, я понял. Я понял только лишь в этом возрасте. И попытаюсь объяснить, как именно это работает.
Итак, начнем с самого-самого простого, с разложения числа. Нам нужно найти НОД от a, b, это пишется так НОД(a, b) = d, где a и b - это числа, которые мы ищем, а "d" - это и есть наибольший общий делитель. Давайте сделаем так. Мы число "a" представим в виде вот такой формулы:
Почему именно такой? Ответ простой – просто так нужно, если мы не сделаем такое представление, то ничего не докажем и не выведем. И это будет работать, спросите вы? Конечно! Абсолютно любое целое число "a" можно разложить в эту формулу.
Пример: возьмем числа a = 10, b = 3, просто для проверки. Чтобы найти q и r, требуется сделать очень простые вещи:
Все, что находится вот в таких скобках [ ] в математике означает, что мы берем ЦЕЛОЕ число от результата, например . Итак: разделить нацело мы можем всегда, и результат этого деления будет в "q" (quotient), а остаток окажется в "r" (remainder). Значит, что формула выше абсолютно справедлива и возможна.
Что дальше? А дальше важно доказать вот что. Возьмем то же самое отношение, просто поменяем вместо "q" и "r" на g, s. Не знаю, зачем. Наверное, для смеха ради.
Самое смешное вот в чем. Оказывается НОД от чисел a, b будет в точности равен НОД от b, s! Это как? Да вот я сам в начале не понял, как это так, пока не разобрал далее... Давайте докажем, что НОД(a, b) = НОД(b, s). Как видно, число g тут просто так, чтобы было и ни на что не влияет сейчас.
Итак. Допустим, у нас нашелся НОД(a, b) и он равен d1. Это означает то, что есть такие целые числа u, v, умножая на которые, мы получим значения a и b:
И причем тут u, v? Давайте сразу к примеру. Вот есть у нас a=18, b=12, какой у них наибольший делитель? НОД(18,12) = 6, т.е. d1 = 6. Проверим:
Вот тут u = 3, v = 2, то есть если умножить u на d1, то мы получим "a", и если v на d1 - то "b". Это означает, что если есть НОД(a, b), то u, v будут точно целыми числами.
Поехали дальше. Давайте теперь поставим вот сюда "a = bg + s" наши предполагаемые a, b, выраженные через u, v:
Что видим? Видим, что справа у нас (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, b) на самом деле (смотри выше доказательство) равен НОД(b, r). Теперь давайте попробуем что-нибудь поискать, например НОД(18,12). Тут у нас a=18, b=12. Раскладываем:
Вот мы нашли q=1, и r = 6. Но нам q не нужен. Мы доподлинно знаем, что НОД(b, r) = НОД(a, b), и что это значит? Это значит, что нам пора искать НОД(12, 6) - потому что r = 6. Ну что же, поищем:
Отлично! У нас остаток r = 0, то есть, мы все-таки да поделили так, что нашли что-то без остатка. И поделили в последний раз мы на число 6. Значит, что , поскольку остатка при делении нет, а значит, НОД был найден.
Вся магия поиска НОД заключается в том, что , и что можно разложить число "a" через число "b" по формуле a = bq + r. В итоге у нас получается, что при поиске НОД мы делаем вот такие вот запросы: где a mod b - это поиск остатка (числа r). Все доказано!