Разбор типовых примеров к первому индивидуальному домашнему заданию по теме «Делимость целых чисел и многочленов»

1. Диофантовы уравнения.

Решите диофантово уравнение 903x + 994 y = 14

Сначала найдём наибольший общий делитель коэффициентов в левой части, то есть НОД (903, 994).

Применим алгоритм Евклида.

994 = 903 ∙ 1 + 91

903 = 91 ∙ 9 + 84

91 = 84 ∙ 1 + 7

84 = 7 ∙ 12

Таким образом, НОД (903, 994) = 7.

Разделим обе части уравнения 903x + 994 y = 14 на 7.

Получим 129 x + 142 y = 2.

Найдём пару целых чисел x и y, таких, что 129 x + 142 y = 1.

Для этого воспользуемся обобщённым алгоритмом Евклида.

Сначала найдём НОД (129, 142) (мы уже знаем, что он равен 1, но результаты вычислений понадобятся нам для промежуточных выкладок).

142 = 129 ∙ 1 + 13

129 = 13 ∙ 9 + 12

13 = 12 ∙ 1 + 1

12 = 1 ∙ 12

Теперь эти выкладки рассматриваем от конца к началу, то есть выразим 1 как линейную комбинацию 13 и 12, затем – как линейную комбинацию 129 и 13, и, наконец, как линейную комбинацию 142 и 129.

1 = 13 – 12 = 13 – (129 – 13 ∙ 9) = 13 – 129 + 13 ∙ 9 = 13 ∙ 10 – 129 = (142 - 129) ∙ 10 – 129 = 142 ∙ 10 – 129 ∙11

Итак, мы нашли и такие, что .

Но, поскольку уравнение имеет вид 129 x + 142 y = 2, то два найденных числа умножим на 2, то есть в качестве частного решения возьмём и .

Теперь найдём общее решение. Если в уравнении 129 x + 142 y = 2 величину x уменьшить на 142, а величину y увеличить на 129, то сумма не изменится, поскольку величина 129 ∙ 142 к одному слагаемому прибавляется, а из другого слагаемого вычитается.

Поэтому можем общее решение записать так.

x = -22 – 142 t, y = 20 + 129 t, t – произвольное целое число.

Это и будет ответом.

Ответ. x = -22 – 142 t, y = 20 + 129 t, t – произвольное целое число.

Примечание 1.

Если в условии стоит не сумма, а разность, например, 129 x – 142 y = 2, то величины
142 t и 129 t нужно будет брать с одним знаком, поскольку в этом случае увеличение чисел 129 x и 142 y будет происходить на одно и то же число. Поэтому их разность не изменится.

Примечание 2.

В этой задаче, как и во многих других задачах данной серии, можно проверить свой ответ, подставив числа в исходное уравнение или в уравнение 129 x + 142 y = 2 (если вы уверены, что правильно сократили).

Подставим их.

129(-22 – 142 t) + 142 (20 + 129 t) = 129 ∙ (-22) – 129 ∙ 142 t + 142 ∙ 20 + 142 ∙ 129 t =
129 ∙ (-22) + 142 ∙ 20 = 2.

При этом, если вы не учли примечание 1 и ошиблись со знаками, то при проверке это сразу увидите.