● Метод бесконечного (непрерывного) спуска.

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

Задание 1. Решить уравнение 5x+8y=39

Решение:

1. Первый этап решения задачи носит название «спуска» дробей.

Запишем уравнение в следующем виде:

Из этого представим (1) следующим образом: 4-3y=5z – полученное уравнение того же типа, что и изначальное, но с меньшими коэффициентами.

Проделываем такую же операцию, но уже относительно переменной y:

Так как по условию y – целое число, то выражение (1-2z)⋮3 можно записать следующим образом: 1-2z=3u.

Следуя аналогичным рассуждениям по выражению переменной с наименьшим коэффициентом при z, получим:

Так, предполагая, что (1-u)⋮2 – целое число, получим 1-u=2t, следовательно, выразив переменную u через t, замечаем, что дробей в полученном уравнении нет, поэтому «спуск» закончен.

2. Этап «поднятия вверх» по цепочке тех переменных, через которые использовалось выражение.

Так как u=1-2t, то, подставив u в уравнение, оно примет следующий вид:

3. Заключительный этап задания состоит в записи общего решения исходного уравнения: x=3+8y и y=3+8t, где t - произвольное целое число.

● Решение диофантовых уравнений с помощью алгоритма Евклида.

Интересный и простой способ решения линейных целочисленных уравнений.

Задание 2. Решите уравнение 24x-17y=2.

Решение:

Так как НОД(24;17)=1,то данное уравнение разрешимо в целых числах. Приступим к нахождению частного решения с помощью алгоритма Евклида.

Найдем линейное представление наибольшего общего делителя: 1=7-3·2=7-(17-7·2)·2=

=7-17·2+7·4+5·7-2·17=5·(24-17·1)-2·17=5·24-7·17=24·5-17·7

Отсюда получим, что 24·5-17· 7=1, значит, 24· 10-17· 14=2.

Сопоставив получившееся уравнение с исходным, можно записать частное его решение, при котором x0=10 и y0=14.

Тогда общим его решением будет являться следующая система:

● Решение диофантовых уравнений с помощью цепных дробей.

Задание 3. Решить уравнение в целых числах 127x-52y=-1

Решение:

для удобства использования этого метода будем придерживаться записи следующего вида:

Тогда, выделив целую часть дроби 6/5=1+1/5, придем к окончательному результату.

данное выражение называется конечной или непрерывной дробью. Следующий алгоритм по решению представленного задания будет таким:

1) Необходимо отбросить у получившейся дроби последнее звено (в данном случае 1/5).

2) Превратим полученную цепную дробь в простую с помощью преобразований в правой ее части: 127/52=22/9

3) Приведем полученное выражение к общему знаменателю, а после, отбросив его, сопоставим получившееся уравнение с исходным, что позволит найти его корни:

Следовательно, x=9, а y=22 – эти значения и будут являться решением исходного уравнения. По вышеизложенной теореме все его решения будут содержаться в прогрессиях вида:

● Решение диофантовых уравнений с помощью сравнений.

Задание 4. Решить уравнение

Решение: Левую и правую часть уравнения можно разделить на 2, в результате чего получим: 7x-5y=3 (1). Рассмотрев уравнение вида (1), найдем, что НОД (7;5)=1, следовательно, по ранее изложенной теореме в п.3 ∃x,y∈ Z . Затем выразим переменную y через х:

так как по условию необходимо, чтобы уравнение было разрешимо в целых числах, то 7x≡3(mod5). Так как НОД(7;5)=1, то существует только единственный способ решения данного уравнения. Поэтому по теореме Эйлера найдем:

Следующие методы решения диофантовых уравнений вынесены для самостоятельного ознакомления, так как ни в ЕГЭ, ни в ОГЭ, ни в школьных олимпиадах они не встречаются.

Ø Метод, основанный на выделении полного квадрата.

Ø Метод решения уравнения с двумя переменными как квадратного относительно одной из переменных.

Ø Метод решения уравнения Пелля.

Ø Метод решения уравнения Каталана.

Ø Метод решения уравнения Маркова.