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

Линейное диофантово уравнение — это уравнение вида 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, то мы свели задачу к уравнению с взаимно простыми коэффициентами, у которого решения гарантированно есть.

> Нелинейные диофантовы уравнения

В прошлый раз мы разобрали линейные:

ax + by = c

У таких уравнений есть достаточно чёткое решение. В этом их главное отличие от нелинейных: Для их решения необходимо не просто подставить в формулу, а подумать

> Какие уравнения называются нелинейными? (На всякий случай напомню)
Это любые уравнения, где есть произведения переменных или их степени. Пример:

x² + y² = z²
x² − 2y² = 1
xy = 12
x³ + y³ = z³

1️⃣ xy = n
Напомню: x и y - искомые переменные, значения которых должны быть целыми (Мы ведь решаем диофантово уравнение).
Тут всё просто:
x и y должны быть делителями n.
Пример

xy = 12
x и y должны быть делителями 12.
12 делится на:
1, 2, 3, 4, 6, 12 (и ещё отрицательные)
Значит решения:
(1,12), (2,6), (3,4), (4,3), (6,2), (12,1)
и также
(-1,-12), (-2,-6), …

2️⃣ Квадраты: x² = k
Тоже нелинейное, но не слишком сложное
Как решать:
Решить как обычное уравнение, получиться ±√k. Если эти числа целые, то они и будут корнями выражения. Иначе нет корней
Пример:

x² = 49 → x = 7 или x = -7
x² = 50 → целых решений нет (потому что √50 - нецелое число)

3️⃣ Чуть интереснее: x² + y² = z²
Это те самые Пифагоровы тройки. Их бесконечно много, все решения не перечислить
Но есть формула генерации Пифагоровых троек:

Берём два целых числа m и n, где m > n
a = m² − n²
b = 2mn
c = m² + n²

Пример:

m = 2, n = 1
a = 4 − 1 = 3
b = 221 = 4
c = 4 + 1 = 5
Получили (3,4,5)

Если интересен вывод формулы генерации, ставь 💯 на пост

4️⃣ Уравнения Пелля
Уравнения вида x² − Dy² = 1
где D — не квадрат целого числа.
Пример:

x² − 2y² = 1
y = 0 → x² = 1 → x = ±1 ✅
y = 1 → x² = 3 → нет
y = 2 → x² = 9 → x = 3 ✅
...

Здесь решений бесконечно много

В следующих постах подробнее поговорим о Пифагоровых тройках и уравнении Пелля