V.Приклади застосування алгоритму евкліда до розв’язуваня діофантових рівнянь.

Український математик Г.Ф.Вороний (1868-1908) зробив великий внесок у розвиток математичної науки, розв’язання діофантових рівнянь. В його щоденнику читаємо «… сів розв’язувати задачу, над якою б’юсь вже майже два місяці (x²+y²+z²=2mxyz). Треба розв’язати це рівняння в цілих і додатних числах. Я, власне, втратив надію коли-небудь розв’язати цю задачу»(запис від 7 серпня 1885 року). Дуже відвертий і повчальний запис. Кілька скупих фраз, але вони рельєфно показують, з якою наполегливістю працюють творчі математики над розв’язанням нових проблем, яким напруженням волі і розуму здобувається кожний науковий результат.

До розв’язування в цілих числах лінійних діофантових рівнянь з двома невідомими можна застосувати алгоритм Евкліда. Нехай дано рівняння виду ax+by=c (*)

де a,b,c – цілі числа . Нехай d=НСД (a,b). Якщо с не ділиться на d, то не існує цілих х, у , які задовольняють дане рівняння. В іншому разі ліва частина рівняння ділитиметься на d, а права – ні.

Нехай тепер с ділиться на d. Поділивши обидві частини на d, дістанемо рівняння

a₁x+b₁y=c₁

рівносильне даному, де НСД (a₁,b₁)=1.

Таким чином, можна вважати, що в рівнянні ax+by=c числа a i b взаємно прості. Цю умову задовольняють рівняння виду

x+by=c(**) Усі розв’язки в цілих числах рівняння (*) можна записати відразу. Справді, у набуває довільних значень, а x=c-by . Таким чином, пари виду (c – bk;k), де k – довільне число, являють собою всі цілі розв’язки рівняня (**).

Аналогічний результат дістанемо для рівняння ax+y=c . Так усі розв’язки рівняння 5х+у=3 вичерпуються парами (k;3 – 5k), де k – довільне ціле число.

Зведемо рівняння (*) до виду рівняння (**), подавши його у матричній формі: (х,у) = c. (***)

За умовою, числа a та b – взаємно прості. Для них остання відмінна від нуля остача r_m в алгоритмі Евкліда дорівнює 1.

Приклад №14

Знайти цілі числа розв’язки рівняння 42х+25у=7

Розв’язання. Застосуємо до чисел а=42, b=25 алгоритм Евкліда:

42=25●1 +17

25=17●1+8

17=8●2+1

Тут n=3, q₁=1, q₂=1, q₃=2, r₂=8, r₃=1.

Зауважимо, що завчасно нам не потрібно встановлювати взаємну простоту чисел а і b. Остання відміна від 0 остача r₃=1 дорівнює НСД (a, b). Співвідношення r_i-1=r_iq_i+1+r_i+1 рівносильне матричній рівності

Тоді матриця А для нашого прикладу подається так:

(x, y) = (k, 7 – 8k) = (21 – 25k, –35 + 42k), k€Z

ВИСНОВОК

Численні задачі з математики, фізики, хімії та інших галузей науки й практики зводяться до розв’язування рівнянь. Саме ця обставина спонукала математиків насамперед займатися розробкою методів розв’язування різних типів рівнянь. У своїй учнівській науково-дослідницькій роботі досліджував розв’язання діофантових рівнянь, зокрема рівняння виду ax+by=c (a, b, c – цілі числа). Ще одним прикладом діофантового рівняння є рівняння x²+y²=z², розв’язки (x, y, z) якого є цілочисельними довжинами відповідно катетів та гіпотенузи у прямокутних трикутників. Розглянуто і використано при розв’язуванні діофантових рівнянь метод остач і метод повного перебору.

ЛІТЕРАТУРА

1. Вишенський В.А. та ін. «Київські математичні олімпіади (1984 – 1993 рр.) Збірник задач.» - К.: Либідь 1993.

2. Горделадзе Ш.Г. та ін. «Збірник конкурсних задач з математики.» - К.: Вища школа 1993.

3. Федак І.В. «Обласні математичні олімпіади. Збірник задач.» - К.: Т.. 2004

4. «Збірник задач з математики для вступників до вузів: навчальний посібник» за/ред.. М.І. Сканаві. - К.: Вища школа 1996

19