Решение неопределенных уравнений при помощи алгоритма Евклида

Определение 6.1. Неопределенным уравнением будем называть уравнение вида , где и – коэффициенты уравнения, а буквами и обозначены неизвестные величины. При этом предполагается, что – целые числа, отличные от 0. Решить неопределенное уравнение, значит найти такие целые числа, которые будучи подставленными вместо неизвестных величин и , превращают уравнение в верное числовое равенство.

Частный случай. Рассмотрим частный случай неопределенного уравнения, когда правая часть уравнения равна 1:

(6.1)

Заметим, что по теореме 5.1, это уравнение имеет решение только в случае, когда . Пусть , – одно из решений уравнения (6.1). Тогда любая пара целых чисел и , вычисляемых по формулам

(6.2),

где , также является решением уравнения (6.1). Действительно,

.

Пара чисел, вычисленных по формулам (6.2), называется общим решением уравнения (6.1), при этом говорят, что числа , составляют частное решение данного уравнения.

Докажем, что множество решений уравнения (6.1) состоит только из чисел, полученных из некоторого частного решения , при помощи формул (6.2).

Пусть , – некоторое частное решение уравнения (6.1), а , – также решение этого уравнения. Тогда

– верные равенства.

Следовательно, . Последнее равенство означает, что b. Поскольку , имеем b (по следствию 2 к теореме о необходимом и достаточном условии взаимной простоты двух чисел ), а это и означает, что , где . Значит, , где .

Подставим в уравнение (6.1). Получим, что

.

Но

.

Поскольку (по определению неопределенного уравнения), .

Требуемое утверждение доказано.

Примеры.

1) Решим уравнение . Очевидно, что , значит уравнение имеет решение. Найдем НОД чисел 12 и 17 (который, как нам известно, равен 1) при помощи алгоритма Евклида. Для этого разделим на , получим . Таким образом, первый полученный остаток .

Далее, разделим на , получим , при этом .

Продолжим процесс деления:

, ;

, .

Таким образом, последний отличный от остаток равен 1, это и есть наибольший общий делитель чисел и . Найдем линейное представление НОД:

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

Общий случай. В общем случае правая часть неопределенного уравнения может быть любым целым числом:

. (6.3)

Пусть – наибольший общий делитель чисел и . Это значит, что d и d. Поэтому для того, чтобы уравнение (6.3) имело решение необходимо и достаточно, чтобы d.

Пусть d. Разделим обе части уравнения (6.3) на . Получим уравнение, равносильное уравнению (6.3),

. (6.4)

По свойству НОД, установленному теоремой 3, числа и взаимно просты. Тогда составим вспомогательное уравнение

. (6.5)

Найдем его частное решение , – при помощи алгоритма Евклида, так же, как выше было найдено решение уравнения (6.1).

Тогда, очевидно, в качестве частного решения уравнения (6.4) можно взять числа и , а общим решением уравнения (6.4) является

, где .

Пример. Решим уравнение . Поскольку , уравнение имеет решение. Составим вспомогательное уравнение:

. При помощи алгоритма Евклида представим НОД чисел и в виде линейной комбинации этих чисел с целыми коэффициентами:

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