Линейные диофантовы уравнения с двумя переменными
Диофантово уравнение с двумя неизвестными имеет вид:

где
— заданные целые числа,
и
— неизвестные целые числа.
Ниже рассматриваются несколько классических задач на эти уравнения: нахождение любого решения, получение всех решений, нахождение количества решений и сами решения в определённом отрезке, нахождение решения с наименьшей суммой неизвестных.
Вырожденный случай
Один вырожденный случай мы сразу исключим из рассмотрения: когда
. В этом случае, понятно, уравнение имеет либо бесконечно много произвольных решений, либо же не имеет решений вовсе (в зависимости от того,
или нет).
Нахождение одного решения
Найти одно из решений диофантова уравнения с двумя неизвестными можно с помощью Расширенного алгоритма Евклида.
Расширенный алгоритм Евклида по заданным
и
находит их наибольший общий делитель
, а также такие коэффициенты
и
, что:

Утверждается, что если
делится на
, то диофантово уравнение
имеет решение; в противном случае диофантово уравнение решений не имеет. Доказательство следует из очевидного факта, что линейная комбинация двух чисел по-прежнему должна делиться на их общий делитель.
Предположим, что
делится на
, тогда, очевидно, выполняется:

т.е. одним из решений диофантова уравнения являются числа:

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

Тогда заметим, что, прибавив к
число
и одновременно отняв
от
, мы не нарушим равенства:

Очевидно, что этот процесс можно повторять сколько угодно, т.е. все числа вида:

являются решениями диофантова уравнения.
Более того, только числа такого вида и являются решениями, т.е. мы описали множество всех решений диофантова уравнения (оно получилось бесконечным, если не наложено дополнительных условий).