Почему алгоритм Евклида(НОД) работает?

[Resa]

Доброго времени суток!
Пытаюсь понять алгоритм Евклида для отыскания НОД двух чисел. С применением его на практике у меня проблем нет. Но меня задевает то, что принцип заложенный в алгоритм, для меня не очевиден. Тоесть, если я забуду алгоритм, то мне в голову не придет делить делитель на остаток.
Читал об алгоритме в таких книгах: Зайцев, Цыпкин, Дэвенпорт, но вопрос остался. Например, Зайцев приводит соотношение деления двух чисел с остатком, а потом сразу предлагает разделить делитель на остаток без обоснования такого шага. Вишенкой на тортике для меня было прочитать, что оказывается, если остаток разделит делитель на целое число раз, то он и будет НОД. И это же объяснение подходит для случая, когда два числа делятся нацело, если кто забыл. А ничего, что в этот момент мы можем находится на энной итерации и актуальнее будет вопрос не что будет дальше, а как я сюда попал?

[worm2]

Можно так (считаю $a$ и $b$ неотрицательными целыми):
1) $GCD(a, 0) = a$, поскольку 0 делится на что угодно.
2) $GCD(a, b) = GCD(b, a) = GCD(a+b, b) = GCD(a-b, b)$, поскольку если $a$ и $b$ делятся на одно и то же число, то $a+b$ и $a-b$ делятся на то же число.
Пользуясь правилом 2, пытаемся уменьшить больший аргумент (пусть будет $a$), чтобы он стал меньше, чем меньший ($b$). При этом $a-b$, применённое нужное число раз, естественным образом оптимизируется в $a\bmod b$ (остаток от деления $a$ на $b$). Если получается сразу ноль (больший нацело делится на меньший), то по правилу 1 НОД получается. Если не получается, то, поскольку остаток всегда меньше делителя, меняем числа местами и повторяем правило 2.

[Евгений Машеров]

Ну, это скорее вопрос "как строить алгоритмы". Можно с классического Дейкстры начать, "Дисциплина программирования" или "Наука программирования" Гриса.
В общем, нам надо найти нечто, удовлетворяющее условию. Находим инвариант и преобразование, его сохраняющее. И применяем преобразование так, чтобы результат был в некотором смысле "удобнее".
Какие преобразования сохраняют НОД двух чисел? Например, если мы их сложим или вычтем одно из другого, НОД сохранится? А что для нас удобнее, большие числа или малые? Тогда, очевидно, если из большего вычтем меньшее, НОД сохранится, а числа будут "приятнее". Но можно вычитать не один раз, а многократное вычитание, пока можно, сведётся к делению с остатком. Если остаток ноль - значит, НОД был делителем. "Наконец нашли!" Если не ноль - он меньше делителя, и повторяем процедуры, переставив местами.

[beroal]

Resa в сообщении #1410268 писал(а):

Но меня задевает то, что принцип заложенный в алгоритм, для меня не очевиден. Тоесть, если я забуду алгоритм, то мне в голову не придет делить делитель на остаток.
Читал об алгоритме в таких книгах: Зайцев, Цыпкин, Дэвенпорт, но вопрос остался. Например, Зайцев приводит соотношение деления двух чисел с остатком, а потом сразу предлагает разделить делитель на остаток без обоснования такого шага.

Просто авторы не доказали корректность этого алгоритма. Это такой подход, называется «математика без доказательств» (примерно как «физика без формул») . Хотя эту книгу (или книг) я не читал. Возможно, авторы приводят доказательство корректности дальше, но вы его не нашли. (Кстати, пишите данные книг полностью, потому что я не нашёл в вебе даже названия этой книги). Вообще при публикации нового алгоритма в научной статье всегда доказывают его корректность, и в хороших учебниках по информатике тоже.

Доказательство корректности алгоритма Эвклида есть во многих книгах по началам теории чисел или началам алгебры. Доказательство идёт, как у worm2, со следующей поправкой. Надо понимать, что $\gcd(a, b)$ возвращает множество чисел, множество всех НОД-ов. НОД в натуральных числах уникален, поэтому о нём говорят как об одном числе и неформальная запись $\gcd(a, 0) = a$ формально означает $\gcd(a, 0) = \{a\}$. Однако во многих других контекстах, где используется НОД, он не уникален. В целых числах $\gcd(a, 0) = \{a, -a\}$, то это есть множество всех целых чисел, ассоциированных с $a$.

[nnosipov]

Resa в сообщении #1410268 писал(а):

Читал об алгоритме в таких книгах: Зайцев, Цыпкин, Дэвенпорт, но вопрос остался.

Дэвенпорт --- это, скорее всего, "Высшая арифметика. Введение в теорию чисел" (М.: Наука, 1965). Алгоритму Евклида посвящен отдельный пункт (стр. 24-26). Алгоритм детально описан и довольно подробно обоснован, а также сопровожден численным примером. Все ровно так, как автор описал в предисловии: "В этой книге теоремы и их доказательства часто иллюстрируются численными примерами. Примеры обычно очень просты и могут не удовлетворить читателя, который любит вычисления. Задача этих примеров — пояснить общую теорию." Чего можно умудриться не понять в таком изложении стандартной версии алгоритма Евклида --- загадка.

В книге Дэвенпорта есть сложные алгоритмы, которые даются без доказательства их корректности (например, алгоритмы, с помощью которых простые числа можно представить суммой двух квадратов), но автор об этом честно сообщает читателю (и даже пишет, что доказательства не слишком просты).

[Resa]

Извините за небольшое мое изчезновение. Если честно, я задумался над тем, что написал worm2 и не хотел ничего писать пока мое представление продолжало формироваться.
Worm2 написал правило №2. В нем для меня приятная неожиданность. Пытаясь раскусить алгоритм самостоятельно, я несколько раз подозревал, что здесь может быть замешан дистрибутивный закон, но где - понять не повезло. Правило №2 - это натуральный дистрибутивный закон, ведь так? Значит, нет сомнений что $a$, $b$, $a+b$ имеют общий делитель. И тут мысль: если $GDC(a,b)=GDC(a+b,b)$, тогда $GDC(b,a+b)=GDC(a+2b,a+b)$. И снова, $GDC(a+b,a+2b)=GDC(2a+3b,a+2b)$. И так до бесконечности! Вывод: один и тот же НОД содержится в начальном "дистрибутивном выражении" и в эквивалентном ему, путь к которому лежит через произвольное количество повторений. Но при этом разрядность числа будет расти до бесконечности.
И вот есть два бесконечно больших числа. Ты уверен, что их НОД - это та самая двоечка(например) с которой ты начинал? Тут я приуныл. Самое очевидное решение было начать в ручную прописывать этот сценарий на конкретных числах. Допустим $a=2\times3$, а $b=2\times5$. Вот:
$\begin{multiline} 2\times3+2\times5=2\times8\\ 2\times5+2\times8=2\times13\\ 2\times8+2\times13=2\times21\\ 2\times13+2\times21=2\times34\\ 2\times21+2\times34=2\times55\\ 2\times34+2\times55=2\times89\\ 2\times55+2\times89=2\times144\\ 2\times89+2\times144=2\times233\\ 2\times144+2\times233=2\times377\\ 2\times233+2\times377=2\times610\\ 2\times377+2\times610=2\times987\\ 2\times610+2\times987=2\times1597\\ 2\times987+2\times1597=2\times2584\\ 2\times1597+2\times2584=2\times4181\\ 2\times2584+2\times4181=2\times6765\\ 2\times4181+2\times6765=2\times10946\\ 2\times6765+2\times10946=2\times17711\\ \end{multiline}$
Да, числа большие, а значит делителей больше, а значит нельзя исключать, что в разложении этих чисел на простые множители общими окажутся не только 2-ки, но еще какие-то делители и НОД изменится. Но проверяем и убеждаемся, что во всех случаях НОД - это 2. Как такое возможно? - Только в одном случае - когда множители при коефициентах 2 - это два взаимно простых числа. Не простых, а взаимно простых! Шок! Вот это математика! Как возможно, что всегда эти числа оказываются взяимно простыми? Посмотрев еще раз на выражения, я заметил, что $2\times3+2\times5=2\times8$ - это тоже самое что $3+5=8$. Попробую сделать второй вывод... Если $a$ и $b$ - взаимнопростые числа, то $b$ и $a+b$ также будут взаимно простыми числами. Если я нигде не ошибся, то именно этот последний вывод я считаю ключом к доказательству обсуждаемого алгоритма.
А теперь вернемся к тому, что написал worm2. Когда мы уяснили правило 2 и у нас нет более никаких сомнений, подобных описанному выше, то давайте допустим, что правило работает и в обратную сторону, тоесть будем уменьшать делимое, отняв от него делитель. Вообще, чем вызван этот шаг? Да просто два аргумента не поделились нацело и второе правило для нас - как единственное утешение. По-крайней мере, уменьшая делимое мы не теряем НОД, а там, может и более удачное соотношение чисел подвернется и разделятся они! Но тут же понимаем, пока разность делимого и делителя больше делителя не разделятся они. Потому что не в делителе причина неделимости. Остаток, который скрывается за всеми вычитаниями - это он не кратен делителю. Наконец, докопались мы до остатка. Для нас уже не принципиально, что это называется остатком. Главное, что НОД остатка и делителя равен НОД делимого и делителя. Абстрагируемся от предыстории и снова пытаем удачу деля больший аргумент на меньший. Если не в этот раз то в следующий должно разделится без остатка. Тогда и пригодятся те слова из Зайцева, что при делении нацело делитель есть НОД.

beroal в сообщении #1410470 писал(а):

Кстати, пишите данные книг полностью

