Федеральне міністерство за освітою

Державна освітня установа вищої професійної освіти
«Вятський державний гуманітарний університет»
Фізико-математичний факультет
Кафедра вищої математики
Курсова робота
Лінійні Діофантові рівняння
Виконав
студент IV курсу фізико-математичного факультету
Бєлов Денис Володимирович
Перевірила
доцент кафедри вищої математики
Руденко О. С.
Кіров, 2006 р.

Зміст

Введення. 3
1. Діофант та історія діофантових рівнянь. 4
2. Про числі рішень ЛДУ. 6
3. Знаходження рішень для деяких окремих випадків ЛДУ. 8
3.1. ЛДУ c однієї невідомої. 8
3.2. ЛДУ з двома невідомими. 8
4. Знаходження рішень довільного ЛДУ. 12
5. Приклади рішень завдань. 13
Бібліографічний список. 15

Введення.
Визначимо цілі, які стоять перед даною роботою. Для цього дамо два визначення.
Визначення 1. Діофантових рівнянням 1-го ступеня (лінійним) з невідомими називається рівняння виду
,
де всі коефіцієнти і невідомі - цілі числа і хоча б одне .
Для скорочення запису домовимося далі скорочувати фразу лінійне діофантових рівнянь, як ЛДУ.
Визначення 2. Рішенням ЛДУ називається упорядкована n-ка цілих чисел , Така, що .
Нашою метою буде навчитися знаходити рішення невизначеного рівняння першого ступеня, якщо це рішення є.
Для цього, необхідно відповісти на наступні питання:
1). Чи завжди ЛДУ має рішень, знайти умови існування розв'язку.
2). Чи є алгоритм, що дозволяє відшукати рішення ЛДУ.
Робота складається з двох розділів, у першій наведені теоретичні матеріали, в другій рішення деяких завдань.
У частині 1.1 наведені витяги з історії невизначених рівнянь. У частині 1.2. як теореми наводиться необхідна і достатня умова існування розв'язку ЛДУ, також йдеться про кількість рішень. Далі розглядаються методи знаходження рішень, в пункті 1.3 для деяких окремих випадків, у пункті 1.4 для будь-якого ЛДУ, який має розв'язок.

1. Діофант та історія діофантових рівнянь.

