Конспект №2
Алгоритм Евклида.
Наибольший общий делитель (НОД) двух натуральных чисел а и b обозначим как (а,b). Рассмотрим задачу о нахождении (а,b). Ну, во-первых, можно разложить оба числа на простые множители: а=р1p2…pn; b=q1q2…qm. Здесь какие-то р и q могут быть равными (чтобы не использовать степени мы их повторяем столько раз, сколько они встречаются в разложении а и b на множители). Какие-то р и q входят в разложение обоих чисел, являются общими простыми множителями для чисел а и b. Перемножим их все и получим число d, которое и будет являться НОД для чисел а и b. а=dP; b=dQ.
У чисел P и Q у же нет общих множителей, кроме 1, то есть, они взаимно просты.
Пример. Найдём (1665, 2763).
По признакам делимости, сразу видим, что оба числа делятся на 9: 1665=9185; 2763=9×307. Проверкой (делением на 7, 13 и 17) убеждаемся, что 307 – простое число и потому (1665, 2763)=9. Всё бы хорошо, но у этого способа есть один недостаток.
Он состоит в том, что иной раз затруднительно бывает разлагать число на множители (если делителями его являются большие простые числа) и проверять, является ли множитель простым. Существует, однако, другой способ нахождения НОД – с помощью алгоритма Евклида. Пусть, например, a>b. Пусть d-общий делитель a и b.
Тогда d-общий делитель также a-b и b.
Упражнение 1. Докажите это.
Продолжая далее таким же образом, получим, что d -общий делитель также a-2b и b, общий делитель a-3b и b,…, общий делитель a-q1b и b, где 0≤a-q1b<b. То есть, мы, фактически, разделили число а на число b с остатком: обозначив a-q1b за r1, имеем a=q1b+r1, где 0≤r1<b. При этом оказалось, что d -общий делитель a, b и r1.
Теперь оставим а и разделим b на r1: b=r1q2+r2. 0≤r2< r1. При этом d -общий делитель b, r1и r2. Продолжая эту процедуру, получим:
r1=r2q3+r3; 0≤r2<r1
r2=r3q4+r4; 0≤r3<r2
....................................
Убывающая последовательность натуральных чисел b>r1>r2>r3>… обязательно закончится нулём, так как иначе процесс деления продолжится, а бесконечно продолжаться он тоже не может, так как любая убывающая последовательность натуральных чисел конечна. Итак, при каком-то n, получим
rn-2=rn-1×qn+rn; 0≤rn<rn-1
rn-1=rn×qn+1 (rn+1=0)
В
последовательности a,b,r1,r2,...,rn-1,rn
d – общий делитель a,
b и r1,
общий делитель b, r1и
r2,…,общий делитель
rn-2,
rn-1
и rn..
То есть, d – общий делитель
всех этих чисел, в том числе a,
b и rn.
Таким образом, любой общий делитель a
и b служит также делителем
rn. В
том числе, и наибольший общий делитель
a и b, обозначим
его D. Так как D
делит rn,
то D
rn.
Пройдём теперь по последовательности
равенств в обратном порядке, снизу
вверх:
a=q1b+r1 0≤r1<b
b=r1q2+r2 0≤r2<r1
r1=r2q3+r3; 0≤r2<r1
r2=r3q4+r4; 0≤r3<r2
....................................
rn-2=rn-1×qn+rn;
rn-1=rn×qn+1
Из последнего равенства следует, что rn делит rn-1. Так как rn делит также и самого себя, то из предпоследнего равенства следует, что rn делит и rn-2. Поднимаясь вверх, доходим до четвёртого сверху равенства: rn делит r4 и r3 rn делит r2; из третьего: rn делит r3 и r2 rn делит r1; из второго: rn делит r2 и r1 rn делит b;и, наконец, из первого: rn делит r1 и b rn делит a. Итак, rn оказался общим делителем a и b rn D. Но (D rn)(rn D) rn=D. Итак, мы обосновали алгоритм Евклида нахождения НОД двух натуральных чисел.
Упражнение 2.
С помощью алгоритма Евклида найдите НОД 368 и 437; 493 и 899; 574 и 1763.