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

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 13Следующая ⇒

  Евклида

Определение 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) является

, где .

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

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

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

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США