Алгоритм Евклида

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 14:29, 29 апреля 2016.
Версия от 14:29, 29 апреля 2016; Vladimir Bushuyev (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Постановка задачи.

Найти .

Решение

Решается с помощью Алгоритма Евклида

Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел

определена тем, что каждое  — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

Тогда НОД(a,b), наибольший общий делитель и , равен , последнему ненулевому члену этой последовательности.

Существование

Существование таких , то есть возможность деления с остатком на для любого целого и целого , доказывается индукцией по m.

Корректность

Вытекает из следующих двух утверждений:

  • Пусть , тогда НОД (a,b) = НОД (b,r).
    1. Пусть k — любой общий делитель чисел a и b, не обязательно максимальный, тогда  ; где и — целые числа из определения.
    2. Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а (выражение в скобках есть целое число, следовательно, k делит r без остатка)
    3. Обратное также верно и доказывается аналогично 2) - любой делитель b и r так же является делителем a и b.
    4. Следовательно, все общие делители пар чисел a,b и b,r совпадают. Другими словами, нет общего делителя у чисел a,b, который не был бы также делителем b,r, и наоборот.
    5. В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
  • для любого ненулевого .