Реферат: Анализ алгоритма Евклида в Евклидовых кольцах
Одним из древнейших математических алгоритмов является алгоритм Евклида для нахождения наибольшего общего делителя двух положительных чисел. Вот его простейший вид. Пусть заданы два целых числа. Если они равны, то их наибольшим делителем будет каждое из них. В этом случае процесс заканчивается на первом шаге. Если они не равны, то вычитаем из большего числа меньшее. Это шаг алгоритма. Теперь рассмотрим вычитаемое и разность. Проделаем с ними ту же самую процедуру. Этот процесс будет продолжаться до тех пор, пока вычитаемое и разность не станут равны. Поскольку большее число в парах на каждом шаге уменьшается, но всегда не меньше единицы, то такой процесс не может продолжаться бесконечно, а закончится через несколько шагов.
Определение
Число d Î Z , делящее одновременно числа а , b , c , ... , k Î Z , называется общим делителем этих чисел. Наибольшее d с таким свойством называется наибольшим общим делителем. Обозначение:
d = ( a , b , c , ..., k )
Теорема . Если (a , b ) = d , то найдутся такие целые числа u и v , что
d = au + bv .
Определение. Целые числа a и b называются взаимно простыми, если
(a , b ) = 1.
Вспоминая свойство 1 из предыдущего пункта, легко заметить, что два числа a и b являются взаимно простыми тогда и только тогда, когда найдутся целые числа u и v такие, что au + bv = 1.
Пусть даны два числа a и b ; a ³ 0, b ³ 0, считаем, что a > b . Символом := в записи алгоритма обозначаем присваивание. Алгоритм:
1. Ввести a и b .
2. Если b = 0 , то Ответ: а . Конец .
3. Заменить r := "остаток от деления а на b ", а := b , b := r .
4. Идти на 2.
В современной буквенной записи, алгоритм Евклида выглядит так:
a > b; a, b Î Z .
| a = bq 1 + r 1 b = r 1 q 2 + r 2 r 1 = r 2 q 3 + r 3 r 2 = r 3 q 4 + r 4 | 0 £ r 1 < b 0 £ r 2 < r 1 0 £ r 3 < r 2 0 £ r 4 < r 3 |
| r n -3 = r n -2 q n -1 + r n -1 r n -2 = r n -1 q n + r n r n -1 = r n q n +1 | 0 £ r n -1 < r n -2 0 £ r n < r n -1 r n +1 = 0 |
Имеем: b > r 1 > r 2 >... > r n > 0, следовательно процесс оборвется максимум через b шагов.
1.1 Применение алгоритма Евклида
Как и всякая добротно выполненная работа, алгоритм Евклида дает гораздо больше, чем от него первоначально ожидалось получить. Из его разглядывания ясно, например, что совокупность делителей а и b совпадает с совокупностью делителей (a, b) . Еще он дает практический способ нахождения чисел u и v из Z (или, если угодно, из теоремы пункта 2) таких, что
r n = au + bv = (a, b) .
Действительно, из цепочки равенств имеем:
r n = r n -2 - r n -1 q n = r n -2 - (r n -3 - r n -2 q n -1) q n =. ..
(идем по цепочке равенств снизу вверх, выражая из каждого следующего равенства остаток и подставляя его в получившееся уже к этому моменту выражение)
... = au + bv = (a, b) .
Несомненно, описанная Евклидом процедура определения общей меры двух величин применительно к числам (а общая мера двух натуральных чисел, очевидно, есть их наибольший общий делитель) была изобретена задолго до Евклида. Таким же образом находили НОД и древние китайские математики. И только то, что эта процедура стала известна в эпоху Возрождения именно из «Начал, дало ей название « алгоритм Евклида»
Скорее всего, она возникла из коммерческой практики древних купцов, когда им надо было сравнивать различные отношения целых чисел. Как, например, сравнивать отношения чисел 3703700 и 1234567 и чисел 22962965 и 7654321? Вполне естественна была попытка узнать, сколько раз меньшее число укладывается в большем. Легко проверить, что 3703700 = 2 · 1234567 + 1234566, а 22962965 = 3 · 7654321 + 2. Ясно теперь, что отношение 3703700 к 1234567 меньше, чем отношение 22962965 к 7654321. Таким образом, что сейчас мы записываем как
= 2,99999919 <
= 3, 000000261,
Древние вычислители объясняли длинной фразой.
Если бы пришлось сравнить более близкие отношения чисел, например, 
и 
, то вычисления были бы более сложными:
71755875 = 61735500 + 10020375;