СПОСОБИ РОЗВ’ЯЗУВАННЯ ЛІНІЙНИХ РІВНЯНЬ В ЦІЛИХ ЧИСЛАХ

Лінійні діофантові рівняння

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

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

«Арифметика» Діофанта – це збірник задач (їх всього 189), кожна з яких має розв'язок і необхідні пояснення. В збірник входять різноманітні задачі, і їх розв’язки дуже часто не так просто зрозуміти. Діофант практикувався у знаходженні розв’язків невизначених рівнянь або систем таких рівнянь. Його цікавили тільки додатні цілі числа і раціональні розв’язки. Ірраціональні розв’язки він називав «неможливими» і ретельно підбирав коефіцієнти так, щоб отримати шукані додатні, раціональні розв’язки.

Тому, зазвичай, довільне невизначене рівняння (але, як правило, з цілими коефіцієнтами)називають «діофантовим», якщо хочуть наголосити на тому, що рівняння слід розв’язувати в цілих числах.

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

В 1624 році була опублікована книга французького математика Баше де Мезирьяка , у якій для розв'язку рівняння 𝑎𝑥+𝑏𝑦=𝑐 фактично застосовується процес, що зводиться до послідовного визначення неповних часткових підхідних дробів.

Після Баше в XVII і XVIII століттях різні алгоритми для розв'язку невизначеного рівняння першого степеня з двома невідомими давали Роль, Ейлер та інші математики.

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

У серпні 1900 року в Парижі відбувся ІІ міжнародний конгрес математиків. 8 серпня Д. Гільберт прочитав на цьому конгресі доповідь «Математичні проблеми». Серед 23 проблем, розв'язок яких, як вважав Гільберт, було необхідно отримати в наступному XX столітті , десяту проблему він сформулював наступним чином:

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

Гіпотезу, що такого способу не існує, першим сформулював (з вагомими на те доказами) американський математик М. Девіс у 1949 році. Доведення цієї гіпотези затягнулося на 20 років – останній крок був зроблений в 1970 році Юрієм Володимировичем Мятіясеєвичем, на першому році аспірантури він показав алгоритмічну нерозв’язність 10 –ї  проблеми Гільберта.

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

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

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

На полі дійсних чисел R рівняння з трьома невідомими x, y, z, що має вигляд  

ax + by + cz = d                   (1),

має безліч розв’язків (x, y, z)   і множина усіх цих розв’язків задає деяку площину у тривимірному просторі. Методом підбору, а це дає змогу моделювати за певними умовами необхідні нам властивості невідомих трійок, легко записувати дійсні розв’язки рівняння (1). А якщо вам важко усно підбирати числа для розв’язку, то задавайте, двом будь-яким невідомим довільні числа і знаходьте третє невідоме із самого рівняння. Проте ми постараємося  знаходити по тільки цілі трійки чисел(x, y, z).  

Поставимо таку задачу: знайти тільки цілі розв’язки рівняння (1), якщо відома трійка із цілих чисел, { а , b,  с }єZ.

При умові, що

d:НСД(а , b,  с) – ціле число,

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

a) трійка чисел, яка задана через один цілий параметр k:

х = m₁k + n₁,

           y = m₂k + n₂,        (2)

z = m₃k + n₃,

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

(m₁ , m₂, m₃), (n₁ , n₂, n₃).

Для цього задана форма розв’язків (2) підставляється у дане рівняння (1) і тотожно перетворюється ліва і права частини до лінійного виду відносно параметру k:

a(m₁k + n₁) + b(m₂k + n₂) + c(m₃k + n₃)= d.

am₁k + аn₁ + bm₂k + bn₂ + cm₃k + сn₃= d.

am₁k + bm₂k + cm₃k + аn₁ + bn₂ + сn₃ = d.

(am₁ + bm₂ + cm₃)k + (аn₁ + bn₂ + сn₃ ) = 0* k  + d.

 Так як ліва і права частина це дві неперервні лінійні функції, то можна прирівняти коефіцієнти при k  і прирівняти вільні члени. Отримаємо:

am₁ + bm₂ + cm₃ = 0           (3)

аn₁ + bn₂ + сn₃= d            (4)

 Завжди можна підібрати таку трійку цілих чисел (m₁ , m₂, m₃), при заданій трійці (а , b,  с), що складається тільки із цілих чисел, { а , b,  с }, що виконується рівність (3).  Таких трійок існує безліч.

Завжди можна підібрати таку трійку цілих чисел (n₁ , n₂, n₃), при заданій трійці (а , b,  с), що складається тільки із цілих чисел, { а , b,  с } і цілому значенні d, що виконується рівність (4). Таких трійок існує безліч.

Застосуємо цей метод на конкретному прикладі.

Приклад. Знайти  розв’язок діофантового рівняння

2x  - 3y + 7z = 1.

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

Розв’язок діофантового рівняння  

2x  - 3y + 7z = 1

існує, адже d:НСД(а , b,  с) – ціле число, тобто, 1:НСД(2,3, 7) =1

Розв’язок знайдемо у вигляді трійки чисел, яка задана через один цілий параметр k, а саме:

х = m₁k + n₁,

y = m₂k + n₂,

