Поняття діофантового рівняння

Задача.

Знайдемо, наприклад, цілий  розв’язок рівняння 2x + 5y = 17.

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

За  алгоритмом Евкліда 2 і 5, отримуємо  2 ∙ 3 – 5 = 1.

Тобто, пара сх₀ = 3 ∙ 17, су₀ = (- 1) ∙ 17 задовольняє рівняння 2х + 5у=17. Тому загальний розв’язок початкового рівняння такий:

x = 51 + 5t,  у = - 17 – 2t, де t приймає будь-які цілі значення. Очевидно, невід’ємні розв’язки відповідають тим t, для яких виконується нерівність:

Звідси  знайдемо   – 51/5 £ t £ - 17/2.

Ці  нерівності задовольняють числа -10, -9. Відповідні частинні розв’язки записуються у вигляді пар: (1,3), (6, 1).

 

3.Ланцюгові дроби.

Наступний метод пов'язаний з безперервними або ланцюговими дробами.  Звернімося знову до алгоритму Евкліда. З першої рівності системи (1) випливає, що дріб можна записати у вигляді суми цілої частини і правильного дробу: = q₀ + . Але = 1/b/r₁, і на підставі другої рівності тієї ж системи маємо . Значить, =q₀+1/(q₁+ ). Далі отримаємо =q₀ + 1/(q₁+1/(q₂+r₃/r₂)). Продовжуємо до тих пір, доки не прийдемо до знаменника q_n.  У результаті ми представимо звичайну дріб у наступному вигляді:    = q₀ + 1 / (q₁ + 1 / (... + 1 / q_n)). Ейлер назвав дроби такого виду неперервними. Приблизно в той же час у Німеччині з'явився інший термін - ланцюгова дріб. Так за цими дробами і збереглися обидві назви. Через громіздкість розгорнутої записи ланцюгового дробу застосовують компактний запис   [q₀; q₁, q₂, …,q_n].

Задача.

Представимо дріб у вигляді ланцюгового.

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

= 1 + = 1 +   = 1 + = 1 + 1 / (3 + 1 / 9 / 4) =

=1 + 1 / (3 + 1 / (2 +1 / 4)) = [1; 3, 2, 4]

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

 

 

4.Метод розкладу на множники.

Задача.

Розв’яжіть рівняння в цілих числах: x² - y² = 91.

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

Розкладемо ліву частину даного рівняння на множники: (х–у)(х+у)= 91.

Так як  91= 1 ∙ 91 =91 ∙ 1=(-1) ∙ (-91) = (-91) ∙ (- 1) = 7 ∙ 13 =

= 13 ∙ 7 = (-7) ∙ (-13) = (-13) ∙ (-7), то розв'язок даного рівняння зводиться до розв’язання восьми систем:

1.           

(46; 45)

(-46; -45)

3) 

        (46; -45)

4) 

 (-46; 45)

5) 

(10; 3)

6) 

 (-10; -3)

7) 

 (10; -3)

8) 

 (-10; 3)

Відповідь.

(46; 45),(46; - 45),(-46; -45),(-46; 45),(10; 3),(10; -3),(-10; -3),(-10; 3).

 

5. Розв'язання рівнянь в цілих числах як квадратних відносно якої-небудь змінної.

Задача.

Розв’яжіть рівняння в цілих числах: 5х²+ 5у² + 8ху + 2у – 2у + 2 = 0.

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

Якщо спробувати розв'язати дане рівняння методом розкладання на множники, то це досить трудомістка робота, тому це рівняння можна розв'язати більш раціональним способом. Розглянемо рівняння, як квадратне відносно х: 5х²+(8у-2)х+5у²+2у+2=0, х₁,

2 = (1 – 4у ± - 5(5у² + 2у + 2))/5 = (1 – 4у ± )/5.

Дане рівняння має розв'язок лише тоді, коли дискримінант дорівнює нулю, тобто  –9(у + 1) = 0, звідси у = -1. Якщо у = -1, то х =1.

Відповідь. (1; -1)

 

6. Метод остач.

Задача.

Розв’яжіть рівняння в цілих числах 3ª = 1 + у²

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

Видно, що (0; 0) – розв'язок даного рівняння. Доведемо, що інших розв’язків немає.

Роздивимось випадки:

1. х Î N, y Î N                                    (5)

Якщо х Î N , то 3ª ділиться на 3 без остачі, а у² + 1 при діленні на 3 дає остачу або 1, або 2. Звідси, рівність (5) при натуральних значеннях х и у неможлива.

2. Якщо х – ціле від'ємне число, y Î Z, тоді 0<3ª<1, а   1+у²³ 0 і рівність (5) также неможлива. Звідси, (0; 0) – єдиний розв’язок.

Відповідь.  (0; 0).

 

7. Метод невизначеного або нескінченного спуску.

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

 

Задача.

Розв’яжіть рівняння в цілих числах 29х + 13у + 56z = 17 (6)

Виразимо невідоме, коефіцієнт при якому найменший, через інші невідомі у=(17-29х-56z)/13=(1-2x-4z)+(4-3x-4z)/13                     (7)

Позначимо   (4-3x-4z)/13 = t₁      (8)

Із (7) випливає, що t₁ може приймати тільки цілі.

Із (8) маємо   13t₁ + 3x + 4z = 14   (9)

Отримаємо нове діофантове рівняння, але з меншими, ніж у (6) коефіцієнтами.  Застосуємо до (9) ті ж міркування: x=(4-13t₁-4z)/3= =(1-4t₁-z) + (1-t₁-z)/3;      (1-t₁-z)/3 = t₂ , t₂ – ціле, 3t₂+t₁+z = 1  (10)

В (10) коефіцієнт при z – невідомому початковому рівнянні 1 – це кінцевий пункт «спуску». Тепер послідовно виражаємо z, x, y через t₁ і t₂.

Отже,

t₁, t₂ - будь-які цілі числа – усі цілі розв’язки рівняння  (6)

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

3.1. ЛДУ c однієї невідомої.

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

3.2. ЛДУ  з двома невідомими.  Розглянемо тепер лінійне рівняння з двома невідомими  , . Покажемо кілька алгоритмів для знаходження розв’язку.

 

Спосіб 1.

Нехай   . 
Розглянемо два випадки:   
а). не ділиться на . У цьому випадку рішень немає за теоремою 2.   
б). ділиться на , Поділимо на .   
; .   
Таким чином отримали нове ЛДУ, з тією ж множиною рішень, але вже з взаємно-простими коефіцієнтами.  Тому далі ми будемо розглядати саме такі рівняння.   
Розглянемо , .   , перейдемо до порівняння,   
.  
Оскільки , то порівняння має єдиний розв’язок .  
; Підставимо в рівняння.   ; ;  
,причому .  Позначимо .   
Тоді загальний розв’язок можна знайти за формулами: , де . 

Приклад.  , .   
Знайдемо розв’язок порівняння ; ; ,  Тобто .     ;   
Отримали спільний розв’язок: , де .

Спосіб 2.

Розглянемо  ще один спосіб знаходження розв’язків ЛДУ з двома невідомими, а для цього розглянемо рівняння виду . Рівняння такого виду називаються лінійними однорідними діофантовими рівняннями (ЛОДР). Висловлюючи невідому , Через невідому приходимо до . Так як x повинен бути цілим числом, то , де - довільне ціле число. Значить . Розв’язком ЛОДР є n-ки виду , де . Множина всіх таких _n-ок називається загальним розв’язоком ЛОДР, будь-яка ж конкретна пара з цієї множини називається частинним розвязком.   
         Розглянемо тепер рівняння , . Нехай n-ка його частинний розв'язок, а безліч n-ок спільним розв’язком відповідного ЛОДР. Доведем твердження.   
Загальний розв’язок ЛДУ , задається рівняннями , де .   
Доведення. Те, що праві частини зазначених у формулюванні теореми рівностей дійсно є розв’язками, перевіряння їх безпосередньої підстановкою в початкове рівняння. Покажемо, що будь-який розв’язок рівняння має саме такий вигляд, який зазначений у формулюванні твердження. Нехай - Який-небудь розв’язок . Тоді , але ж і . Віднімемо з першої рівності друге і отримаємо:  
- Однорідне рівняння. Пишемо відразу спільний розв’язок: , Звідки отримуємо:   
.Доведення завершено.   
Постає питання про знаходження частинного розв’язку ЛДУ.  
. За теоремою про лінійне розкладання НСД, це означає, що знайдуться такі і з множини цілих чисел, що , Причому ці і ми легко вміємо знаходити за допомогою алгоритму Евкліда. Помножимо тепер рівність на і отримаємо: , Тобто , .  
Таким чином, для знаходження спільного розв’язку знаходимо спільний розв’язок ЛОДР, частинний розв’язок ЛДУ і їх додаємо.  
Зауваження: особливо цей спосіб зручний, коли або . Якщо, наприклад, , , тоді n-ка , очевидно, буде частинним розв’язком ЛДУ. Можна відразу виписувати спільний розв’язок.  
Приклад. , .  
Знайдемо частинний розв’язок. Використовуємо алгоритм Евкліда.   
;   
Отримуємо лінійне розкладання НСД:   
, тобто .   ,  

Отримали спільний розв’язок: , де .

Як бачимо, отриманий розв’язок, не збігається з розв’язком , знайденим першим способом.   
Позначимо і отримаємо , тобто ці розв'язки рівносильні.

Спосіб 3.  Ще один спосіб спирається на теорему:   
Нехай - Довільний розв’язок діофантових рівнянь  
, , тоді безліч рішень рівняння в цілих числах збігається з множиною пар , де , , де t - будь-яке ціле число.  
Доведення цього нескладного факту можна знайти, наприклад, у книзі Бухштаб [ст. 114].   
Знову ж частинний розв’язок можна легко відшукати за допомогою алгоритму Евкліда. 

