Решение неопределенных уравнений при помощи алгоритма Евклида
Определение 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) является
, где .
Пример. Решим уравнение 
. Поскольку 
, уравнение имеет решение. Составим вспомогательное уравнение:
. При помощи алгоритма Евклида представим НОД чисел 
и 
в виде линейной комбинации этих чисел с целыми коэффициентами:
. Таким образом, получим частное решение вспомогательного уравнения: 
и частное решение исходного уравнения: 
. Тогда общее решение исходного уравнения имеет вид: 
, где .
Дата добавления: 2021-03-18; просмотров: 89; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!