Лекції з теорії чисел

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

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

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

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

Книга Діофанта несподівано справила ще й величезний опосередкований вплив на розвиток математичної науки останніх трьох століть. Справа в тому, що юрист з Тулузи П'єр Ферма (1601 - 1665), вивчаючи "Арифметику" Діофанта, зробив на полях цієї книги знамениту позначку: "Я знайшов воістину дивовижний доказ того, що рівняння xn+yn=zn при n> , немає рішень у цілих числах, проте поля цієї книжки дуже малі, щоб тут його вмістити". Це одне з найкорисніших математичних тверджень отримало назву "Великої теореми Ферма" і, чомусь, викликало справжній ажіотаж серед математиків та аматорів (особливо після призначення у 1908 році за його доказ премії у 100 000 німецьких марок). Спроби добити цю марну теорему породили цілі розділи сучасної алгебри, теорії алгебри чисел, теорії функцій комплексного змінного і алгебраїчної геометрії, практична користь від яких вже не підлягає жодному сумніву. Сама теорема, здається, благополучно доведена у 1995 році; П'єр Ферма, звичайно, погарячкував на полях "Арифметики", бо він фізично не міг придумати подібного доказу, що потребує колосальної сукупності математичних знань. Елементарного доказу великої теореми Ферма поки що ніхто з жителів нашої планети знайти не зміг, хоча над його пошуком билися найкращі уми останніх трьох століть. Проте, досі тисячі психічно нездорових любителів-"ферматистів" у жадобі слави та грошей бомбардують своїми листами академічні інститути та університети та майже щороку один із співробітників кафедри алгебри та дискретної математики Уральського держуніверситету, де я працюю, змушений вести з таким психом дипломатичнулистування на заздалегідь заготовленому бланку:

"Шановний. У Вашому доказі на сторінці №. у рядку №. міститься помилка. ".

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

де a, b, c Про Z; a та b - не нулі.

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

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

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

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

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

Випадок 1. Нехай c = 0, рівняння має вигляд ax + by = 0 – "однорідне лінійне діофантове рівняння". Трохи попрацювавши, знаходимо, що

x = -b ay.

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

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

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

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

м н оx = x 0 - bt y = y 0 + at.

Таким чином, і в теорії лінійних діофантових рівнянь загальне рішення неоднорідного рівняння є сумою загального розв'язання відповідного однорідного рівняння та деякого (будь-якого) приватного розв'язання неоднорідного рівняння. Ось воно – прояв єдності лінійного світу! (Одного разу, перед іспитом з диференціальних рівнянь, мені снився кошмар, ніби всі лінійні простори рішень змовилися між собою і вимагали від мене додати до них приватне рішення, оскільки вони не хотіли утримувати нульовий вектор, а хотіли бути лінійними різноманіттями. Я відмовився, а на ранок, на іспиті, мені дісталася однорідна система!)

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

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

- Однорідне рівняння. Далі, дивлячись на випадок 1, розгляд якого завершився кількома рядками вище, пишемо відразу загальне рішення: x * - x 0 = - bt , y * - y 0 = at, звідки миттєво, використовуючи навички третього класу середньої школи, отримуємо:

м н оx * = x 0-bt, y * = y 0 + at.

"Все це, звичайно, цікаво", - скаже читач, - "Але як же шукати те саме приватне рішення x 0 , y 0 & gt;, заради якого і затіяна вся метушня цього пункту і яке, як тепер з'ясовується, нам так потрібно?". Відповідь до дурості проста. Ми домовилися, що ( a , b ) = 1. Це означає, що знайдуться такі u і v з Z , що au + bv = 1 (якщо ви забули, поверніться в пункт 4), причому ці u і v ми легко вміємо знаходити з допомогою алгоритму Евкліда. Помножимо тепер рівність au + bv = 1 c і отримаємо: a ( uc ) + b ( vc ) = c , тобто. x 0 = uc, y 0 = vc. От і все!

приклад. Ви - хроноп, придуманий Хуліо Кортасаром у книзі "З життя хронопів та фамів". Вам потрібно розплатитись у магазині за синю пожежну кишку, бо червона в господарстві вже давно є. У вас у кишені монети номіналом лише в 7 і 12 копійок, а вам треба сплатити 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 0 = uc = (-5) · 43 = - 215 y 0 = vc = 3 · 43 = 129.

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

x = -215 - 12 t y = 129 + 7 t

і, легко бачити, що при t = - 18, виходять цілком розумні x = 1, y = 3, тому дубасити касира необов'язково.

Завдання

1 . Розв'яжіть діофантові рівняння:

б) 6 x – 27 y = 21;

в) 11 x + 99 y = 41.

2 . Для кожного цілого z розв'яжіть у цілих числах рівняння 2 x + 3 y = 5 z.

3 . Розв'яжіть рівняння 3 sin 7 x + cos 20 x = 4, а потім запропонуйте вирішити його знайомому школяру. Хто швидше?

4 . Скільки різними способами можна розплатитися за смачну дев'яностосемикопеечную жувальну гумку лише п'ятаками та копійками?