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

Виконав студент IV курсу фізико-математичного факультету Бєлов Денис Володимирович

Вятський державний гуманітарний університет

Визначимо цілі, що стоять перед цією роботою. Для цього дамо два визначення.

Визначення 1. Діофантовим рівнянням 1-го ступеня (лінійним) з невідомими називається рівняння виду

де всі коефіцієнти та невідомі - цілі числа і хоча б одне.

Для скорочення запису умовимося далі скорочувати фразу лінійне діофантове рівняння, як ЛДУ.

Визначення 2. Рішенням ЛДУ називається впорядкована n-ка цілих чисел, така, що.

Нашою метою буде навчитися знаходити рішення невизначеного рівняння першого ступеня, якщо це рішення є.

Для цього необхідно відповісти на такі питання:

1). Чи завжди ЛДУ має рішення знайти умови існування рішення.

2). Чи є алгоритм, що дозволяє знайти рішення ЛДУ.

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

У частині 1.1 наведено витяги з історії невизначених рівнянь. У частині 1.2. у вигляді теореми наводиться необхідна та достатня умова існування рішення ЛДУ, також йдеться про кількість рішень. Далі розглядаються методи знаходження рішень, у пункті 1.3 для деяких окремих випадків, у пункті 1.4 для будь-якого ЛДУ, що має рішення.

Діофант (Dióphantos) представляє одну із цікавих загадок в історії математики. Ми не знаємо, ким був Діофант, точні роки його життя, нам не відомі його попередники, які б працювали в тій же області, що й він. [10]

На могилі Діофанта є вірш-загадка, вирішуючи яку неважко підрахувати, що Діофант прожив 84 роки. Прочасу життя Діофанта ми можемо судити з праць французького дослідника науки Поля Таннрі, і це, ймовірно, середина III ст.н.е. [10]

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

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

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

Перше загальне рішення рівняння першого ступеня , де цілі числа, зустрічається у індійського мудреця Брахмагупти (бл. 625 г). Тому, строго кажучи, немає підстав називати лінійні невизначені рівняння діофантові. Проте, історично все ж таки склалося застосовувати термін «діофантово», до будь-якого рівняння, яке вирішується в цілих числах.

У 1624 р. публікується книга французького математика Баше де Мезір'яка "Problẻmes plaisans et delectables que se font par les nombres". Баше де Мезір'як для вирішення рівняння фактичнозастосовує процес, що зводиться до послідовного обчислення неповних приватних та розгляду відповідних дробів.

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

Ланжежем, який, однак, зауважує, що фактично це той самий спосіб, який був дано Баше де Мезір'яком та іншими математиками, що розглядали невизначені рівняння до нього. Невизначені рівняння 1-го ступеня стали записуватись і вирішуватися у формі порівняння значно пізніше, починаючи з Гауса. [2]

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

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

Однак, якщо про довільне діофантове рівняння не можна сказати, чи має воно ціле коріння, чи ні, то проблема існування цілого коріння ЛДУ вирішена. Наведемо теореми, користуючись якими завжди можна сказати, чи має цілі рішення дане ЛДУ чи ні.

Теорема 1. При взаємно простих коефіцієнтах діофантове рівняння

має рішення у цілих числах.

Доведення. Позначимо через безліч тих позитивних чисел, для яких рівняння

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

У множині існує найменше число ( - підмножина натуральних чисел), яке ми позначимо через - цілі числа, такі, що

Нехай, де; тоді

Ми підібрали цілі значення: , ,…, , такі, що , але , а - найменше позитивне число, тобто не може бути позитивним, , , .

Ми, що – спільний дільник чисел , отже, оскільки , , , , то рівняння можна розв'язати у цілих числах.

Теорема 2. Нехай - найбільший загальний дільник коефіцієнтів. Діофантове рівняння має рішення тоді і лише тоді, коли . Число рішень такого рівняння дорівнює або нулю, або нескінченності.

Доведемо послідовно всі три твердження теореми.

1). Нехай. Для рівняння

де , Існують цілі числа: що задовольняють йому. Тобто. такі, що

т. е. - рішення рівняння.

2). Нехай тепер не ділить. Тоді ліва частина рівняння за будь-яких цілих ділиться на , а права на не ділитися, так що рівність при цілих значеннях неможлива.

3). Якщо - впорядкована n-ка чисел, що задовольняє рівняння, то, наприклад, всі n-ки

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

Якщо хоч одна пара коефіцієнтів взаємно проста, то , і рівняння має безліч рішень.

Розглянемо лінійне рівняння з одного невідомої, тобто. рівняння виду

Зрозуміло, що рішенням цього рівняння буде , і рішення буде цілим числом тільки в тому випадку, коли .

Розглянемо тепер лінійне рівняння із двома невідомими

Покажемо кілька алгоритмів знаходження рішення.

Розглянемо два випадки:

а). не ділиться на . В цьому випадку рішень немає за теоремою 2.

б). ділиться на , поділимо на .

Таким чином отримали нове ЛДУ, з тим самим безліччю рішень, але вже із взаємно-простими коефіцієнтами. Тому далі ми розглядатимемо саме такі рівняння.

