Калькулятор лінійного діофантового рівняння

Q: Як розв’язати лінійне діофантове рівняння вручну?

Спершу обчисліть g = gcd(a, b) алгоритмом Евкліда. Якщо g не ділить c, цілих розв’язків немає. Інакше застосуйте розширений алгоритм Евкліда, щоб знайти коефіцієнти Безу з g = sa + tb, помножте їх на c/g і отримайте x_0 = s · c/g та y_0 = t · c/g, а тоді запишіть усі розв’язки у вигляді x = x_0 + (b/g)t, y = y_0 - (a/g)t.

Q: Чи можна використовувати від’ємні коефіцієнти або від’ємну праву частину?

Так, усі три значення можуть бути від’ємними або нульовими — відкидаються лише дроби та десяткові числа. НСД завжди обчислюється за модулями, тому він додатний. Формули загального розв’язку працюють без змін і з від’ємними a, b чи c; змінюються лише знаки кроків b/g і a/g у параметричних формулах.

Q: Як найпростіше зрозуміти, що розв’язків немає?

Перевірте подільність на НСД: розв’язки існують тоді й лише тоді, коли gcd(a,b) ділить c. Швидка перевірка на парність виявляє чимало типових випадків — якщо a і b обидва парні, ліва частина завжди парна, тож непарне c робить рівняння нерозв’язним. Аналогічно вираз 6x + 10y завжди парний і до того ж кратний лише gcd(6,10)=2.

Q: Як знайти лише невід’ємні або додатні розв’язки?

Параметрична множина x = x_0 + (b/g)t, y = y_0 - (a/g)t дає лінійні умови на t. Розв’яжіть нерівності x ≥ 0 і y ≥ 0 відносно t, візьміть їх перетин (це скінченний діапазон цілих чисел) і перелічіть усі значення. Якщо отриманий діапазон t порожній, розв’язку з обома невід’ємними змінними не існує.

Q: Чому калькулятор дає інший окремий розв’язок, ніж у підручнику?

Окремий розв’язок ніколи не єдиний — якщо підходить пара (x_0, y_0), то підходить і (x_0 + b/g, y_0 - a/g). Обидві відповіді правильні, бо через параметр t вони породжують цілком ту саму множину розв’язків. Цей калькулятор зсуває x_0 у компактний діапазон 0 ≤ x_0 < |b/g|, чого підручники можуть не робити. Завжди перевіряйте відповідь підстановкою в ax + by.

Q: Що буде, якщо a або b дорівнює нулю?

Рівняння перетворюється на рівняння з однією змінною. Якщо b = 0, потрібно, щоб a mid c; тоді x = c/a фіксований, а y може бути будь-яким цілим числом, і симетрично для a = 0. Якщо обидва коефіцієнти нульові, рівняння або виконується завжди (c = 0, підходить будь-яка пара), або ніколи. Калькулятор опрацьовує всі ці вироджені випадки безпосередньо.

Q: Чим це відрізняється від розв’язування звичайного лінійного рівняння?

У дійсних числах рівняння ax + by = c з ненульовим коефіцієнтом завжди має розв’язки — ними є ціла пряма. Діофантова версія вимагає лише цілих пар, через що рівняння може бути нерозв’язним (коли gcd(a,b) nmid c) або мати дискретну, рівномірно розставлену множину розв’язків на тій прямій замість суцільної. Крок між сусідніми розв’язками дорівнює саме (b/g, -a/g).

Оновлено: 15.10.2026

Розв’язує лінійне діофантове рівняння ax + by = c у цілих числах. Введіть коефіцієнти a, b і c, щоб перевірити, чи існують розв’язки, отримати один окремий розв’язок і повну множину x = x₀ + (b/g)t, y = y₀ − (a/g)t.

Розв’язання ax + by = c у цілих числах

Формула лінійного діофантового рівняння

Формула

\[ ax + by = c, \qquad a, b, c \in \mathbb{Z} \] \[ g = \gcd(a, b) \] \[ \text{Цілочислові розв’язки існують} \iff g \mid c \] \[ x = x_0 + \frac{b}{g}\,t, \qquad y = y_0 - \frac{a}{g}\,t, \qquad t \in \mathbb{Z} \]

Де:

\(a\), \(b\) — цілі коефіцієнти при \(x\) та \(y\)
\(c\) — ціла права частина рівняння
\(g = \gcd(a, b)\) — найбільший спільний дільник коефіцієнтів
\((x_0, y_0)\) — один окремий розв’язок, який знаходять зі співвідношення Безу \(g = s\,a + t\,b\) множенням на \(c/g\)
\(t\) — довільний цілий параметр, що породжує всі розв’язки

Рівняння має цілі розв’язки тоді й лише тоді, коли \(\gcd(a,b)\) ділить \(c\). Якщо це так, розв’язків нескінченно багато: відштовхуючись від одного розв’язку \((x_0, y_0)\), кожен інший можна одержати, додавши \(b/g\) до \(x\) та віднявши \(a/g\) від \(y\) однакову кількість разів \(t\).

Лінійне діофантове рівняння — приклад обчислення

Приклад: розв’яжемо \(12x + 18y = 30\) у цілих числах (стандартні значення калькулятора).

\[ \gcd(12, 18): \quad 18 = 1 \cdot 12 + 6, \quad 12 = 2 \cdot 6 + 0 \implies \gcd(12, 18) = 6 \]

\[ 6 \mid 30 \implies \text{розв’язки існують} \]

\[ \text{Безу: } 6 = (-1) \cdot 12 + 1 \cdot 18, \qquad \frac{c}{g} = \frac{30}{6} = 5 \]

\[ x_0 = -1 \cdot 5 = -5, \qquad y_0 = 1 \cdot 5 = 5 \]

\[ 12 \cdot (-5) + 18 \cdot 5 = -60 + 90 = 30 \;\checkmark \]

Зсунувши \(x_0\) у межі \(0 \le x < |b/g| = 3\), отримуємо еквівалентний окремий розв’язок \((1, 1)\), адже \(12 \cdot 1 + 18 \cdot 1 = 30\).

Результат: усі цілі розв’язки — це \(x = 1 + 3t\), \(y = 1 - 2t\) для довільного цілого \(t\); наприклад \((1, 1)\), \((4, -1)\), \((-2, 3)\).

Як користуватися калькулятором

Введіть цілий коефіцієнт при \(x\) у поле Коефіцієнт при x (a).
Введіть цілий коефіцієнт при \(y\) у поле Коефіцієнт при y (b).
Введіть праву частину у поле Права частина (c).
Прочитайте блоки результату: Чи існують цілі розв’язки? показує, чи ділить \(\gcd(a,b)\) число \(c\); Один розв’язок (x₀, y₀) дає перевірений окремий розв’язок; Загальний цілий розв’язок містить повну множину з параметром \(t\); Покрокове розв’язання показує алгоритм Евкліда, коефіцієнти Безу та хід міркувань.

Усі три введені значення мають бути цілими числами (додатними, від’ємними або нульовими). Якщо ввести неціле значення, калькулятор попросить ціле число, адже діофантові рівняння за означенням розв’язуються лише в цілих числах.

Що таке лінійне діофантове рівняння?

Діофантовим називають рівняння, розв’язки якого шукають лише в цілих числах. Лінійне діофантове рівняння \(ax + by = c\) — найпростіший його вид: потрібно знайти всі пари цілих чисел \((x, y)\), що задовольняють його точно, без дробів і десяткових значень. Такі рівняння природно виникають щоразу, коли величини неподільні — монети фіксованих номіналів, ящики з товаром, люди чи плитки.

Ключовим тут є умова розв’язності: вираз \(ax + by\) завжди кратний \(\gcd(a, b)\), тому й \(c\) мусить бути кратним \(\gcd(a, b)\). Наприклад, \(6x + 10y\) завжди парне, тож рівняння \(6x + 10y = 7\) не має цілих розв’язків, як би ви не шукали. Якщо ж умову виконано, співвідношення Безу гарантує щонайменше один розв’язок, який ефективно знаходить розширений алгоритм Евкліда.

Як інтерпретувати результат: коли розв’язки існують, їх нескінченно багато — вони утворюють арифметичну прогресію. Загальний розв’язок \(x = x_0 + (b/g)t\), \(y = y_0 - (a/g)t\) перелічує їх усі: кожен крок параметра \(t\) збільшує \(x\) на \(b/g\) і зменшує \(y\) на \(a/g\), лишаючи вираз \(ax + by\) незмінним. Якщо потрібні розв’язки у певних межах (скажімо, невід’ємні), підставте кілька значень \(t\) і залиште ті, що підходять.

Припущення, обмеження та поради

Лише цілі числа. Коефіцієнти мають бути цілими; рівняння не розв’язується над раціональними чи дійсними числами. У дійсних числах \(ax + by = c\) завжди має розв’язки, коли \(a\) або \(b\) не дорівнює нулю — саме обмеження цілістю й робить задачу цікавою.
Обмеження на розмір чисел. Обчислення виконуються стандартною арифметикою, тому тримайте коефіцієнти в безпечному діапазоні цілих чисел (приблизно до 15 цифр), щоб уникнути проблем із точністю.
Вироджені випадки опрацьовано. Якщо \(a = b = 0\), рівняння або виконується завжди (\(c = 0\), підходить будь-яка пара), або не виконується ніколи. Якщо рівно один коефіцієнт нульовий, рівняння містить лише одну змінну, і калькулятор розв’язує його безпосередньо.
Годиться будь-який окремий розв’язок. Пара \((x_0, y_0)\) не єдина — калькулятор зсуває її до компактного вигляду з \(0 \le x_0 < |b/g|\), але будь-який вибір через параметр \(t\) породжує ту саму повну множину розв’язків.
Перевірка відповіді. Завжди перевіряйте підстановкою: обчисліть \(a x_0 + b y_0\) і переконайтеся, що результат дорівнює \(c\). Калькулятор виконує цю перевірку за вас і показує її у результаті.

