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

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

Алгоритм Евклида основан на следующих двух утверждениях:

Лемма 1. Если а в, то НОД (а, в) = в, НОК (а, в) = а.

Доказательство. Т.к. а в Ù в в Þ в = ОД (а, в). (ОД (а, в) – общий делитель чисел а, в).

Но, число в не имеет делителей больших, чем в, а потому и числа а и в не имеют общих делителей, больших, чем в. Значит,
в = НОД (а, в).

Т.к. а а Ù а в Þ а = ОК (а, в). (ОК (а, в) – общее кратное чисел а, в). Если предположить, что существует m = ОК (а, в) < а, то m не делится на а, значит, а есть НОК (а, в).

Лемма 2. Если а = вq + r, то НОД (а, в) = НОД (в, r).

Доказательство. Пусть d – какой-либо общий делитель чисел (а, в), т.е. а d Ù в d. Тогда r = (а – вq) d по теореме о делимости разности и произведения, следовательно, в – есть общий делитель (в, r).

Пусть теперь d¢ – какой-либо общий делитель чисел в и r, т.е. в d¢ Ù r d¢. Тогда а = вq + r тоже делится на d¢ в силу делимости суммы и произведения. Следовательно, d¢ – является общим делителем для чисел а и в.

Таким образом, мы установили, что всякий общий делитель для чисел а и в является общим делителем для в и r, и, обратно, всякий ОД для чисел в и r является ОД чисел а и в. А это значит, что множество всех ОД чисел а и в совпадает с множеством ОД чисел в и r. Тогда НОД (а, в) = НОД (в, r). Что и требовалось доказать.

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

Если а разделить на в с остатком, затем в разделить с остатком на первый остаток r ₁, затем r ₁, разделить на r ₂, затем r ₂ разделить на r ₃ и так далее, то последний, отличный от нуля остаток равен НОД (а, в).

Доказательство. Выпишем все неравенства, которые возникают в процессе последовательного деления, описанного в условии теоремы:

1) а = вq ₁+ r ₁, где 0 ≤ r ₁ < в,

2) в = r ₁ q ₂+ r ₂, где 0 ≤ r ₂ < r ₁,

3) r ₁= r ₂ q ₃+ r ₃, где 0 ≤ r ₃ < r ₂,

4) r ₂= r ₃ q ₄ + r ₄, где 0 ≤ r ₄ < r ₃,

… … ……

n – 1) r_{n -3}= r_{n -2} q_{n -1} + r_{n -1}, где 0 ≤ r_{n -1} < r_{n -2},

n) r_{n -2}= r_{n -1} q_n + r_n, где 0 ≤ r_n < r_{n -1},

n + 1) r_{n -1}= r_nq_{n +1} + r_{n +1}, где r_{n +1} = 0.

Прежде всего, отметим, что, что процесс последовательного деления не может быть бесконечным, т.к. получающиеся в последовательных делениях остатки r ₁, r ₂, r ₃, … являются целыми неотрицательными числами и образуют убывающую последовательность
r ₁ > r ₂ > r ₃>.. …, а убывающая последовательность целых неотрицательных чисел не может содержать бесконечного множества элементов. Поэтому через конечное число таких последовательных делений обязательно получается остаток равный нулю. В нашей записи таким остатком является остаток r_{n +1}, полученный при (n + 1) последовательном делении. Последний не равный нулю остаток r_n.

Докажем, что r_n и есть НОД (а, в). Действительно, из выписанных выше равенств 1), 2), …, n – 1), n), n + 1), выражающих процесс последовательного деления на основе лемм 1 и 2, заключаем, что НОД (а, в) = НОД (в, r ₁) = НОД(r ₁, r ₂) = НОД (r ₂, r ₃) = … =НОД (r_{n -3}, r_{n -2}) = НОД (r_{n -2}, r_{n -1}) = НОД (r_{n -1}, r_n) = r_n. Что и требовалось доказать.

Приведём пример, на котором покажем краткую запись алгоритма. Пусть нужно найти НОД (816, 323).

Процесс последовательного деления удобно записывать в виде многократного деления углом:

Следствие. Множество всех делителей НОД (а, в)есть в то же время множество всех общих делителей чисел а и в.

Например, НОД(120, 160) = 40. Все общие делители чисел 120 и 160 – это делители числа 40: 1, 2, 4, 5, 8, 10, 20, 40.

НОД нескольких (более двух) чисел находится по теореме 2, § 2.

П р и м е р. Найти НОД (5912, 8868, 13302, 18475).

1) НОД(5912, 8868) = 2956,

2) НОД(2956, 13302) = 1478,

3) НОД(1478, 18475) = 739,

4) НОД(5912, 8868, 13302, 18475) = 739.

НОК этих чисел можно найти, используя теорему о связи НОД и НОК двух чисел (теорема 1, § 12).

Не нашли, что искали? Воспользуйтесь поиском: