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

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

[pic]

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

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

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

Содержание:

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

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

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

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

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

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

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

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

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

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

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

К

[pic]

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

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. Тогда нашу цепочку вычислений можно записать так:

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

[pic] [pic]

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.

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

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

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

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

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

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

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

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

Например, для чисел 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