ЛІНІЙНІ ДІОФАНТОВІ РІВНЯННЯ

Діофантовими (на честь Діофанта Александрійського, старогрецького ученого ІІІ ст.) називаються рівняння і системи з цілими коефіцієнтами, що мають число невідомих, що перевершує число рівнянь. Система стає невизначеною, і в неї знаходять цілі (рідше раціональні) розв'язки.

Невизначені рівняння 1-го степеня почали розглядатися ще індуськими математиками приблизно з V століття. Деякі такі рівняння з двома і трьома невідомими з'явилися в зв'язку з проблемами, що виникли в астрономії, наприклад, при розгляді питань, зв'язаних з визначенням періодичного повторення небесних явищ.

У другому виданні книги французького математика Баше де Мезір’яка “Problemis plaisans et delectables que se font par les nombres”, що вийшли в 1624 р., зважується невизначене рівняння ax+by=c. Баше де Мезір’як фактично застосовує процес, що зводить до послідовного обчислення не повних часток і розгляду придатних дробів; однак він не розглядав неперервних дробів як таких. Популярний твір Баше де Мезір’яка дуже вплинув на розвиток теорії чисел, так як сприяв виникненню інтересу до цієї області математики.

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

Невизначені рівняння 1-го степеня стали записуватися й розв'язуватися у формі порівняння значно пізніше, починаючи з німецького математика Гаусса. Він вперше систематизував теорію та визначив поняття конгруенції, в своїй книзі “Disquisitionesarithmeticae” (“Дослідження з арифметики”).

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

ах + bу = с,

де а, b, с це цілі числа, а, b- взаємно прості числа.

Oчевидно, це рівняння має нескінченно багато розв'язків.

Розв'язок прийнято позначати парою чисел: (x, y).

Нескінченну множину розв'язків можуть мати також діафантові рівняння другого і третього степеня.

Діофантові рівняння більш високих степенів, як правило, можуть мати лише скінчене число розв'язків.

Означення.

Рівняння виду

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

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

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

Покажемо це на прикладах.

Приклад 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), тому це рівняння має розв’язків в цілих числах.

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

ах + bу = с

треба:

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

НСД(a/m; b/m ) = НСД(p;s)= 1, де a/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) Отже, маємо дві рівності:

3x + 5y = 7, 3x₀ + 5y₀ = 7,

Віднімемо одне рівняння з іншого, позначимо
x- x₀ і у -y₀ через p і g, і отримаємо
3a + 5b = 0.

Звідси ми бачимо, що b ділиться на 3, а а – на 5.

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

x - 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 - будь-яке ціле число.

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

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

1) 21x + 48y = 6;

2) 2x + 8y = 5;

3) 17x + 47y = 67.

Деякі рівняння в цілих числах

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

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

ах + bу = с

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

2) Якщо а, b, с – натуральні числа, а та b – взаємно прості, то рівняння

ах – bу = с

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

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

х² - у² = 13, де

1•13=(-13)•(-1)=(х – у)(х + у)

рівносильно сукупності 4-ьох систем в цілих числах.

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

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

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

Наприклад, у рівнянні
n³-n = 3m²+1 для довільних цілих чисел ліва частина рівняння, тобто вираз

n(n - 1)(n + 1), ділиться на 3, а права частина під час ділення на 3 дає в остачі 1.

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

Наприклад, у рівнянні

х²+ х -1 = 32у+1

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

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

Наприклад, у рівнянні

4^m = 3k + 2

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

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

Повна теорія рівнянь другого степеня була створена спільними зусиллями багатьох математиків і підсумована до початку ХІХ століття видатним німецьким математиком К.Гауссом. Важливих успіхів у дослідженні діофантових рівнянь вищих степенів було досягнуто лише на початку ХХ століття.

Про складність діофантових рівнянь можна судити з такої події.

На ІІ Міжнародному Конгресі математиків, що відбувся у Парижі в серпні 1990 р., німецький математик Д.Гільберт зробив доповідь «Математичні проблеми», де сформулював, на його думку, найбільш цікаві проблеми, дослідження яких стимулювало б подальший розвиток математики.

Серед них за номером 10 була така: «Нехай є довільне діофантове рівняння з довільним числом невідомих і з цілими раціональними коефіцієнтами; потрібно вказати загальний метод, використовуючи який можна за скінченну кількість кроків встановити, має дане рівняння розв’язки в раціональних числах чи ні». На розв’язання цієї проблеми пішло понад піввіку, над нею працювало багато видатних математиків.

І тільки в 1972 році російський математик Ю.Матіясевич довів, що десята проблема Гільберта нерозв’язна.

Зрозуміло, що вивчення діофантових рівнянь у загальноосвітніх школах не передбачене навчальними програмами. Але і діофантові рівняння, і задачі, що зводяться до діофантових рівнянь, часто пропонуються учасникам різних математичних змагань: олімпіад, турнірів, фестивалів; членам Малої академії наук – на контрольних роботах, абітурієнтам – на вступних випробуваннях. Успішне розв’язання таких завдань не потребує додаткових знань, а вимагає від учнів твердих знань шкільної математики, логічного мислення, вміння застосовувати свої знання у нестандартних ситуаціях. Водночас корисно також знати деякі способи розв’язань.

Найчастіше розв’язки діофантових рівнянь вдається знайти, використовуючи такі прийоми.

1. Розв’язати рівняння відносно однієї змінної, а іншу вибрати так, щоб ця змінна була цілою.

2. Розкласти ліву частину рівняння на множники за умови, що права частина рівняння є цілим числом, і замінити рівняння сукупністю систем простіших рівнянь.

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

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

Задачі для самостійного осмислення.

1. Знайти найменше натуральне число, яке під час ділення на 9 і 14 дає відповідно остачі 7 і 5.

Відповідь. Найменше шукане натуральне число m = 61.

2. П'ятикласник розставляє іграшкових солдатів по 10 в шеренгу. В останній шерензі не вистачило трьох солдатів. Він почав ставити в шеренгу по 12 солдатів - 7 залишилося. Потім він склав їх в коробки по 100 штук - третя коробка виявилася неповною. Скільки всього солдатів в школяра?

3. Чи можна між 30 дітьми розділити порівну 29 цукерок, не розрізаючи їх більш ніж на 6 частин?

4. Кілька років тому були в ходу монети по 3 і 5 коп. Скількома способами можна набрати ними суму в 10 рублів(100 коп = 1 гривня)?

5. Якщо кожен хлопчик купить пиріжок, а кожна дівчинка – булочку, то вони витратять разом на одну копійку менше, ніж якби кожен хлопчик купив булочку, а кожна дівчинка – пиріжок. Відомо, що хлопчиків більше, ніж дівчаток. На скільки?

6. 175 Шалтаїв стоять дорожче, ніж 125, але дешевше, ніж 126 Болтаїв. Доведіть, що на трьох Шалтаїв і одного Болтаєвого рубля не вистачить.

7. У класі кожен хлопчик дружить з трьома дівчатками, а кожна дівчинка – з двома хлопчиками. При цьому в класі всього 19 парт і 31 піонер. Скільки в класі учнів?

8. Дві команди розіграли першість школи в десяти видах, причому за перемогу команда отримувала 4 очки, за нічию – 2 і за програш – 1 очко. Разом обидві команди набрали 46 очок. Скільки було нічиїх?

9. Четверо товаришів купили разом човен. Перший вніс половину суми, внесеної останніми; другий – третина суми, внесеної останніми; третій – чверть суми, внесеної останніми, а четвертий вніс 130 рублів. Скільки коштує човен і скільки вніс кожен?

10. На дорозі, що сполучає два аули, немає горизонтальних ділянок. Автобус йде в гору завжди із швидкістю 15 км/ч, а під гору – 30 км/ч. Знайдіть відстань між аулами, якщо відомо, що шлях туди і назад автобус проїжджає за 4 години.

11. Чи існують такі натуральні
а і b, що ab(а -b) = 45045?