Обратные остатки

Первое решение. Запишем последовательно шаги алгоритма Евклида:

Тогда Теперь в обратную сторону будем восстанавливать и Возьмём Тогда Пусть

и

где все числа целые. Такие найдутся, поскольку и были получены с помощью деления с остатком. Тогда

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Для начала докажем небольшую лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть Тогда существует целое такое, что

Доказательство. Рассмотрим последовательность Ясно, что при всех натуральных Тогда остается возможный остаток при делении на который может появиться у чисел этой последовательности. По принципу Дирихле для некоторых имеем Будем считать, что и, используя взаимную простоту, получим Положим

______________________________________________________________________________________________________________________________________________________

Рассмотрим уравнение Можно полагать, что (в противном случае разделим обе части на ). Итак, все свелось к решению уравнения По модулю получим Такое сравнение, исходя из леммы, имеет решение, что равносильно наличию решения уравнения по определению сравнений по модулю.