Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

§ 4. Алгорифм Евклида

1. Общая теория

Читатель прекрасно знаком с обычной процедурой "длинного" деления одного целого числа а на другое число b и знает, что эту процедуру можно продолжать до тех пор, пока остаток не станет меньше, чем делитель. Так, если а = 648 и b = 7, то мы получаем частное q = 92 и остаток r = 4.


По этому поводу можно сформулировать следующую общую теорему: если a и b - целые числа, причем b отлично от нуля, то можно всегда найти такое целое число q, что

а = b*q + r, (1)

где r есть целое число, удовлетворяющее неравенству 0≤r<b.

Докажем эту теорему независимо от процедуры длинного деления. Достаточно заметить, что число а или само есть кратное числа b, или же лежит между двумя последовательными кратными b:

bq<а<b(q + 1) = bq + b.

В первом случае равенство (1) оправдывается, причем r = 0. Во втором случае из первого неравенства вытекает, что

а - bq = r<0,

а из второго, что

а - bq = r<b,

так что число r в этом случае удовлетворяет условию 0<r<b.

Из отмеченного обстоятельства можно вывести большое число различных важных следствий. Первое из них - это метод для нахождения общего наибольшего делителя двух целых чисел.

Пусть а и b - два каких-то целых числа, не равных одновременно нулю; рассмотрим совокупность всех чисел, на которые делятся и а и b. Эта совокупность, несомненно, конечная, так как если, например, а≠ 0, то никакое число, большее чем а, не может быть делителем а. Отсюда следует, что число общих делителей а и b конечно: пусть через d обозначен наибольший из них. Число d называется общим наибольшим делителем а и b, и мы условимся обозначать его d = (а, b). Так, если а = 8, b = 12, то непосредственная проверка показывает, что (8, 12) = 4; если а - 5, b = 9, то мы точно так же получаем (5,9) = 1. Если а и b - достаточно большие числа, например, а = 1804, b = 328, то попытки найти общий наибольший делитель с помощью непосредственных проб довольно утомительны. Короткий и вполне надежный метод вытекает из алгорифма Евклида. (Алгорифмом называют всякий систематизированный прием вычисления.) Он основан на том обстоятельстве, что из соотношения вида

а = b*q + r (2)

необходимо следует, что

(а, b) = (b, r). (3)

В самом деле, всякое число u, которое одновременно делит и а и b

а = su, b = tu,

делит также и r, так как r = а - bq = su - qtu = (s - qt)u; и обратно, всякое число и, которое одновременно делит b и r

b = s'v, r = t'v,

делит также и а, так как а = bq + r = s'vq + t'v = (s'q + t')v. Значит, каждый общий делитель а и b есть вместе с тем общий делитель b и r, и обратно. Но раз совокупность всех общих делителей а и b совпадает с совокупностью всех общих делителей b и г, то ясно, что общий наибольший делитель а и b должен совпадать с общим наибольшим делителем b и r. А это и выражено равенством (3). Мы сейчас убедимся в полезности установленного обстоятельства.

Для этого вернемся к примеру нахождения общего наибольшего делителя чисел 1804 и 328. Обыкновенное "длинное" деление


приводит нас к заключению, что

1804 = 5*328 + 164.

Отсюда в силу (3) следует, что

(1804, 328) = (328, 164).

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


то мы получаем дальше 328 = 2*164 + 0, так что (328, 164) - (164,0) = 164. Значит, (1804, 328) = (328, 164) = (164,0) = 164, и общий наибольший делитель найден.

Эта самая процедура нахождения общего наибольшего делителя двух чисел в геометрической форме описана в "Началах" Евклида. Мы дадим ее общее описание в арифметической форме, исходя из произвольных целых чисел а и b, которые оба одновременно не равны нулю.

Так как сразу ясно, что (а,0) = а, то можно допустить, что b≠0. Последовательные деления приводят нас к цепи равенств:


Деление продолжается, пока какой-нибудь из остатков r1, r2, r3,... не обратится в нуль. Рассматривая неравенства, выписанные справа, мы видим, что последовательно получаемые остатки образуют убывающую последовательность положительных чисел:

b> r1> r2 > r3 > r4> ... > 0.

Отсюда ясно, что после конечного числа делений (нужно сделать не более b операций, но часто гораздо меньше, так как разности между соседними r обыкновенно превышают единицу) должен получиться остаток 0:

rn-2 = rn-1qn+rn,
rn-1 = rnqn+1 + 0.

Как только это получится, мы можем утверждать, что (а, b) = rn; другими словами, общий наибольший делитель (а, b) равен последнему остатку в последовательности (5). Это следует из повторного применения равенства (3) к соотношениям (4); в самом деле, из этих соотношений следует:

(а, b) = (b, r1), (b, r1) = (r1, r2), (r1, r2) = (r2, r3), (r2, r3) = (r3, r4), ..., (rn-1, rn) = (rn, 0) = rn.

Упражнение. Выполните алгорифм Евклида с целью нахождения общего наибольшего делителя: а) 187; 77; Ь) 105; 385; с) 245; 193.

Из равенств (4) можно вывести одно o чрезвычайно важное свойство общего наибольшего делителя (а, b): Если d = (а, b), то можно найти такие целые положительные или отрицательные числа k и l, что

d = ka + lb, (6)

Чтобы убедиться в этом, рассмотрим последовательные остатки (5). Первое из равенств (4) нам дает

r1 = a - q1b,

так что r1 может быть записано в форме k1a + l1b (в данном случае k1 = 1, l = -q1). Из следующего равенства получается: r2 = b - q2r1 = b - q2(k1a + l1b) = (-q2k1)a +

Очевидно, такое же рассуждение можно по очереди применить ко всем остаткам r3, r4,..., пока не придем к представлению

rn = ka + lb,

которое мы и желали получить.

В качестве примера рассмотрим алгорифм Евклида в применении к нахождению (61, 24): общий наибольший делитель есть 1, и интересующее нас представление числа 1 получается из равенств

61 = 2*24 + 13, 24 = 1*13 + 11, 13 = 1*11 + 2, 11 = 5*2 + 1, 2 = 2*1 + 0.

Первое из этих равенств дает

13 = 61 - 2*24,

второе -

11 = 24 - 13 = 24 - (61 - 2*24) = -61 + 3*24,

третье -

2 = 13 - 11 = (61 - 2*24) - (-61 + 3*24) = 2*61 - 5*24

и, наконец, четвертое -

1 = 11 - 5*2 = (-61 + 3*24) - 5(2*61 - 5*24) = -11*61 + 28*24.
предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Зачем математики ищут простые числа с миллионами знаков?

Задача построения новых оснований математики - унивалентные основания

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2018
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru