Алгоритм Евклида и расширенный алгоритм Евклида.

 

Пусть даны , и требуется найти их НОД. Пусть при этом . Разделим большее на меньшее с остатком . Затем второе на остаток, снова, возможно с остатком . Затем первый остаток на второй, получив остаток  :  

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

 

Теорема 5. Остаток , полученный при алгоритме Евклида, является: 1) общим делителем для

2) наибольшим среди общих делителей. 

Доказательство.

Из последнего равенства видно, что  делится на . Тогда из предпоследнего   видно, что  делится на , так как оба слагаемых делятся на . 

Теперь, когда известно, что  и  делятся на , очевидно, что из равенства  следует, что и  тоже делится на . Продолжая таким образом подниматься всё выше, дойдём до того, что  и  делятся на .

А тогда и левые части первых двух равенств:  

делятся на . Итак,  общий делитель для . 

 

2) Докажем, что это и есть наибольший общий делитель. Пусть = , но . Из первого равенства, , тогда , то есть если  делятся на , то и  делится на . 

Далее, из второго равенства, , если  и  делятся на , то и  делится на . Аналогично следуя далее, дойдём до того, что и  делится на . Но тогда  не наибольший общий делитель, а по условию, он наибольший. Значит, .  

(Теорема 2). Если = , то существуют такие , что .
Рассмотрим другое доказательство, получающееся из алгоритма Евклида, и дающее возможность непосредственно найти .

(это построение  называется расширенным алгоритмом Евклида).

Из предпоследнего, , то есть НОД есть линейная функция от . В свою очередь, из предшествующего ему, можно выразить , таким образом, НОД  окажется выражен через :

 . 

Далее, поднявшись выше, можно выразить  через , таким образом,  окажется выражен через . В конце концов,  будет выражен через , которые из двух первых равенств

выражены через . То есть,  будет выражен через a,b как линейная комбинация, с коэффициентами u,v, состоящими из .

Если a делится на b без остатка, d=НОД(a,b) = b.

 

Пример. Для чисел  найти НОД, а также представление  (алгоритм Евклида и расширенный алгоритм Евклида). 

Решение. Делим столбиком, последнее 50 на 5 делится без остатка.

Здесь .

Последний остаток равен 5.

Теперь выразим , начиная с предпоследнего уравнения.

, где , подставляем одно в другое,

 = . 

, . 

 

Пример. Для чисел  найти НОД, а также представление . 

Решение.

Последний остаток равен 13.

 = . 

Проверка: . 

 

 

Определение. Натуральное число, большее единицы, называется простым, если оно не имеет натуральных делителей кроме себя и единицы. Не простые числа называются составными.

(число 1 не относится ни к простым, ни к составным).  

Примеры простых чисел меньше 100: 

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. 

 

ЛЕКЦИЯ 9. 11.03.2021.

 

Лемма 6. Всякое натуральное число, большее 1, делится по крайней мере на одно простое число.

 

Теорема 7. (Евклид).     Каково бы ни было конечное множество простых чисел , всегда найдётся простое число, не принадлежащее этому множеству.