Линейные уравнения

Линейные уравнения

Теперь мы знаем все, что нужно для решения диофантовых уравнений вида ах + by = с,

где а, b и c — произвольные целые числа. Чтобы решить это уравнение, нужно найти все пары целых чисел (х, у), которые удовлетворяют соотношению ах + by = с.

Посмотрим, как это сделать. Обозначим через d наибольший общий делитель а и b. По определению а и b делятся на d, следовательно, выражение ах + by также будет делиться на d. Так как согласно исходному уравнению ах + by = с, число d также должно быть делителем с. Следовательно, если с не делится на d, то уравнение не имеет решений. Так, решений не имеет уравнение 50х + 120у = 7. Мы уже показали, что наибольший общий делитель 50 и 120 равен 10, а 7 не делится на 10.

Далее будем предполагать, что с делится на d.

Тогда мы можем записать а = dp, b = dq и с = dr, где р и q — взаимно простые.

Сначала рассмотрим случай с = 0, то есть однородное уравнение ах + by = 0.

91

Разделив на d первый член уравнения, получим следующее: достаточно решить уравнение рх + qy = 0, или, что аналогично, рх = —qy. Будем рассуждать следующим образом: так как рх равно — qy, qy должно делиться на р. Однако р и q взаимно простые, следовательно, остается единственный вариант: у делится на р, то есть существует целое число ? такое, что у = ?р. Аналогично доказывается, что х делится на q, поэтому существует другое целое число ? такое, что х = ?q. Подставив значения х и у в уравнение, получим: ?pq = —?pq, то есть ? = —?, так как pq отлично от нуля. Следовательно, решениями уравнения ах + by = 0 будет пара чисел (q, —р) и всех кратных им чисел (?q, —?р).

Теперь предположим, что с отлично от нуля. Если известно два решения (x₀, у₀) и (х₁ y₁) уравнения ах + by = с, то:

а(х₀ - х₁) + b(у₀ - у₁) = (ах₀ + by₁-(ax₁+by₁) = с-с = О,

откуда следует, что (x₀ — x₁, у₀ — y₁) — решение однородного уравнения ах + by = 0.

Так как все решения этого уравнения имеют вид (?q, —?р), найдется целое число ? такое, что x₀ — x₁ = ?q и у₀ — у₁ = —?р, или, что аналогично, х = x₀ — ?q и y₁ = y₀ +?р. Иными словами, уравнение имеет бесконечно много решений, но все они выводятся из частного решения (x₀, у₀). Напомню, что р и q — результат деления а и b на наибольший общий делитель. Следовательно, мы доказали, что все решения выглядят так:

где (x₀, у₀) — частное решение, ? — любое целое число. Теперь всего лишь осталось найти метод, позволяющий получить (x₀, у₀). Найти эти решения нетрудно, если р и q — взаимно простые, так как по соотношению Безу существуют два целых числа u и v такие, что рu + qv— 1. Умножив u и v на r, получим два числа x₀ = ur и у₀ = vr такие, что ax₀ + by₀ = с.

Рассмотрим пример. Допустим, мы хотим решить диофантово уравнение 50х + 120у = 20.

Мы уже знаем, что наибольший общий делитель 50 и 120 равен 10.

Так как 20 делится на 10, уравнение имеет решение.

92

В этом случае в упрощенном виде уравнение выглядит так: 5х + 12у = 2. Найдем числа, которые мы обозначили через u и v. Так как 1 = 5 — 2 ·2 и 2 = 12 — 2·5, имеем

1 = 5 - 2 · (12 - 2 · 5) = 5 · 5 - 2 · 12,

то есть u = 5, v = —2. Умножив эти значения на 2, получим частное решение (10, —4), на основе которого можно найти общее решение: