Задачі на рівняння в цілих числах з двома невідомими

Правила та рекомендації:

Задачі на розв'язування рівнянь у цілих чис­лах традиційно пропонують на математичних олім­піадах для учнів 6 класів. Ця стаття допоможе учневі ознайомити зі специфічними методами розв'язування таких рівнянь. Рекомен­дації пропонуються у формі коментарів до розв'я­зань опорних задач.

Означення. Рівняння  виду   ах +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) 32/х +17у = 3^0,5 - це недіофантове рівняння(бо коефіцієнти а та b  являються нецілими числами), проте це лінійне рівняння відносно двох невідомих х та  у.

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

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

Під час розв'язування рівнянь у цілих числах часто бувають корисними такі факти.

I.                  1) Якщо а, b, с — цілі числа, а та b — взаємно прості, то рівняння 

ах + bу = с

має розв'язки в цілих числах.

Розв'язки рівняння ах + bу = с в цілих числах записують у вигляді:

х = х_о+ bn;

у = у_о - аn,

де n=0, ±1, ±2, ... та (х_о; у_о) – довільний розв’язок даного рівняння, який, як правило, шукають або усно або за допомогою алгоритма Евкліда.

Завдання:

1. Записати і перевірити розв'язки рівнянь в цілих числах:

а)  2х+3у=5;  має розв'язки (х; у)=(1+3n;1-2n);  

б) 2х-5у=4;   має розв'язки (х; у)=(-2+5n; -1+2n);       

в) 7х+2у=13;  має розв'язки (х; у)=(1+2n; 2-7n);

г)16х-5у=1.   має розв'язки (х; у)=(1-5n; 3+16n).

2. Розв'язати в цілих числах невизначені рівняння:

1)   12х+5у=17;    2)5х+7у=11;  3) 21х+19у=73    і     4) 15х-7у=19.

3. Розкласти число 200 на суму таких двох цілих додатних чисел,
щоб одне з них ділилось на 11, а друге – на 13.

4. Розкласти число 800 на суму таких двох цілих додатних чисел,
щоб одне з них ділилось на 17, а друге – на 23.

2) Якщо а, b, с — натуральні числа, НСД(a;b) =1, тобто взаємно прості, то рівняння

ах - bу = с

 має роз­в'язки в натуральних числах.

II.      1) Якщо ліва частина рівняння розкладається на множники, які набувають цілих значень для цілих значень змінних, а права частина рівняння — ціле число, то дане рівняння можна замінити рівносиль­ною йому сукупністю систем рівнянь.

Наприклад, рівняння х² - у² = 13 рівносильно  сукупності систем із двох рівнянь. Яких?

2) Розв'язки рівняння можна знайти, якщо ви­разити одну змінну через іншу і дослідити, для яких значень другої змінної перша змінна набуває цілих значень.

III. Рівняння не має розв'язків у цілих числах, якщо для довільних цілих значень змінної в лівій і правій частинах рівняння отримуюються цілі числа, для яких виконується хоча б одна з таких умов:

1) Ліва і права частини під час ділення на деяке ціле число дають різні остачі.

Наприклад, у деякому рівнянні для довільних цілих чисел ліва частина рівняння, тобто вираз х(х -1)(х +1), ділиться на 3, а права частина під час ділення на 3 дає в остачі 1.

2) Остання цифра числа в лівій частині інша, ніж остання цифра числа в правій частині.

Наприк­лад, у деякому рівнянні для довільних натуральних х та у числа, які одер­жуються в лівій частині, закінчуються цифрами 1, 5 і 9, а числа, які одержуються в правій частині, закінчуються цифрами 3 і 7.

3) Одна з частин рівняння є точним квадратом (кубом), але друга частина такою не є.

Наприклад, у деякому рівнянні ліва частина для довільного натурального n: є точним квадратом, тоді як права частина ні для якого нату­рального у не може бути точним квадратом (точний квадрат під час ділення на 3 дає в остачі або 0, або 1).

Зауваження. Можна скористатися такими фактами:

1)Якщо кожний доданок ділиться на деяке число, то й їх сума ділиться на це число.

2) Якщо кожний доданок суми, крім одного, ділиться на дане число, то сума не ділиться на це число.

Приклад 2:

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

2)   -0,25 х – у/6 = 1/12, коефіцієнти рівняння  а =-0,25; b =1/6;  с =1/12; якщо це рівняння помножити на  спільний знаменник 12, і скоротити коефіцієнти, тоді отримаємо лінійне діофантове рівняння з двома невідомими:  -3х - 2у = 1. 

3) 1,34х –4,17у = 7,3 коефіцієнти рівняння  а =1,34  ; b =-4,17;  с = 7,3;  якщо це рівняння помножити на на  спільний знаменник 100,  тоді отримаємо лінійне діофантове  рівняння з двома невідомими:  134х - 417у = 730.  

Твердження 1. Лінійне діофантове рівняння з двома невідомими  ах + bу = с можна  розв’язати в цілих числах тоді і тільки тоді, коли число  с ділиться націло на НСД(а, b), тобто с: НСД(а, b).

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

виконується умовa :  n =  a/c; m =  b/c.      Якщо поділити обидві частини рівняння на число с, тоді отримаємо рівняння виду:  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), тому це рівняння має розв’язків  в цілих числах.

Метод  «спуску» для лінійних діофантових рівнянь

Перебір варіантів при вирішенні рівняння в цілих числах часто опиняється вельми трудомістким. Тому розглянемо ще один старовинний прийом – метод «спуску» (або метод розсіювання). Таким методом вирішення невизначених (діофантових) рівнянь першого степеня з цілими коефіцієнтами займалися ще в Стародавній Індії. Цим способом іноді у наш час розв’язують такі рівняння.

         Приклад. Розв’язати рівняння в цілих числах:    

19х – 8у = 13          (1).

        Розв’язування. Виражаючи  у – невідоме з найменшим по модулю коефіцієнтом через  х  отримаємо:   

                               у = (19х –13):8                (2).

         Тепер потрібно з'ясувати, при яких цілих значеннях х відповідні  значення  у  також є цілими числами. Тобто, виділивши цілу частина, запишемо рівняння (2) таким чином:  

                               у = 2х + (3х –13):8                            (3).

З рівняння (3) виходить, що  у  при цілому значенні  х  матиме ціле значення тільки в тому випадку, якщо вираз (3х –13):8   також матиме ціле значення, замінимо цей вираз на  ціле число z.         Значить

(3х –13):8 = z         (4),

зведемо до розв’язування  рівняння (4) з двома невідомими   х  і  z, тоді його можна записати так:     

3x – 8z = 13          (5).

        Продовжуючи тим же способом, з рівняння (5) отримаємо:

(8z +13):3 = 2z + (2z +13):3         (6).

         Виходить, невідоме  х  приймає ціле значення при цілому  z  тоді, коли (2z +13): 3     прийматиме ціле значення. Нехай цей вираз рівний  цілому числу p, отримаємо:

р = (2z +13):3               (7)

 або   

3р – 2z = 13            (8).

        Далі:                                     

z = (3р –13):2 = р + (р –13):2                           (9).

       Аналогічно (4) і (7)  (р –13):2  повинно бути цілим числом, підставимо замість цього виразу  ціле значення q  отримуємо:    

q = (р –13):2        (10)

перетворимо                                        

 р – 2q = 13              (11).

      З рівняння (11) отримуємо:       

р = 2q + 13              (12).

     Відмітимо, що при будь-яких значеннях 2q   матимемо цілі значення p.

     З рівності (3), (6), (9), (12) за допомогою послідовних підстановок знаходимо наступні вирази для невідомих  х  і   у  рівняння (1):

x = 2z + p = 2(p+q) + p = 3p + 2q =  3(2q + 13) + 2q = 8q + 39

y = 2x + z = 2(8q + 39) + p + q = 16q +78 +(2q +13)+ q =19q + 91.

  Таким чином, формули:    

 x = 8q + 39

y = 19q + 91,

при  q  =  0       … дають можливість знаходити пари чисел, які задовольняють рівняння (1)

     Наведемо приклади таких рішень:

q	-4	-3	-2	-1	0	1	2	3	4
x=8q + 39	7	15	23	31	39	47	55	63	71
y=8q + 91,	15	34	53	72	91	110	129	148	167

Cпосіб знаходження «часткового»  розв’язку діофантового рівняння

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

ах + bу = с

треба помножити все рівняння на спільний знаменник,  а  потім:

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

НСД(a/m;  b/m ) = НСД(p;s) = 1, де  a/m = p; b/m = s;

якщо ця умова не виконується, тоді роблять висновок дане рівняння не має розв’язку в цілих числах.

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

ах + bу = с;

(це можна зробити:  методом підбору,  методом Евкліда, графічним способом та іншими способами.)

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

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

Cпосіб розкладу  одиниці  на суму цілочисельних добутків.

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

1) перевірити  умову  розв’язності  даного  рівняння;

2)  якщо розв’язки існують, тоді  знайти за допомогою алгоритму Евкліда цілочисельний розв’язок  (n; m) для    рівняння:

ах + bу = 1;

3) рівність  ах + bу = 1 помножити на  ціле число  с і отримати:   а(nc) + b(mc) = c,

записати цілочисельну пару   х_о = nc,    у_о  = mc,  що є  розв’язком ах + bу = с.

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

х = nc - ak,

у  = mc + bk;

або

(х_о - ak,  у_о+ bk),

де 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) Отже, маємо дві рівності:

3x + 5y = 7,  

3x₀ + 5y₀ = 7,

Віднімемо одне рівняння з іншого, позначимо

x- x₀ і у -y₀

через p і g, і отримаємо

3a + 5b = 0.

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

х - x₀ = 5k; 

у - y₀ = -3k,

звідси маємо, 

x = 14 + 5k;

y = -7 - 3k,

де  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 = 22+173k;  

y = 253 +1990k,

 k - будь-яке ціле число.

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

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

Ми ознайомилися з класом діофантових рівнянь, які є лінійні, тобто це рівняння, які можна звести до вигляду

ax + bx = c, де a, b, c - цілі числа.

Зрозуміло, що коли с не ділиться на спільний дільник чисел а та b, то таке рівняння не має розв’язків у цілих числах. Якщо ж а та b взаємно прості, то існує нескінченна множина розв’язків:

x = x_o + bn,

y = y_o - an,

де (x_o; y_o) – який-небудь один (частковий) із розв’язків, n Î Z. Справді, якщо (x_o; y_o) – розв’язок, ax+ by= с. Віднімаючи цю рівність від заданого рівняння, дістанемо

а(х - x_o) + b(у – y_o) = 0,

звідки                

х = x+ b(y_o-у):a.

Для того, щоб х було цілим, необхідно, щоб другий з доданків останній рівності був цілим числом. Оскільки а та b – взаємно прості, то (y_o-у) має ділитися на а. Отже,

y_o - у = -аn, n Î Z.

Звідси і знаходимо всі цілочислові розв’язки (х; у) за вказаними вище формулами.

Задача. Розв’язати у цілих числах рівняння  19х + 97у = 1997.

Розв’язання. Виразимо х через у:  х = (1997 - 97y):19.

Надаватимемо змінній у послідовних значень 0, 1 ,… , 18, перебираючи всі можливі остачі від ділення 1997 - 97у  на 19. Оскільки 19 та 97 – взаємно прості, то  1997 - 97у

ділитиметься на 19 лише для одного такого у. Легко пересвідчитись, що таким значенням є y _o = 1. Тоді х _o = 100 . Отже, всі розв’язки данного рівняння у цілих числах задаються рівностями

х = 100 + 97n     та       у=1-19 n,          n Î Z.

Зауважимо, що, виражаючи х через у при розв’язуванні останнього рівняння, ми могли б записати його також у вигляді  х = 105 - 5у +  (2 - 2y):19.

Зрозуміло, що тоді перевіряти подільність чисельника одержуваного дробу на 19 було б значно простіше.

Задача. Газету розрізали на 7 шматків. Потім вибрали деякі шматки газети і їх теж розрізали на 7 шматків. І продовжили так розрізати ще  кілька разів.  Чи можна в результатів таких розрізань отримати 2017 шматків газети?

Розв'язання. Внаслідок розрізання одного шматка газети на сім частин, загальна кількість шматків газети збільшиться на 6. Це є інваріантна величина. Наприклад, внаслідок розрізання цілої газети отримали 1+ 6 шматків.  Отже, якщо ми виконаємо  n розрізань шматків газети, то в результаті отримаємо 1+6∙n шматків газети. Залишилося розв’язати в  цілих числах рівняння 1+6∙n = 2017.  Отже після 336 розрізань отримаємо  2017.

Відповідь. Можна.

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

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

1) 21x + 48y = 6;     2) 2x + 8y = 6;     3) 17x + 51y = 68;  4) 6х - 2у = 1.

2. Запишіть розв’язки рівнянь в цілих числах:

1)  х+ 3у = 5;   2) 2х - 5у = 4;  3) 7х + 2у = 13               4) - 6х - 5у = 1.

3. Розв’язати в цілих числах невизначені рівняння:

1)   12х + 5у = 17;  2) 5х + 7у = 11; 3) 21х + 19у = 73;   4) 15х - 7у = 19.

4. Розкласти число 200 на суму таких двох цілих додатних чисел, щоб одне з них ділилось на 11, а друге – на 13.

5. Розкласти число 800 на суму таких двох цілих додатних чисел, щоб одне з них ділилось на 17, а друге – на 23.

Задача 1. Чи можна виплатити 100 гривень сорока купюрами вартістю 1, 10 і 100 гривень?

Розв'язання. Якщо 100 гривень можна виплатити, задовольнивши умову задачі, то справедливі рівності:

х + 10y + 100z = 1000      і      х + у + z = 40.

З другого рівняння отримаємо х = 40 - у - z і підставимо в перше рівняння:
40 - у - z + 10у + 100z = 1000,           9у + 99z  = 960.

Оскільки НСД (9; 99) = 9, а 960 не ділиться на 9, то рівняння

х + 10у + 100z = = 1000

не має розв'язку серед цілих чисел. Отже, виплатити 1000 гривень, задоволь­нивши умову задачі, не можна.

Задача 2. Довести, що будь-яку суму, виражену цілим числом гривень, більшим за 7, можна заплатити без здачі, маючи лише купюри вартістю 3 і 5 гривень.

Задача 3. Довести, що будь-яку покупку вартістю в ціле число гривень можна заплатити одними тригривенними купюрами, якщо в касира будуть лише п'ятигривенні купюри.

Задача 4. На складі є цвяхи в ящиках по 16, 17 і 40 кг. Чи можна взяти 140 кг цвяхів, не відкриваючи ні одного ящика?

Задача 5. Привезли 420 т вугілля у вагонах по 16, 20 і 25 т. Скільки яких вагонів було використано, якщо відомо, що всього було 27 вагонів?