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

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

Определение

Число 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 .

Имеем: b > r ₁ > r ₂ >... > r _n > 0, следовательно процесс оборвется максимум через b шагов.