Таблицы Брадиса

Пара Ъ, г заменяется по

Пара Ъ, г заменяется по

Элементы математики в задачах - Г. А. Мерзон

в)  Эта на первый взгляд несложная и ничем вроде не примеча­тельная задача очень важна для доказательства того, что при помощи алгоритма Евклида действительно получается НОД двух чисел.

Итак, начнем доказательство. Введем обозначения: пусть d = = НОД(а, Ъ), В = НОД(а, са + Ъ), а = dx, Ъ = dy. Заметим, что и а = dx, и са + Ъ = d (сх + у) делятся на d. Значит, d — общий делитель чисел а и са + Ъ. Следовательно, В ^ d (потому что В — наибольший общий делитель чисел а и са + Ъ).

Теперь докажем неравенство в другую сторону. Так как а делится на В, то и са делится на В. А из того, что са и са + Ъ делятся на В, следует, что и их разность Ъ делится на В. Значит, В — общий делитель чисел а и Ъ. Следовательно, d ^ В.

Из всего вышесказанного следует, что В = d.

Задача 8 (алгоритм Евклида). Рассмотрим следующий процесс. Пусть (а, Ъ) — пара положительных чисел такая, что а ^ Ъ. Она заменяется на пару (Ъ, г), где г — остаток от деления а на Ъ. Пара (Ъ, г) заменяется по тому же правилу и так далее. Процесс завершается, когда получается пара вида (<і, 0). Покажите, что:

а) процесс всегда завершается;

б) d = НОД(а, Ъ).

Решение. а) Процесс всегда завершается, так как для каждой следую­щей пары второе число будет по модулю строго меньше (условие 2 в определении 1) второго числа предыдущей пары. Поэтому ясно, что рано или поздно мы получим пару, в которой второе число будет равно нулю, и процесс завершится.

б) Из пункта в) предыдущей задачи следует, что при каждой за­мене у пар (а, Ъ) и (Ъ, г) будет одинаковый НОД. Значит, у первой пары и у последней — одинаковые НОД. А это и означает, что d = = НОД(а, Ъ).

Задача 9. Вычислите при помощи алгоритма Евклида