Пункт 5. Лінійні діофантові рівняння з двома невідомими.

Звичайно, довільне рівняння (але, як правило, усе-таки з цілими коефіцієнтами) одержує титул "діофантове", якщо хочуть підкреслити, що його потрібно вирішити в цілих числах, тобто знайти всього його розв’язки, що є цілими. Ім'я Діофанта - видатного Олександрійського математика - з'являється тут не випадково. Діофант цікавився розв’язком рівнянь у цілих числах ще в третьому столітті н.е..

Відступ про Діофанта і його історичний слід.

Третій і останній період античного суспільства - період панування Рима. Рим завоював Сіракузи в 212 році, Карфаген - у 146 році, Грецію - у 146, Месопотамію - у 46, Єгипет - у 30 році до нашої ери. Величезні території виявилися колоніями, але римляни не чіпали їхньої культури й економічного устрою доки ті платили податки і побори. Установлений римлянами на сторіччя мир приніс усій завойованій території самий довгий період безвійськового існування, торгівлі і культурного обміну.

Олександрія виявилася центром античної математики. Велися оригінальні дослідження, хоча компілювання, переказ і коментування стали основним видом наукової діяльності. Олександрійські вчені приводили науку в порядок, збираючи розрізнені результати в єдине ціле, і багато праць античних математиків і астрономів дійшли до нас тільки завдяки їхній діяльності. Грецька наука з її незграбним геометричним способом вираження при систематичному відмовленні від алгебраїчних позначень згасала, алгебру й обчислення (прикладну математику) олександрійці взяли зі сходу, з Вавилону та Єгипту.

Основна праця Діофанта ( 250 р.) - "Арифметика". Вціліли лише шість книг оригіналу, загальне їхнє число - предмет здогадів. Ми не знаємо, ким був Діофант, - можливо, що він був эллінізований вавілонянин. Його книга - один з найбільш захоплюючих трактатів, що збереглися від греко-римської стародавності. У ній уперше зустрічається систематичне використання алгебраїчних символів, є особливі знаки для позначення невідомої, мінуса, зворотної величини, зведення в ступінь. Папірус №620 Мічіганського університету, куплений у 1921 році, належить епосу Діофанта і наочно це підтверджує. Серед рівнянь, розв'язаних Діофантом, — x² - 26 y² = 1 і x² - 30 y² = 1, тепер відомі нам як окремі випадки "рівняння Пелля", причому Діофант цікавиться їхніми розв’язками саме в цілих числах.

Книга Діофанта вплинула на розвиток математичної науки останніх трьох сторіч. Справа в тому, що юрист із Тулузи П’єр Ферма (1601 - 1665), вивчаючи "Арифметику" Діофанта, зробив на полях цієї книги знамениту позначку: "Я знайшов воістину дивний доказ того, що рівняння xⁿ + yⁿ = zⁿ при n > 2, не має розв’язків у цілих числах, але поля цієї книги занадто малі, щоб тут це умістити". Це одне із самих марних математичних тверджень одержало назву "Великої теореми Ферма" і, чомусь, викликало дійсний ажіотаж серед математиків і аматорів (особливо після призначення в 1908 році за його доказ премії в 100000 німецьких марок). Спроби добити цю марну теорему породили цілі розділи сучасної алгебри, алгебраїчної теорії чисел, теорії функцій комплексної змінної й алгебраїчної геометрії, практична користь від який уже не підлягає сумніву. Сама теорема доведена в 1995 році; П’єр Ферма, звичайно, погарячкував на полях "Арифметики", тому що він фізично не міг придумати подібного доказу, що вимагає колосальної сукупності математичних знань. Елементарного доказу великої теореми Ферма поки ніхто з жителів нашої планети знайти не зміг, хоча над пошуком билися кращі розуми останніх трьох століть. Однак, дотепер тисячі психічно нездорових аматорів-"ферматистів" у спразі слави і грошей бомблять своїми листами академічні інститути й університети.

Нехай потрібно розв’язати лінійне діофантове рівняння:

ax + by = c ,

де a , b , c Î Z ; a і b - не нулі.

Спробуємо помислити, дивлячись на це рівняння.