3.3. Знаходження рішень довільного ЛДУ.

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

З іншого боку зазначимо, що    
Відзначимо також, що    
Отже, за кінцеве число кроків рівняння (*) приведеться до виду  (***) , де числа (I = 1 ,..., n), які не дорівнюють нулю, рівні між собою за абсолютною величиною. Зі співвідношення випливає, що числа можуть приймати тільки значення 0, ± 1, причому не всі з них рівні нулю. Припустимо, для визначеності, . Тоді рівняння (***) має наступне розв’язання:   
 
де t _2, t _3, ..., t _n - довільні цілі числа. Звідси, враховуючи проведені заміни, виходить і розв’язок рівняння (*). Відзначимо, що при отриманні розв’язку рівняння (***) використовувався лише факт, що , Тому, при виконанні алгоритму можна зупинитися на тому кроці, коли хоча б один з коефіцієнтів стане рівним ± 1.

4. Невизначені рівняння вищих порядків. Рівняння . Піфагорові трійки

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

Можна взяти 𝑥, 𝑦, 𝑧 такими, що вони не мають спільного дільника, більшого за одиницю, інакше можна було б одразу скоротити обидві частини рівняння  на квадрат цього множника. Із таких міркувань випливає, що 𝑥, 𝑦, 𝑧 є попарно взаємно простими, бо якщо, наприклад 𝑥, 𝑦 ділились на , то і 𝑧 ділилось би на 𝑑. Таким чином, одне з чисел 𝑥, 𝑦 повинно бути непарним. Легко бачити, що інше має бути парним. Інакше в протилежному випадку, якщо б , то ділилось на 2, але не ділилось би на 4 і тому не було б квадратом. 

(Якщо . Таким чином квадрат не може ділитися на 2 і не ділитися на 4 одночасно).

Нехай 𝑥 – парне, 𝑦 – непарне, тоді 𝑧  непарне. Візьмемо   отримаємо .

𝑡 і 𝑢 – взаємно прості. Дійсно, якщо 𝑡 і 𝑢 мали спільний множник , то 𝑑 містився б в , а це неможливо, бо 𝑦 та 𝑧 є взаємно простими.

Тому 𝑡 та 𝑢 повинні бути порізну точними квадратами. Доведемо це. Для цього скористаємось теоремою про розклад чисел на прості множники. Маємо

Таким чином, в  силу наслідків із теореми про  розклад отримуємо

Але так як 𝑡 та 𝑢 взаємно прості, то для кожного 𝑖 одне із чисел  дорівнює нулю і тому інше дорівнюватиме . Отже, всі показники в розкладах чисел 𝑡 та 𝑢 парні, звідки випливає, що кожне із цих чисел є точним квадратом:     Звідси  (5) 

Таким чином  кожен розв'язок рівняння  у взаємно простих цілих числах повинен представлятись у вигляді (5), де  - взаємно прості цілі числа, із яких одне парне, а інше не парне (інакше 𝑦 і z були б парними одночасно). І навпаки, якими не були б взаємно прості цілі числа

 різної парності, числа 𝑥, 𝑦, 𝑧 – складені з них по формулам (5) і дають розв’язки рівняння  у взаємно простих числах. Дійсно, перш за все

Крім того, якщо б 𝑦 та ділились на просте число 𝑑, то також  
 ділись би на 𝑑, і так, як 𝑑 не може дорівнювати 2 (бо в силу різної парності чисел , 𝑦 і 𝑧 непарні), внаслідок того, що добуток двох чисел ділиться на просте число, то одне із чисел обов’язково ділиться на цей простий дільник, випливає ,що  повинні ділитися на 𝑑, а це суперечить тому, що числа є взаємно простими. Отже, 𝑦 та 𝑧, а також і вся трійка 𝑥, 𝑦,𝑧 – взаємно прості. Таким чином формули (5) при взаємно простих  різної парності, дають всі розв’язки рівняння  у взаємно простих цілих числах. 

Доведення теореми  Ферма для четвертих степенів. Доведемо наступну теорему:

Теорема 5.

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

Доведення.  Припустимо, що існує система відмінних від нуля розв’язків останнього рівняння. Тоді серед цих систем розв’язків повинна існувати така, для якої 𝑧 приймає найменше можливе значення. Покажемо, що 𝑥 та 𝑦 при цьому взаємно прості. Дійсно, якби 𝑥 і 𝑦 мали спільний дільник 𝑑, то 𝑧 ділилось би на 𝑑 і цілі числа  давали б систему розв’язків з меншим 𝑧.

Як і в  попередньому дослідженні рівняння , впевнюємось в тому, що із пари чисел 𝑥, 𝑦 одне повинне бути парним, а друге непарним.