ЛІНІЙНІ ДІОФАНТОВІ РІВНЯННЯ З ДВОМА НЕВІДОМИМИ.

ЛІНІЙНІ ДІОФАНТОВІ РІВНЯННЯ З ДВОМА НЕВІДОМИМИ.

Означення. Рівняння  виду  

ах +bу = с

називається лінійне діофантове рівняння з двома невідомими, якщо  а, b, с  – цілі числа, а  ≠ 0, b ≠ 0 , с ≠  0.

Приклад 1:

Приклади лінійних діофантових  рівнянь з двома невідомими:

1)  2х +3у = -5, коефіцієнти рівняння а =2, b =3, с = -5.

2) - х - 3у = 10, коефіцієнти рівняння  а =-1, b = -3, с =10.  

3) 32х +17у = 3, коефіцієнти рівняння а =32, b =17, с =3.  

4)  2,3х +3,3у=5,5 - це недіофантове рівняння(бо коефіцієнти а та b  являються нецілими числами), проте це лінійне рівняння відносно двох невідомих х та  у і   його можна звести до діофантового, якщо помножити усі числа на 10.

Зауваження. До виду лінійних діофантових рівнянь з двома невідомими можна звести рівняння виду  pх +qу = g, якщо  p, q, g – звичайні дроби, p  ≠ 0, q ≠ 0 , g ≠  0.

Для цього  досить: записати всі коефіцієнти звичаними дробами і помножити ліву та праву частину рівняння на спільний знаменник, тобто помножити на найменше спільне кратне коефіцієнтів, НСК(p, q, g). Покажемо це на прикладах.

Приклад 2:

Приклад 2:

1)  ^x/₂+^y/₃=³/₅, коефіцієнти рівняння а =0,5; b = ¹/₃;  с = ¹/₅; якщо це рівняння помножити на  спільний знаменник 30, і скоротити коефіцієнти, тоді отримаємо лінійне діофантове рівняння з двома невідомими:  15х +10у = 18.

Твердження 1. Лінійне діофантове рівняння з двома невідомими

ах + bу = с

можна  розв’язати в цілих числах тоді і тільки тоді, коли число  с ділиться націло на НСД(а, b), тобто с : НСД(а, b).

Припустимо, що для лінійного діофантового рівняння з двома невідомими ах + bу = с

виконується умова:  ^a/_c=n, ^b/_c=m     Якщо поділити обидві частини рівняння на число с, тоді отримаємо рівняння виду:  nх + mу = 1.  Отже маємо більш краще твердження:

Твердження 2. Лінійне діофантове рівняння з двома невідомими

ах + bу = с

можна  розв’язати в цілих числах тоді і тільки тоді, коли НСД(а, b) =1, НСД(а, b,с) =1, тобто, цілі числа  а та  b – взаємно прості, ( не мають спільного дільника, крім 1).

Приклад 3:

Приклади лінійних діофантових  рівнянь з двома невідомими:

1)  2х +3у = -5, коефіцієнти рівняння а =2, b =3, с = -5, НСД(а, b) = НСД(2, 3)= 1, тому це рівняння має розв’язки в цілих числах.

2) - 6х - 3у = 10, коефіцієнти рівняння  а =-6, b = -3, с =10,

НСД(а, b) = НСД(-6, -3) = 3, тому це рівняння не має розв’язків  в цілих числах.

 3) 34х +17у = 51, коефіцієнти рівняння а =34, b =17, с =51, поділимо  обидві частини даного рівняння на 17, отримаємо рівняння 2х +1у = 3. НСД(2, 1) = 1,  при цьому 3: НСД(2, 1), тому це рівняння має розв’язків  в цілих числах.

Для розв’язування лінійного діофантового рівняння з двома невідомими

ах + bу = с

треба:

1) Перевірити умову розв’язності даного рівняння в цілих числах. Для цього  спочатку ділять обидві частини рівняння на число m = НСД(а, b,с) , а потім перевіряють умову: НСД(а:m, b:m) = НСД(p;s)= 1, де  а:m = p; b:m = s; якщо ця умова не виконується, тоді роблять висновок дане рівняння не має розв’язку в цілих числах.

2) Якщо рівняння має розв’язок в цілих числах, тоді треба відшукати хоча б одну пару (х_о, у_о) цілих чисел, яка є розв’язком даного рівняння;(це можна зробити:  методом підбору, методом Евкліда, графічним способом та іншими способами.)

3) записують всю множину розв’язків лінійного діофантового рівняння з двома невідомими, як множину цілочисельних пар у вигляді

(х_о - рk, у_о+ sk),  де k – довільне ціле число.

Приклад 4:

Розв’язати рівняння 3x + 5y = 7 в цілих числах.

Розв’язання:

1) Перевіримо умову розв’язності: коефіцієнти рівняння а =3, b =5, с =7, НСД(3, 5) = 1, отже  маємо ціле число, якщо 7: НСД(3, 5), тому дане рівняння має множину розв’язків в цілих числах.

2) Знайдемо спочатку який-небудь конкретний розв’язок: Тут використаємо  таку ідею, до речі, часто допомагає і при розв’язанні інших завдань.

Спочатку знайдемо одну пару цілих чисел (m; n), яка є  рівняння розв’язком іншого, легшого рівняння: 3x + 5y = 1, тоді матимемо правильну  рівність: 3m + 5n = 1,  а для того, щоб знайти один розв’язок (х_о, у_о)  для рівняння 3x + 5y = 7, треба буде помножити  правильну рівність  3m + 5n = 1 на 7. Продемонструємо цю ідею на практиці.  Оскільки легко встановити, що  3m + 5n = 3∙2 + 5∙(-1) = 1, то  3x + 5y = 3∙(2∙7) + 5∙(-7∙1) = 1∙7  і, отже, x₀ = 14, y₀ = 7 – це розв’язок даного рівняння (одне з багатьох, не більш!).

3) Отже, маємо дві рівності:

3х + 5у = 7, 

3х_о + 5у_о = 7.

Віднімемо одне рівняння з іншого, позначимо x- x₀ і у -y₀ через p і g, і отримаємо 3a + 5b = 0. Звідси ми бачимо, що b ділиться на 3, а  а – на 5. Покладемо p = 5k, тоді g = 3k – тут очевидно,  що  k - може бути будь-яким цілим числом. Отже, ми отримуємо набір розв’язків:

x - х_о = 5k;   х = 14 + 5k, де  k – ціле число.

y - y_о = -3k; у = - 7 -3,  де  k – ціле число. 

 Інших розв’язків, звичайно, немає.

Відповідь: (14 +5k; -7 -3k), де k – довільне ціле число.

Приклад 5:

Розв’язати рівняння  3x -12y = 7 в цілих числах.

Розв’язання:

1)Це рівняння не має цілих розв’язків. Ліва частина ділиться на 3,  бо НСД(3;12) = 3, тоді як права частина не ділиться на 3.  Звертаємо вашу увагу, що не виконується умова розв’язності: 7 не ділиться на ціло на 3.

Відповідь:  розв’язку в цілих числах рівняння не має.

Приклад 6:

Розв’язати рівняння  1990x - 173y = 11.

Розв’язання:

1)Числа, що беруть участь у рівнянні, такі великі, що підбором тут конкретного розв’язку не знайти. Проте нам допоможе те, що числа 1990 і 173 взаємно прості (перевірте це). Це означає, що дане рівняння має розв’язки в цілих числах.

2)Отже,  НСД(1990;173) = 1, а це значить, що одиницю  можна подати  у вигляді суми 1990m -173n = 1, де m і n – деякі цілі числа.

Продемонструємо використання алгоритму Евкліда. Більше число 1990 поділимо на 173 стовпчиком, отримаємо неповну частку 11 і остачу 87. Згідно цього маємо рівність

1990 = 173 ∙11 + 87 ( або 87 = 1990 -173∙11).                      (3)

Тепер число 173 поділимо на 87 стовпчиком, отримаємо неповну частку 1, а остачу 86. Згідно цього маємо рівність

173 = 87∙1 + 86 ( або 86 = 173 - 87∙1).                      (2)

Далі, число 87 поділимо на 86 стовпчиком, отримаємо неповну частку 1 а остачу 1. Згідно цього маємо рівність

87 = 86∙1 +1 ( або 1 = 87 - 86∙1).                       (1)

Враховуючи рівності (1), (2), (3), які записані в дужках число 1 можна записати отак:

1= 87 – 86 = 87 – (173 - 87∙1) = 87∙2 - 173∙1 = (1990 - 173∙11)∙2 - 173∙1 = 1990∙2 - 173∙22 - 173∙1 = 1990∙2 - 173∙23 = 1.

Отже, якщо не вдається легко підібрати конкретний розв’язок, як в даному випадку, то, використовуючи алгоритм Евкліда, можна завжди  отримати  потрібну пару: m = 2, n = 23. Отже, за допомогою такої могутньої зброї, як алгоритм Евкліда, ми отримуємо конкретне вирішення допоміжного рівняння 1990m - 173n = 1:  пару (2, 23).

3) Якщо помножити числа на 11, то отримаємо  x₀ = 22, y₀ = 253 – це конкретний розв’язок рівняння 1990x - 173y = 11. Далі отримуємо, згідно формул множину цілих розв’язків:

x = х_о + 173k = 22 + 173k, де  k – ціле число.

y = y_о + 1990k = 253 + 1990k,  де  k – ціле число. 

Відповідь:  (22+173k; 253+1990k), де k – будь-яке ціле число.

1. Завдання  для самостійного опрацювання:

Знайдіть всі цілі розв’язки рівняння: 

1) 21x + 48y = 6;

2) 2x + 8y = 5;

3) 17x + 47y = 67.