Діофант (Dióphantos) представляє одну з цікавих загадок в історії математики. Ми не знаємо, ким був Діофант, точні роки його життя, нам не відомі його попередники, які працювали б у тій же області, що й він. [10]
На могилі Діофанта є вірш-загадка, розв'язуючи яку неважко підрахувати, що Діофант прожив 84 роки. Про час життя Діофанта ми можемо судити по роботах французького дослідника науки Поля Таннрі, і це, ймовірно, середина III ст.н.е. [10]
Найбільш цікавим видається творчість Діофанта. «Праці його немов блискучому вогню серед повної непроникною пітьми». [Будівництво] До нас дійшло 7 книг з, можливо, 13 [1], які були об'єднані в «Арифметику». Стиль і зміст цих книг різко відрізняються від класичних античних творів з теорії чисел і алгебри, зразки яких ми знаємо по «Початкам» Евкліда, лем з творів Архімеда і Аполлонія. «Арифметика», безсумнівно, стала результатом численних досліджень, багато з яких залишилися нам невідомі. Ми можемо тільки гадати про її коріння і дивуватися багатству і красу її методів і результатів.
«Арифметика» Діофанта - це збірник задач (їх всього 189), кожна з яких має рішенням і необхідним поясненням. У збори входять вельми різноманітні завдання, а їх рішення часто надзвичайно дотепно. Діофант практикувався в знаходженні рішень невизначених рівнянь виду , або систем таких рівнянь. Типово для Діофанта, що його цікавлять тільки позитивні цілі та раціональні рішення. Ірраціональні рішення він називає «неможливими» і ретельно підбирає коефіцієнти так, щоб вийшли шукані позитивні, раціональні рішення.
Тому, звичайно, довільне невизначений рівняння (але, як правило, все-таки з цілими коефіцієнтами) отримує титул "діофантових", якщо хочуть підкреслити, що його потрібно вирішити в цілих числах.
Невизначені рівняння 1-го ступеня почали розглядатися індуськими математиками пізніше, приблизно з V століття. Деякі такі рівняння з двома і трьома невідомими з'явилися в зв'язку з проблемами, що виникли в астрономії, наприклад, при розгляді питань, пов'язаних з визначенням періодичного повторення небесних явищ. [2]
Перше спільне рішення рівняння першого ступеня , Де - Цілі числа, зустрічається в індійського мудреця Брахмагупти (бл. 625 г). Тому, строго кажучи, немає підстав називати лінійні невизначені рівняння діофантових. Однак, історично все ж склалося застосовувати термін «діофантових», до будь-якого рівняння, які розв'язуються в цілих числах.
У 1624 р. в публікується книга французького математика Баше де Мезірьяка «Problẻmes plaisans et delectables que se font par les nombres». Баше де Мезірьяк для вирішення рівняння фактично застосовує процес, що зводиться до послідовного обчислення неповних приватних і розгляду відповідних дробів.
Після Баше де Мезірьяка в XVII і XVIII століттях різні правила для вирішення невизначеного рівняння 1-го ступеня з двома невідомими давали Роль, Ейлер, Саундерсон та інші математики.
Ланцюгові дроби до рішення таких рівнянь були застосовані Лагранжем, який, однак, зауважує, що фактично це той же спосіб, який був даний Баше де Мезірьяком та іншими математиками, які розглядали невизначені рівняння до нього. Невизначені рівняння 1-го ступеня стали записуватися і вирішуватися у формі порівняння значно пізніше, починаючи з Гаусса. [2]
У серпні 1900 р. в Парижі відбувся II Міжнародний конгрес математиків. 8 серпня Д. Гільберт прочитав на ньому доповідь "Математичні проблеми". Серед 23 проблем, вирішення яких (на думку Д. Гільберта) абсолютно необхідно було отримати в наступаючому XX ст., Десяту проблему він визначив так:
"Нехай задано діофантових рівняння з довільним числом невідомих і раціональними числовими коефіцієнтами. Вказати спосіб, за допомогою якого можливо після кінцевого числа операцій встановити, вирішується чи це рівняння в цілих числах". [7]
Гіпотезу, що такого способу немає, першим висунув (з достатнім на те підставою) американський математик М. Девіс в 1949 р. Доказ цієї гіпотези розтягнулося на 20 років - останній крок був зроблений тільки в 1970 р. Юрієм Володимировичем Матіясеевічем, на першому році аспірантури він показав алгоритмічну нерозв'язність 10 проблеми Гільберта.
Проте, якщо про довільне діофантових рівняння не можна сказати, чи має воно цілі коріння, чи ні, то проблема існування цілих коренів ЛДУ вирішена. Наведемо теореми, користуючись якими завжди можна сказати, чи має цілі рішення дане ЛДУ чи ні.

2. Про числі рішень ЛДУ.

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

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

має рішення в цілих числах. , Очевидно, не порожньо, тому що при заданих , Можна підібрати цілі значення , Такі, щоб було позитивним числом.
У безлічі існує найменше число ( - Підмножина натуральних чисел), яке ми позначимо через Позначимо через - Цілі числа, такі, що
.
Нехай , Де ; Тоді

.
Ми підібрали цілі значення: , , ..., , Такі, що , Але , А - Найменше позитивне число в , Т. е. не може бути позитивним, , , .
Аналогічно отримуємо: , ..., .
Ми бачимо, що - Загальний дільник чисел , Отже, оскільки , , , , То рівняння вирішується в цілих числах.
Теорема 2. Нехай - Найбільший спільний дільник коефіцієнтів . Діофантових рівнянь має розв'язок тоді і тільки тоді, коли . Число рішень такого рівняння одно або нулю, або нескінченності.
Доведемо послідовно всі три твердження теореми.
1). Нехай . Для рівняння
,
де , Існують цілі числа: задовольняють йому. Тобто такі, що
.
Тоді

