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

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

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

Лемма 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).

Вопросы и задания для самопроверки

1. Прочитайте записи 21 3, 24 6, 15 5, 20 4 = 5.

2. Истинны ли следующие высказывания:

«Свойства отношения делимости не зависят от системы счисления», «Признаки делимости зависят от системы счисления»?

3. Сформулируйте признак делимости на 6 в двенадцатеричной системе счисления.

4. Запишите 10 подряд идущих составных чисел, сделайте это без подбора.

5. Назовите способы нахождения НОД и НОК двух чисел.

ГЛАВА XI

РАСШИРЕНИЕ ПОНЯТИЯ ЧИСЛА. ЦЕЛЫЕ ЧИСЛА.

РАЦИОНАЛЬНЫЕ ЧИСЛА

Две практические потребности: подсчет числа элементов конечного множества и измерение величин привели к возникновению понятия числа. При подсчете предметов ответ всегда выражается натуральным числом. Однако, если выражать натуральным числом изменение количества элементов конечного множества, то потребуются дополнительные указания (произошло уменьшение или увеличение). Значит, целесообразно дополнить множество натуральных чисел «новыми» числами, применение которых учитывает не только величину, но и направление. В главе VIII данного пособия рассмотрен случай, когда измеряемая величина состоит из нескольких, равных единице измерения, частей и результат измерения выражается натуральным числом. Однако, не всегда единица величины укладывается целое число раз в измеряемой величине и тогда для того, чтобы выразить результат потребуются новые числа, отличные от натуральных.

Итак, для практических потребностей запас только натуральных чисел оказался недостаточным.

С точки зрения математической теории на очень ранней ступени развития понятия числа с полной определенностью выяснилось, что только натуральными числами обойтись невозможно и требуется введение новых чисел, расширение понятия числа. Без этого над числами нельзя производить таких простейших арифметических действий как вычитание и деление, а эти действия над натуральными числами уже выводят за пределы натуральных чисел. Так за множеством натуральных чисел последовало множество целых чисел, множество рациональных чисел, потом – множество действительных чисел; далее – множество комплексных чисел, причем каждое из перечисленных множеств содержит предыдущее, являясь его расширением, а исходным множеством в процессе расширения понятия числа является множество N натуральных чисел.

Дата добавления: 2015-07-18