z = m₃k + n₃.

Згідно вище викладеного методу невизначених коефіцієнтів одразу використаємо виведені нами формули:

am₁ + bm₂ + cm₃ = 0,          

аn₁ + bn₂ + сn₃= d.            

Для даного  рівняння отримаємо рівності:

2m₁  - 3m₂ + 7m₃ = 0,           

2n₁ - 3n₂ + 7n₃= 1.            

Методом підбору(а це дає змогу моделювати за певними умовами необхідні нам властивості невідомих трійок, а якщо вам важко підбирати числа для розв’язку, то задавайте, двом будь-яким невідомим довільні цілі числа і знаходьте третє невідоме із самого рівняння)  знаходимо по одній цілій трійки чисел:

(m₁ , m₂ , m₃) = (2, 6, 2)        

(n₁ , n₂ , n₃) = (1, -2, -1)        

Таким чином, маємо трійку-розв’язок (x, y, z) з одним цілим параметром k.

х = 2k + 1,

y = 6k -2,

z = 2k - 1.

Перевірка.

2(2k + 1) – 3(6k -2)+ 7(2k - 1) = 1,   

4k + 2 – 18k + 6 + 14k - 7 = 1,

0*k +1 = 1,   

1=1.        

Відповідь: (2k + 1,   6k -2,   2k – 1 ),  де k - довільне ціле число.

Пропонуємо розглянути більш простіший метод спуску.

Приклад. Знайти  розв’язок діофантового рівняння

8х +33у + 16z =1416 .

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

Потрібно перевірити існування розв’язку діофантового рівняння

8х + 33у + 16z =1416.

1416:НСД(8,33, 16) =1416:1=1416.

Отже розв’язок існує.

Використаємо метод спуску. Виділяємо цілу частину у лівій частині рівняння. Для цього поділимо все рівняння на 8. Отримаємо

х + 4у + у/8 + 2z =177.

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

у/8 = - х - 4у - 2z + 177.

Ліва і права частини останнього рівняння це цілі числа, тому

y = 8n,  де n - довільне ціле число.

Виокремимо у лівій частині змінну х, враховуючи, що y = 8n:

х = - 4у - у/8 - 2z +177,

х = - 4*8n - n - 2z +177 = -33n  - 2z + 177.

Покладемо  z = n і отримаємо трійку цілих чисел (х  у  z), яка є цілочисельним розв’язком даного рівняння

х = -33n  - 2n + 177 = - 35n + 177

y = 8n,

z = n,

де n - довільне ціле число.

Або

(х  у  z) = (- 35n + 177;   8n;   n),

де n - довільне ціле число.

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

якщо n =0, то трійка чисел (х  у  z) = ( 177;   0;   0) є розв’язком;  

якщо n = -1, то трійка чисел (х  у  z) = ( 212;   -8;   -1) є розв’язком;  

якщо n = 1, то трійка чисел (х  у  z) = ( 142;    8;    1) є розв’язком.  

Відповідь: (- 35n + 177;   8n;   n),  де n - довільне ціле число.

Звичайно, виникає запитання, чи можна розв’язок лінійного діофантового рівняння записати через два цілих параметри наприклад, трійка чисел, яка задана через два цілі параметри k i l:

х = p₁ + q₁*k + g₁*l = 1*p₁ + q₁*k + g₁*l,

y = p₂+ q₂*k + g₂*l = 1*p₂+ q₂*k + g₂*l,

z = p₃ + q₃*k + g₃*l = 1*p₃ + q₃*k + g₃*l.

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

І все-таки покажемо алгоритм, як шукати цілі трійки чисел (х  у  z)  через два цілі параметри k i l. Користуючись методом невизначених коефіцієнтів для пошуку цілих значень невідомих трійок

(р₁ , р₂, р₃), (q₁ , q₂, q₃), (g₁ , g₂, g₃),

отримаємо  рівності:

aр₁ + bр₂ + cр₃ = d           (5)

aq₁ + bq₂ + cq₃ = 0           (6)

аg₁ + bg₂ + сg₃= 0            (7)

Завжди можна підібрати таку трійку цілих чисел (р₁ , р₂, р₃), при заданій трійці (а , b,  с), що складається тільки із цілих чисел, { а , b,  с }, що виконується рівність (5).  Таких трійок існує безліч.

Завжди можна підібрати таку трійку цілих чисел (q₁ , q₂, q₃), при заданій трійці (а , b,  с), що складається тільки із цілих чисел, { а , b,  с } і цілому значенні d, що виконується рівність (6). Таких трійок існує безліч.

Завжди можна підібрати таку трійку цілих чисел (g₁ , g₂, g₃), при заданій трійці (а , b,  с), що складається тільки із цілих чисел, { а , b,  с } і цілому значенні d, що виконується рівність (7). Таких трійок існує безліч.

Звертаємо увагу, що однопараметричний розв’язок  завжди є окремим випадком двопараметричного  розв’язку, тобто 

х = m₁k + n₁ = 1*n₁ + m₁*k + g₁*0,

y = m₂k + n₂= 1*n₂+ m₂*k + g₂*0,

z = m₃k + n₃= 1*n₃ + m₃*k + g₃*0.

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