, перейдемо до порівняння,

Т.к. то порівняння має єдине рішення.

; підставимо на рівняння.

Тоді загальне рішення можна визначити за формулами: , де .

Знайдемо рішення порівняння;

Отримали загальне рішення: , де .

Розглянемо ще один спосіб знаходження рішення ЛДУ з двома невідомими, а для цього розглянемо рівняння виду. Рівняння такого виду називаються однорідними лінійними діофантовими рівняннями (ЛОДУ). Висловлюючи невідому, через невідому приходимо до. Так як x повинен бути цілим числом, то де - довільне ціле число. Значить. Рішеннями ЛОДУ є n-ки виду, де . Безліч всіх таких n-ок називається загальним рішенням ЛОДУ, будь-яка конкретна пара з цієї множини називається приватним рішенням.

Розглянемо тепер рівняння . Нехай n-ка його приватне рішення, а безліч n-ок загальне рішення відповідного ЛОДУ. Доведемо пропозицію.

Загальне рішення ЛДУ, задається рівняннями, де.

Доведення. Те, що праві частини зазначених у формулюванні теореми рівностей справді є рішеннями, перевіряється їх безпосередньою підстановкою у вихідне рівняння. Покажемо, що будь-яке рішення рівняння має саме такий вигляд, який зазначено у формулюванні речення. Нехай - якесь рішення рівняння. Тоді, але ж і. Віднімемо з першої рівності другу і отримаємо:

- Однорідне рівняння. Пишемо відразу загальне рішення: , звідки отримуємо:

Постає питання про знаходженняприватного рішення ЛДУ.

За теоремою про лінійне розкладання НОД, це означає, що знайдуться такі і з безлічі цілих чисел, що , причому ці ми легко вміємо знаходити за допомогою алгоритму Евкліда. Помножимо тепер рівність і отримаємо: , тобто. , .

Таким чином, для знаходження загального рішення знаходимо загальне рішення ЛДУ, приватне рішення ЛДУ та їх складаємо.

Примітка: особливо цей спосіб зручний, коли або . Якщо, наприклад, , тоді n-ка, очевидно, буде приватним рішенням ЛДУ. Можна одразу виписувати загальне рішення.

Знайдемо приватне рішення. Використовуємо алгоритм Евкліда.

Отримуємо лінійне розкладання НОД:

Отримали загальне рішення: , де .

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

Позначимо та отримаємо , тобто ці рішення рівносильні.

Ще один спосіб спирається на теорему:

Нехай - довільне рішення діофантового рівняння

безліч рішень рівняння у цілих числах збігаються з безліччю пар , де , , де t – будь-яке ціле число.

Доказ цього нескладного факту можна знайти, наприклад, у книзі Бухштабу [2, стор 114].

Знову ж таки приватне рішення можна легко відшукати за допомогою алгоритму Евкліда.

Перейдемо тепер до рішення ЛДУ з невідомих, тобто рівнянь виду

де всі коефіцієнти та невідомі - цілі числа і хоча б одне. Для існування рішення з теореми 2 необхідно, щоб

перейдемо до рівносильного рівняння

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

Перепишемо це рівняння у вигляді

Очевидно, що рішення рівняння (*) та (**) пов'язані між собою взаємнооднозначною відповідністю і, таким чином, розв'язавши рівняння (**), нескладно знайти всі рішення рівняння (*). З іншого боку зазначимо, що

Зазначимо також, що

Отже, за кінцеве число кроків рівняння (*) приведеться до вигляду

де числа (i = 1. n), які не дорівнюють нулю, дорівнюють між собою за абсолютною величиною. Зі співвідношення слід, що числа можуть набувати лише значення 0,±1, причому не всі з них дорівнюють нулю. Припустимо, для певності, . Тоді рівняння (***) має таке рішення:

де t2, t3, . tn – довільні цілі числа. Звідси, враховуючи проведені заміни, виходить рішення рівняння (*). Зазначимо, що при отриманні рішення рівняння (***) використовувався лише факт, що тому, при виконанні алгоритму можна зупинитися на тому кроці, коли хоча б один з коефіцієнтів дорівнюватиме ±1.

1). Вирішити в цілих числах рівняння

4x - 6y + 11z = 7, (4,6,11) = 1.

Розділивши із залишком -6 на 4, отримаємо -6 = 4(-2) + 2. Подаємо вихідне рівняння у вигляді

4(x – 2y) + 2y + 11z = 7.

Після заміни x = x - 2y це рівняння запишеться так

Враховуючи, що 11 = 2 · 5 + 1, перетворимо останнє рівняння:

4x + 2(y + 5z) + z = 7.

Поклавши y = y + 5z, отримаємо

Це рівняння має таке рішення: x, y - довільні цілі числа, z = 7 - 4x - 2y.

Отже y = y - 5z = 20x + 11y - 35, x = x + 2y = 41x + 22y - 70.

Таким чином, рішення вихідного рівняння має вигляд

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

2). Вирішити в цілих числах рівняння

Розділимо 5 на -4 з «залишком», , Перетворимо вихідне рівняння до виду