Категория: Теория чисел Добавил: Admin Дата публикации: 09.08.2014
1621
0

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

Ключевые слова: теория чисел, лекции, примеры решений задач.

Пусть даны два числа 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 > r1 > r2 >... > rn > 0, следовательно процесс оборвется максимум через b шагов.

Пример. Пусть а = 525, b = 231. Алгоритм Евклида: (ниже приводится запись деления уголком, и каждый раз то, что было в уголке, т.е. делитель, приписывается к остатку от деления с левой стороны, а остаток, как новый делитель, берется в уголок)

 

Запись того же самого в виде цепочки равенств:
 

Таким образом, (525, 231) = 21. Линейное представление наибольшего общего делителя:
 




avatar