Статья Нахождение НОД с помощью Алгоритма Евклида

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

Воробьева Ю.А.

Санкт-Петербург 2016 г.

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

Содержание:

1.Алгоритм: как это начиналось.

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

3. Арифметика отрезков.

1. Алгоритм: как это начиналось.

Слово алгоритм в наше время, знакомо, наверное, каждому. И связываем мы его обычно с очень современными вещами: компьютерами и их разнообразными применениями. Однако и это само слово, и те понятия, которые с ним связывают, имеют очень давнюю и почтительную историю.

Сейчас алгоритмом называют почти любую инструкцию, которая описывает в каком порядке и какие действия нужно выполнить, чтобы достичь того или иного результата. Так что приготовление торта - тоже алгоритм.

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

• Любой алгоритм создается для достижения какой-то совершенно конкретной цели

• Эта цель достигается за конечное число шагов (или за конечное число шагов выясняется , что цели достигнуть невозможно.

• Каждый шаг определяется результатами предыдущих шагов и начальными условиями

Типичный пример такого алгоритма -деление чисел «уголком».Его цель- по двум целым числам a,b найти целое число с , такое что a=bc. Каждый шаг деления однозначными числами a и b, и за конечное число шагов мы либо находим нужное число с, либо обнаруживаем, что числа с такими свойствами нет (пи этом деление выполняется с остатком).

К

стати, появление самого слова, алгоритм связано с правилами арифметических действий. Несмотря на то, что цифры, которые мы используем часто называют арабскими, придумали в Индии около v века н.э. Затем их освоили математики арабского Востока, а уже оттуда сведения о них проникли в Европу. Примерно в 825 году один из самых знаменитых ученых своего времени Мухаммед ибн Мусса Аль-Хорезми, работавший в Багдаде, написал книгу, в которой подробно описывал правила десятичной арифметики. В начале XII века в Европе был издан латинский перевод этой книги под названием Algoritmi de numero Indorum.Первым словом в этом названии стояло переделанное по образцам имя автора, то есть, книга должна была называться «Аль-Хорезми об индийском счете». Но очень скоро слово алгоритм стало нарицательным , и превратилось в название любых способов вычисления десятичной записи.

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

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

Н

Основной шаг алгоритма Евклида- это деление с остатком.

Если a,b два целых положительных числа, то разделив a на b, мы однозначно определим пару целых неотрицательных чисел q и r,таких, что

a=bq+r

( если a меньше b, то q=0, если b является делителем a, то r=0)аша ближайшая цель - познакомиться с одним из самых древних знаменитых алгоритмов - алгоритмом Евклида . Он придуман более двух тысячилетий назад для отыскания наибольшего делителя (НОД) двух целых чисел.остатком несколько раз подряд .

Попробуем применить деление с остатком несколько раз подряд (начнем с пары чисел a,b , затем прейдем к b,r и так далее). Например, для пары чисел330 и 144 мы получим цепочку равенств:

330=144*2+42, 144=42*3+18, 42=18*2+6, 18=6*3+0.

На последнем шаге остаток оказался равным 0, следовательно, продолжать деление дальше невозможно.

Итак, процесс остановился. Что же мы получили? У нас образовалась цепочка последовательных остатков 42,18 и 6. Нетрудно проверить, что последний из них является НОД исходных чисел a и b, то есть НОД(144,330)=6.

Процедура, которую мы сейчас выполнили ,- это и есть алгоритм Евклида. Давайте его рассмотрим более внимательно.

На каждом шаге алгоритма у нас образуется два новых числа: неполное частное и остаток. Будем обозначать частное, которое получается при i-ом делении q, а остаток, полученный при этом делении, обозначим ri. Тогда нашу цепочку вычислений можно записать так:Если a и b делятся

Тоже на d, тогда r1,r2,…rn делятся на d

1. а=bq1+r1

2. b=r1q2+r2

3. r1=r2q3+r3

……………

n. rn-2=rn-1qn+rn

n+1. rn-1=rnqn+1

На rn делятся все остальные остатки r1,r2,…rn-1

Мы здесь выполнили n+1 шаг, считая, что на шаге с номером n+1 получается остаток, равный 0, и процесс вычислений прекращается. Но сразу же возникает вопрос: всегда ли такой процесс должен оборваться за конечное число шагов?

Что бы понять это, заменим делитель на каждом шаге, начиная со второго, равен остатку, полученному на предыдущем шаге. Поэтому в нашей цепочке остатков каждый новый член строго меньше предыдущего, то есть, r1>r2>r3>…rn.

Но убывающая цепочка целых положительных чисел не может быть бесконечной (если она начинается с числа k, то в ней не больше членов, чем k).

И

Теперь нам понадобится простое, но очень важное свойство делимости :

Если в равенстве x = y+z какие-то два члена делятся на число d, то и третий член этого равенства делится на d.так, процесс вычислений на каком-то шаге должен прекратиться. Но что может помешать нам продолжать его? Только одно: если очередной остаток равен 0, то следующий шаг деления становится невозможным. На этом шаге наша цепочка равенств оборвется.

Посмотрим на последнее равенство нашей цепочки =r. Из него следует, что остаток является делителем предпоследнего остатка

в нашем примере последний остаток - это 6, а предпоследний -18).