В.В. Зыйцев, В. В. Рыжков, М. И. Сканави - Элементарная Математика(Издательство "Наука", Москва 1974г.
А. Г. Цыпкин - Справочник по математике для средних учебных заведений(Изд-во "Наука", 1988г)
Г. Дэвенпорт - Высшая Арифметика. Введение в теорию чисел.(перевод с английского, изд-во "Наука", 1965г.)

nnosipov в сообщении #1410483 писал(а):

Чего можно умудриться не понять в таком изложении стандартной версии алгоритма Евклида --- загадка.

Прошу понять меня правильно, я не имел в виду бросить тень на эти чудесные книги. Я их по-прежнему ценю. Только Дэвенпорта я читаю в электронном варианте, а чтобы купить остальные книги мне пришлось поехать в другой город на книжный базар. Дело в том, что этим алгоритмом, я занялся вообще не по своей воле. Я наткнулся в специальной литературе на слова "операция вычета по модулю". Так как я серьезно отношусь к этой литературе, то не могу расчитывать на усвоение материала, не понимая математического аппарата, на который этот материал опирается. Вот траектория, которая меня завела в эту тему: вычеты по модулю - сравнение по модулю - деление с остатком - алгоритм Евклида. Естесственно, нервничаешь ибо всегда хочется быстрее.
Возможно, у кого-то есть комментарии по теме - милости прошу.

[Brukvalub]

Resa в сообщении #1410568 писал(а):

Возможно, у кого-то есть комментарии по теме - милости прошу.

У меня есть вопрос вот по этому высказыванию:

Resa в сообщении #1410568 писал(а):

И вот есть два бесконечно больших числа.

Дайте определение бесконечно большого числа.

[nnosipov]

Resa в сообщении #1410568 писал(а):

чтобы купить остальные книги мне пришлось поехать в другой город на книжный базар

Потрясен, но вместе с тем и удивлен: неужели тех книг нет тоже в электронном виде? В наше время такое случается только по отношению к очень редким книгам. А эти производят впечатление совсем обычных.

Вы школьник?

[Munin]

Всё это легче понимать, если знать основную теорему арифметики.

[Resa]

Brukvalub в сообщении #1410577 писал(а):

Дайте определение бесконечно большого числа.

Честно? - Не знаю. Но предвосхищаю вопрос: почему тогда используешь? Не ваш так других пользователей вопрос. Поэтому поясню в каком смысле использовал это слово. Раз я смог увеличить разрядность несколько раз подряд, то по индукции могу это делать бесконечно, главное, чтобы время было в распоряжении и вычислительная мощность

nnosipov в сообщении #1410579 писал(а):

Потрясен, но вместе с тем и удивлен: неужели тех книг нет тоже в электронном виде? В наше время такое случается только по отношению к очень редким книгам. А эти производят впечатление совсем обычных.

Вы школьник?

Все просто. Во-первых, ценю реальную книгу намного больше электронной. Об отличии процесса чтения электронной и реальной книг где-то говорила Татьяна Черниговская. Я склонен согласится. Во-вторых, я отнюдь не ехал за этими книгами. Просто из прочих мой выбор пал на них. Я не школьник.

[vpb]

О, Аллах !
Resa, Вы почитайте книжку О.Оре, Приглашение в теорию чисел. Поистине, нет книги более простой ! Если не знаете где взять, зайдите на сайт gen.lib.rus.ec.

[nnosipov]

Да, Дэвенпорта, наверное, пока рановато читать.

[vpb]

Resa в сообщении #1410585 писал(а):

Но предвосхищаю вопрос: почему тогда используешь?

Такого вопроса тут быть не может, т.к. участники форума обращаются друг к другу на "Вы".

[Munin]

Resa в сообщении #1410585 писал(а):

Во-первых, ценю реальную книгу намного больше электронной. Об отличии процесса чтения электронной и реальной книг где-то говорила Татьяна Черниговская. Я склонен согласится.

Ну говорила и говорила. Самое главное: электронных книг намного больше, в том числе не переиздаваемых сегодня, старых хороших книг. И они доступней (часто бесплатны), то есть можно спокойно набрать несколько книг "про запас", и выбрать из них для чтения одну, не сожалея о потраченных средствах.

[Brukvalub]

Resa в сообщении #1410585 писал(а):

Brukvalub в сообщении #1410577

писал(а):
Дайте определение бесконечно большого числа.

Честно? - Не знаю. Но предвосхищаю вопрос: почему тогда используешь? Не ваш так других пользователей вопрос. Поэтому поясню в каком смысле использовал это слово. Раз я смог увеличить разрядность несколько раз подряд, то по индукции могу это делать бесконечно, главное, чтобы время было в распоряжении и вычислительная мощность

Для меня это выглядит дико: использовать в разговоре термины, не зная их точного смысла. Напоминает солдатскую шутку, когда новобранца посылают к завгару "за ведром клиренса".