т. е. - Рішення рівняння.
2). Нехай тепер не ділить . Тоді ліва частина рівняння при будь-яких цілих ділиться на , А права на не ділитися, так що рівність при цілих значеннях неможливо.
3). Якщо - Упорядкована n-ка чисел, що задовольняє рівнянню, то наприклад, всі n-ки
при
також задовольняють цьому рівнянню і, таким чином, у нас або зовсім не буде рішень, або їх буде безліч.
Якщо хоч одна пара коефіцієнтів взаємно проста, то , І рівняння має незліченну безліч рішень.

3. Знаходження рішень для деяких окремих випадків ЛДУ.

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

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

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

3.2. ЛДУ з двома невідомими.

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

Спосіб 1.

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

Отримали спільне рішення: , Де .

Спосіб 2.

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

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

Отримуємо лінійне розкладання НОД:
, Тобто .
,
Отримали спільне рішення: , Де .
Як бачимо, отримали рішення, не збігалася з рішенням, знайденим першим способом.
Позначимо і отримаємо , Тобто ці рішення рівносильні.

Спосіб 3.

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

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

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

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

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

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

Відзначимо також, що

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

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

5. Приклади рішень завдань.

1).   Вирішити в цілих числах рівняння
4 x - 6 y + 11 z = 7, (4,6,11) = 1.
Розділивши з залишком -6 / 4, отримаємо -6 = 4 (-2) + 2. Уявімо вихідне рівняння у вигляді
4 (x - 2 y) + 2 y + 11 z = 7.
Після заміни x  = x - 2 y це рівняння запишеться наступним чином
4 x  + 2 y + 11 z = 7.
Враховуючи, що 11 = 2.5 + 1, перетворимо останнє рівняння:
4 x  + 2 (y + 5 z) + z = 7.
Поклавши y  = y + 5 z, отримаємо
4 x  + 2 y  + z = 7.
Це рівняння має наступне рішення: x , y  - довільні цілі числа, z = 7 - 4 x  - 2 y .
Отже y = y  - 5 z = 20 x  + 11 y  - 35, x = x  + 2 y = 41 x  + 22 y  - 70.
Таким чином, рішення вихідного рівняння має вигляд
, Де , - Довільні цілі числа.
2). Вирішити в цілих числах рівняння

Розділимо 5 на -4 з «залишком», , Перетворимо вихідне рівняння до вигляду
.
Замінивши отримаємо , Отже
, Є вирішенням даного ЛДУ.
Бібліографічний список.
1. Башмакова, І.Г. Діофант і Діофантові рівняння [Текст]. - М.: «Наука», 1972 р. - 68 с.
2. Бухштаб, А. А. Теорія чисел [Текст]. - М.: Державне навчально-педагогічне видавництво міністерства освіти РРФСР, 1960. - 378 с.
3. Виноградов, І.М. Основи теорії чисел: Навчальний посібник. 11-е вид. [Текст]. - СПб.: Видавництво «Лань», 2006. - 176 с.
4. Гаус, Карл Фрідріх Праці з теорії чисел. Під загальною ред. Виноградова І.М. [Текст] - М.: Изд. академічних наук СРСР, 1959 р. - 980 с.
5. Гельфонд, А.О. Рішення рівнянь у цілих числах. Популярні лекції з математики, вип. [Текст]. М.: «Гостехиздат», 1957 р. - 66 с.
6. Давенпорт, Г. Введення в теорію чисел [Текст]: Пер. з англійської Мороза Б.З. під ред. Линника Ю.В. - М.: «Наука», 1965 р. - 176 с.
7. Матісеевіч, Ю.В. Десята проблема Гільберта [Текст]. - М.: «Фізматліт», 1973 р. - 224 с.
8. Міхеловіч, Ш.Х. Теорія чисел [Текст]. - М.: «Вища школа», 1962 р. - 260 с.
9. Соловйов, Ю. Невизначені рівняння першого ступеня [Текст]: Квант, 1992 р., № 4.
10. Будівництво, Д.Я. Короткий нарис історії математики [Текст]. - М.: «Наука», 1990 р. - 256 с.