🖥 Линейные диофантовы уравнения

🖥 Линейные диофантовы уравнения

Линейное диофантово уравнение — это уравнение вида ax + by = c, где a, b и c — целые числа, а x и y нужно найти среди целых.

❓ Главный вопрос: существуют ли такие x и y, что равенство выполняется?

Решение существует только если число c делится на наибольший общий делитель (НОД) чисел a и b. Если для уравнения ax + by = c, gcd(a, b) не делит c, то целых решений нет.

gcd = НОД

Если делит — решений бесконечно много, и их можно записать в общем виде.

📌 Пример:

3x + 7y = 1

НОД(3,7) = 1, а значит решение существует.

Найдём одно частное решение

Можно подобрать x = 5, y = -2, потому что 3*5 + 7*(-2) = 15 - 14 = 1.

Общее решение тогда:

x = 5 + 7t

y = -2 - 3t

где t — любое целое число.

Каждое значение t даёт новую пару (x, y), и все они подходят. Если заменить 1 на другое число, например 10, то нужно умножить найденное решение на 10:

3x + 7y = 10 → x = 50 + 70t, y = -20 - 30t.Для уравнения с одной переменной, например ax = c, всё проще: x = c / a, и решение есть только если a делит c. Но это уже школьная алгебра

Почему это так работает

Если записать gcd(a, b) = d, это значит, что a и b можно представить так:

a = d·a₁

b = d·b₁ где a₁ и b₁ уже взаимно просты, то есть их gcd(a₁, b₁) = 1. Подставим это в исходное уравнение:

a·x + b·y = c

d·a₁·x + d·b₁·y = c Разделим обе части на d:

a₁x + b₁y = c / d

👀 Теперь видно: чтобы решения существовали, c / d должно быть целым. Если c не делится на d, то дробь получится нецелой, и целых x и y уже не найдёшь. Если же c делится на d, то мы свели задачу к уравнению с взаимно простыми коэффициентами, у которого решения гарантированно ест