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

В задаче будем искать наибольший положительный НОД, но будем считать, что числа в алгоритме Евклида могут быть отрицательными. Тогда по алгоритму Евклида

Заметим, что Докажем небольшую лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть — простое число. Тогда и и

Доказательство. Действительно, пусть и Мы знаем, что или С другой стороны, тогда возможно в том и только в том случае, если и Все переходы равносильны, и лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Таким образом, если числа и имеют общий делитель то все простые числа являются делителями чисел и Поскольку то все такие простые числа являются делителями Тогда, если простое число делит и и то оно равно Таким образом, Получаем после подстановки в выражение для НОД

Заметим, что Тогда по лемме простое число, делящее либо равно либо делит оба числа и По алгоритму Евклида Таким образом, любое простое число, делящее равно Следовательно, Снова подставляем!

Снова заметим, что однако числа и взаимно просты, поэтому общих делителей у и нет. Это значит, что тогда Положим тогда и Так как получаем и Таким образом, мы получили и пример, и оценку.