Этот пост я постараюсь сделать максимально простым для понимания
👍 Диофантовы уравнения
Думаю, многие впервые слышат это понятие. Диофантово уравнение - то же уравнение, но обязательно с целыми коофицентами и решениями.
Может быть не очень понятно, поэтому давайте разберёмся на примере
В данной ситуации, нам неизвестны
➡️ Диофантовые уравнения делятся на линейные и нелинейные. Отличаются они тем, что для линейных метод решения однозначнее.
Линейное диофантово уравнение - то, которое может представить как
Решений в уравнении может не быть совсем, может быть несколько или бесконечно много. Диофантовы уравнения хороши тем, что практически нет общего алгоритма их решения - над каждым уравнением надо подумать
Думаю, многие впервые слышат это понятие. Диофантово уравнение - то же уравнение, но обязательно с целыми коофицентами и решениями.
Может быть не очень понятно, поэтому давайте разберёмся на примере
a² + b² = c² (Это кстати, теорема Пифагора)
В данной ситуации, нам неизвестны
a, b, c. Если решать это как обычное уравнение, то ответами могут быть например a=1.5 b=2 c=2.5. Но если представлять уравнение, как диофантово, то это решение не подходит - a, b, c должны быть целыми. Такие числа, в примере с теоремой Пифагора называются Пифагоровыми тройкамиЛинейное диофантово уравнение - то, которое может представить как
ax + by = c, где a, b, c - целые числа, а x и y - искомые переменныеРешений в уравнении может не быть совсем, может быть несколько или бесконечно много. Диофантовы уравнения хороши тем, что практически нет общего алгоритма их решения - над каждым уравнением надо подумать
Please open Telegram to view this post
VIEW IN TELEGRAM
🖥 Линейные диофантовы уравнения
Линейное диофантово уравнение — это уравнение вида ax + by = c, где a, b и c — целые числа, а x и y нужно найти среди целых.
❓ Главный вопрос: существуют ли такие x и y, что равенство выполняется?
Решение существует только если число c делится на наибольший общий делитель (НОД) чисел a и b. Если для уравнения ax + by = c, gcd(a, b) не делит c, то целых решений нет.
gcd = НОД
Если делит — решений бесконечно много, и их можно записать в общем виде.
📌 Пример:
Каждое значение t даёт новую пару (x, y), и все они подходят. Если заменить 1 на другое число, например 10, то нужно умножить найденное решение на 10:
Для уравнения с одной переменной, например ax = c, всё проще: x = c / a, и решение есть только если a делит c. Но это уже школьная алгебра
Почему это так работает
Если записать gcd(a, b) = d, это значит, что a и b можно представить так:
где a₁ и b₁ уже взаимно просты, то есть их gcd(a₁, b₁) = 1. Подставим это в исходное уравнение:
Разделим обе части на d:
👀 Теперь видно: чтобы решения существовали, c / d должно быть целым. Если c не делится на d, то дробь получится нецелой, и целых x и y уже не найдёшь. Если же c делится на d, то мы свели задачу к уравнению с взаимно простыми коэффициентами, у которого решения гарантированно есть.
Линейное диофантово уравнение — это уравнение вида 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, то мы свели задачу к уравнению с взаимно простыми коэффициентами, у которого решения гарантированно есть.
❤9
> Нелинейные диофантовы уравнения
В прошлый раз мы разобрали линейные:
У таких уравнений есть достаточно чёткое решение. В этом их главное отличие от нелинейных: Для их решения необходимо не просто подставить в формулу, а подумать
> Какие уравнения называются нелинейными? (На всякий случай напомню)
Это любые уравнения, где есть произведения переменных или их степени. Пример:
1️⃣ xy = n
Напомню: x и y - искомые переменные, значения которых должны быть целыми (Мы ведь решаем диофантово уравнение).
Тут всё просто:
x и y должны быть делителями n.
Пример
2️⃣ Квадраты: x² = k
Тоже нелинейное, но не слишком сложное
Как решать:
Решить как обычное уравнение, получиться
Пример:
3️⃣ Чуть интереснее: x² + y² = z²
Это те самые Пифагоровы тройки. Их бесконечно много, все решения не перечислить
Но есть формула генерации Пифагоровых троек:
Пример:
Если интересен вывод формулы генерации, ставь 💯 на пост
4️⃣ Уравнения Пелля
Уравнения вида
где 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 ✅
...
Здесь решений бесконечно много
В следующих постах подробнее поговорим о Пифагоровых тройках и уравнении Пелля
💯17
> Пифагоровы тройки: Формула генерации
В прошлом посте, мы узнали о формуле генерации Пифагоровых троек (пролистай немного вверх в канале, если не видел):
> Почему из этой формулы всегда выходит тройка
Считаем:
> А откуда вообще взялась эта формула
Уравнение
то же самое, что
То есть точки
Если кто не понял: Сейчас мы просто заменили `a/c` на `x`, а `b/c` на `y`
Теперь воспользуемся теоремой: если взять любую прямую с рациональным наклоном, она пересечёт окружность в рациональной точке.
Берём прямую через точку (-1, 0) со склонением t:
мы взяли именно эту точку, потому что она лежит в окружности и она рациональная
Теперь подставляем
После упрощения получается рациональное решение:
Теперь делаем t рациональным: t = n/m (m, n целые)
Подставляем:
А теперь вспоминаем, что x = a/c и y = b/c, значит можно взять:
Вот и всё, мы и получили формулу генерации Пифагоровых троек.
Если есть идеи, что ещё доказать/разобрать, пиши в комментариях 👇
В прошлом посте, мы узнали о формуле генерации Пифагоровых троек (пролистай немного вверх в канале, если не видел):
Берём два целых числа m и n, где m > n
a = m² − n²
b = 2mn
c = m² + n²
> Почему из этой формулы всегда выходит тройка
Считаем:
a² + b²
= (m² − n²)² + (2mn)²
= (m⁴ − 2m²n² + n⁴) + 4m²n²
= m⁴ + 2m²n² + n⁴
= (m² + n²)²
= c² ✅
> А откуда вообще взялась эта формула
Уравнение
a² + b² = c²
то же самое, что
(a/c)² + (b/c)² = 1
То есть точки
(x,y)=(a/c,b/c) лежат на окружности:x² + y² = 1
Если кто не понял: Сейчас мы просто заменили `a/c` на `x`, а `b/c` на `y`
Теперь воспользуемся теоремой: если взять любую прямую с рациональным наклоном, она пересечёт окружность в рациональной точке.
Берём прямую через точку (-1, 0) со склонением t:
мы взяли именно эту точку, потому что она лежит в окружности и она рациональная
y - 0 = t(x - (-1))
y = t(x + 1)
Теперь подставляем
y в наше уравнение окружностиx² + [t(x+1)]² = 1
После упрощения получается рациональное решение:
x = (1 − t²)/(1 + t²)
y = 2t/(1 + t²)
Теперь делаем t рациональным: t = n/m (m, n целые)
Подставляем:
x = (m² − n²)/(m² + n²)
y = 2mn/(m² + n²)
А теперь вспоминаем, что x = a/c и y = b/c, значит можно взять:
a = m² − n²
b = 2mn
c = m² + n²
Вот и всё, мы и получили формулу генерации Пифагоровых троек.
Если есть идеи, что ещё доказать/разобрать, пиши в комментариях 👇
❤8