Нехай ( a , b ) = d . Тоді a = a ₁ d ; b = b ₁ d і рівняння виглядає так:

a ₁ d· x + b ₁ d· y = c , тобто d· ( a ₁ x + b ₁ y ) = c .

Тепер зрозуміло, що в такого рівняння є розв’язок (пари цілих чисел x і y ) тільки тоді, коли d | c . Оскільки дуже хочеться розв’язувати це рівняння далі, то нехай d | c . Поділимо обидві частини рівняння на d, і далі будемо вважати, що ( a , b ) = 1.

Розглянемо кілька випадків.

Випадок 1. Нехай c = 0, рівняння має вид ax + by = 0 - " однорідне лінійне діофантове рівняння". Знаходимо, що

x = ­ b / a * y

Оскільки x  має бути цілим числом, то y = at , де t - довільне ціле число (параметр). Значить x = - bt і розв’язками однорідного діофантового рівняння ax + by = 0 є усі пари виду {- bt , at }, де t = 0; ±1; ±2;... Множина усіх таких пар називається загальним розв’язком лінійного однорідного діофантового рівняння, будь-яка ж конкретна пара з цієї множини називається частковим розв’язком.

Випадок 2. Нехай тепер c ¹ 0. Цей випадок закривається наступною теоремою.

Теорема. Нехай ( a , b ) = 1, { x ₀ , y ₀ } - частковий розв’язок діофантового рівняння ax + by = c . Тоді його загальний розв’язок задається формулами:

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

Доказ. Те, що праві частини зазначених у формулюванні теореми рівностей дійсно є розв’язками, перевіряється їх безпосередньою підстановкою у вихідне рівняння. Покажемо, що будь-який розв’язок рівняння ax + by = c має саме такий вид, який зазначений у формулюванні теореми. Нехай { x * , y *} - який-небудь розв’язок рівняння ax + by = c . Тоді ax * + by * = c , але і ax ₀ + by ₀ = c . Віднімемо від першої рівності другу й одержимо:

a ( x *- x ₀ ) + b ( y *- y ₀ ) = 0

- однорідне рівняння. Далі, дивлячись на випадок 1, пишемо відразу загальний розв’язок: x *- x ₀ = - bt , y *- y ₀ = at , звідки одержуємо:

Як же шукати саме частковий розв’язок { x ₀ , y ₀ }. Ми домовилися, що ( a , b ) = 1. Це означає, що знайдуться такі u і v з Z , що au + bv = 1 (пункт 4), причому ці u і v знаходимо за допомогою алгоритму Евкліда. Помножимо тепер рівність au + bv = 1 на c і одержимо: a ( uc ) + b ( vc ) = c , тобто x ₀ = uc , y ₀ = vc .

Приклад. Ви - хроноп, придуманий Хуліо Кортасаром у книжці "З життя хронопів і фамів". Вам потрібно розплатитися в магазині за синю пожежну кишку, тому що червона в господарстві вже давно є. У вас у кишені монети 7 і 12 копійок, а вам треба заплатити 43 копійки. Як це зробити? Вирішуємо рівняння:

7 x + 12 y = 43

Включаємо алгоритм Евкліда:

12 = 7· 1 + 5

7 = 5· 1 + 2

5 = 2· 2 + 1

2 = 1· 2

Виходить, найбільший спільний дільник чисел 7 і 12 дорівнює 1 , а його лінійний вираз такий:

1 = 5 - 2· 2 = 5 - (7 - 5) · 2 = (12 - 7) - (7 - (12 - 7) · 2) = 12· 3 + 7· (- 5),

а саме u = - 5, v = 3. Частковий розв’язок:

x ₀ = uc = (- 5) · 43 = - 215

y ₀ = vc = 3 · 43 = 129.

Отже, ви повинні відібрати в касира 215 монет по 7 копійок і дати йому 129 монет по 12 копійок. Однак процедуру можна спростити, якщо записати загальний розв’язок неоднорідного діофантового рівняння:

x = -215 - 12 t

y = 129 + 7 t

і бачимо, що при t = - 18, виходить x = 1, y = 3.