Но если мы поднимемся по этой цепочке еще на одну строчку вверх ( к равенству с номером n), то заметим, что в правой части оба слагаемых делятся на . Значит и число влевой части этого равенства тоже делится на .

Продолжая эти рассуждения , мы дойдем до самого первого равенства a=bq+r

И обнаружим, что оба исходных числа a и b делятся на .

С другой стороны, из этого первого равенства следует, что если какое-то число d является делителем и a, и b, то первый остаток тоже делится на d.

Итак, мы выяснили, что алгоритм Евклида обязательно завершится за конечное число шагов, и последний остаток, не равный 0, который получается при этом, равен наибольшему общему делителю двух исходных чисел.Таким образом , число является общим делителем a и b, и при этом само делится на каждый их общий делитель. Но в точности значит, что является наибольщим общим делителем чисел a и b, тоесть, НОД(a,b)=

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

Например, для чисел 4099 и 4127 алгоритм Евклида дает быстро понять, что их НОД равен 1. Действительно, 4127=4099*1+28, 4099=28*146+11, 28=11*2+6, 11=6*1+5, 5=1*5

А теперь попробуйте разложить эти числа на множители! Вам потребуется затратить немало сил. Дело в том, что эти числа - простые, и чтобы понять это, вам придется перепробывать деление на все простые числа до 61 (кстати, подумайте ,почему этого достаточно).

3.Арифметика отрезков.

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

В течении более чем двух тысяч лет эта книга служила образцом ясного и логически стройного изложения. Евклид очень четко разделял

• Определения, т.е. точные описания объектов, о которых идет речь

• Постулаты и аксиомы- это утверждения, истинность которых не требует доказательств.

• Теоремы, т.е. утверждения, истинность которых подтверждается рассуждением.

Такой способ описания теории стал основным сначала в математике, с потом и в других точных науках. Те из вас, кто уже познакомился с геометрией, заметили несомненное сходство.

Алгоритм для нахождения НОД двух чисел Евклид назвал антанарезис (что примерно означает взаимное вычитание).

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

Если меньший отрезок целое число раз укладывается в большем, то Евклид говорит, что меньший отрезок измеряет больший ( это равносильно тому, что большее число делится на меньшее без остатка).

Применим этот способ рассуждения е нашему примеру. Пусть отрезок АВ имеет 330, а СD -144. Если мы вычтем из АВ отрезок СD , то оставшийся отрезок ЕВ будет по прежнему больше , чем СD ( его длина будет186).Значит, надо вычесть СD еще раз. Теперь оставшийся отрезок ВF =42, меньше, чем СD, и мы будем вычитать его из СD до тех пор, пока не получим меньшую величину (вычесть придется 3 раза). Оставшийся отрезок DI =18 будем «укладывать» в ВF ( он уложится там дважды, и , остаток ВК будет иметь длину 6). На последнем шаге видим, что ВК укладывается в DI ровно 3 раза, следовательно, процесс завершился.

B

K

F

E

A

АВ=2СD+BF

CD=3BF+DI

BF=2DI+BK

DI=3BK

D

I

H

G

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