Якщо у вашій задачі одразу два лінійні рівняння, систему виду \(ax + by = c\), \(dx + ey = f\) розв’язують методом виключення змінних, а не через подільність на НСД. Діофантова логіка також лежить в основі таких тем, як пряма пропорційність, де дві цілочислові величини зростають у фіксованій пропорції, і є класичним інструментом олімпіадних задач та теорії чисел.

Часті запитання

Як розв’язати лінійне діофантове рівняння вручну?

Спершу обчисліть \(g = \gcd(a, b)\) алгоритмом Евкліда. Якщо \(g\) не ділить \(c\), цілих розв’язків немає. Інакше застосуйте розширений алгоритм Евкліда, щоб знайти коефіцієнти Безу з \(g = sa + tb\), помножте їх на \(c/g\) і отримайте \(x_0 = s \cdot c/g\) та \(y_0 = t \cdot c/g\), а тоді запишіть усі розв’язки у вигляді \(x = x_0 + (b/g)t\), \(y = y_0 - (a/g)t\).

Чи можна використовувати від’ємні коефіцієнти або від’ємну праву частину?

Так, усі три значення можуть бути від’ємними або нульовими — відкидаються лише дроби та десяткові числа. НСД завжди обчислюється за модулями, тому він додатний. Формули загального розв’язку працюють без змін і з від’ємними \(a\), \(b\) чи \(c\); змінюються лише знаки кроків \(b/g\) і \(a/g\) у параметричних формулах.

Як найпростіше зрозуміти, що розв’язків немає?

Перевірте подільність на НСД: розв’язки існують тоді й лише тоді, коли \(\gcd(a,b)\) ділить \(c\). Швидка перевірка на парність виявляє чимало типових випадків — якщо \(a\) і \(b\) обидва парні, ліва частина завжди парна, тож непарне \(c\) робить рівняння нерозв’язним. Аналогічно вираз \(6x + 10y\) завжди парний і до того ж кратний лише \(\gcd(6,10)=2\).

Як знайти лише невід’ємні або додатні розв’язки?

Параметрична множина \(x = x_0 + (b/g)t\), \(y = y_0 - (a/g)t\) дає лінійні умови на \(t\). Розв’яжіть нерівності \(x \ge 0\) і \(y \ge 0\) відносно \(t\), візьміть їх перетин (це скінченний діапазон цілих чисел) і перелічіть усі значення. Якщо отриманий діапазон \(t\) порожній, розв’язку з обома невід’ємними змінними не існує.

Чому калькулятор дає інший окремий розв’язок, ніж у підручнику?

Окремий розв’язок ніколи не єдиний — якщо підходить пара \((x_0, y_0)\), то підходить і \((x_0 + b/g,\; y_0 - a/g)\). Обидві відповіді правильні, бо через параметр \(t\) вони породжують цілком ту саму множину розв’язків. Цей калькулятор зсуває \(x_0\) у компактний діапазон \(0 \le x_0 < |b/g|\), чого підручники можуть не робити. Завжди перевіряйте відповідь підстановкою в \(ax + by\).

Що буде, якщо a або b дорівнює нулю?

Рівняння перетворюється на рівняння з однією змінною. Якщо \(b = 0\), потрібно, щоб \(a \mid c\); тоді \(x = c/a\) фіксований, а \(y\) може бути будь-яким цілим числом, і симетрично для \(a = 0\). Якщо обидва коефіцієнти нульові, рівняння або виконується завжди (\(c = 0\), підходить будь-яка пара), або ніколи. Калькулятор опрацьовує всі ці вироджені випадки безпосередньо.

Чим це відрізняється від розв’язування звичайного лінійного рівняння?

У дійсних числах рівняння \(ax + by = c\) з ненульовим коефіцієнтом завжди має розв’язки — ними є ціла пряма. Діофантова версія вимагає лише цілих пар, через що рівняння може бути нерозв’язним (коли \(\gcd(a,b) \nmid c\)) або мати дискретну, рівномірно розставлену множину розв’язків на тій прямій замість суцільної. Крок між сусідніми розв’язками дорівнює саме \((b/g, -a/g)\).