Решение линейных диофантовых уравнений. Способы решения диофантовых уравнений. Большая теорема Ферма

Сегодня предлагаю поразмышлять над некоторой интересной математической задачкой.
А именно, давайте-ка для разминки решим следующее линейной уравнение:

«Чего сложного?» - спросите вы. Действительно, лишь одно уравнение и целых четыре неизвестных. Следовательно, три переменных есть свободные, а последняя зависит от оных. Так давайте выразим скорее! Например, через переменную , тогда множество решений следующее:

где - множество любых действительных чисел.

Что же, решение действительно оказалось слишком тривиальным. Тогда будем нашу задачу усложнять и делать её более интересной.

Вспомним про линейные уравнения с целыми коэффициентами и целыми корнями , которые, собственно, являются разновидностью диофантовых уравнений . Конкретно - наложим на наше уравнение соответствующие ограничение на целочисленность коэффициентов и корней. Коэффициенты при неизвестных у нас и так целые (), а вот сами неизвестные необходимо ограничить следующим:

где - множество целых чисел.

Теперь решение, полученное в начале статьи, «не проканает», так как мы рискуем получить как рациональное (дробное) число. Так как же решить это уравнение исключительно в целых числах?

Заинтересовавшихся решением данной задачи прошу под кат.

А мы с вами продолжаем. Попробуем произвести некоторые элементарные преобразования искомого уравнения:

Задача выглядит по-прежнему непонятной, в таких случаях математики обычно производят какую-нибудь замену. Давайте и мы с вами её бахнем:

Опа, мы с вами достигли интересного результата! Коэффициент при у нас сейчас равен единице , а это значит, что мы с вами можем выразить эту неизвестную через остальные неизвестные в этом уравнении без всяких делений (чем грешили в самом начале статьи). Сделаем это:

Обращу внимание, что это говорит нам о том, что какие бы не были (в рамках диофантовых уравнений), всё равно останется целым числом, и это прекрасно.

Вспоминая, что справедливо говорить, что . А подставив заместо полученный выше результат получим:

Тут мы также видим, что что какие бы не были , всё равно останется целым числом, и это по-прежнему прекрасно.

Тогда в голову приходит гениальная идея: так давайте же объявим как свободные переменные, а будем выражать через них! На самом деле, мы уже это сделали. Осталось только записать ответ в систему решений:

Теперь можно лицезреть, что в системе решений нигде нет деления , а это значит, что всегда решения будут целочисленными. Попробуем найти частное решение исходного уравнения, положив, к примеру, что :

Подставим в исходное уравнение:

Тождественно, круто! Давайте попробуем ещё разок на другом примере?

Тут мы видим отрицательный коэффициент, он может доставить нам изрядных проблем, так что давайте от греха избавимся от него заменой , тогда уравнение будет следующим:

Как мы помним, наша задача сделать такие преобразования, чтобы в нашем уравнении оказалась неизвестная с единичным коэффициентом при ней (чтобы затем выразить её через остальные без любого деления). Для этого мы должны снова что-нибудь взять «за скобку», самое быстрое - это брать коэффициенты из уравнения которые самые близкие к единице. Однако нужно понимать, что за скобку можно взять только лишь то число, которое обязательно является каким-либо коэффициентом уравнения (ни больше, ни меньше), иначе наткнемся на тавтологию/противоречие или дроби (иными словами, нельзя чтобы свободные переменные появились где-то кроме как в последней замене). Итак:

Введем замену , тогда получим:

Вновь возьмем за скобку и наконец получим в уравнении неизвестную с единичным коэффициентом:

Введем замену , тогда:

Выразим отсюда нашу одинокую неизвестную :

Из этого следует, что какие бы мы не взяли, все равно останется целым числом. Тогда найдем из соотношения :

Аналогичным образом найдем из соотношения :

На этом наша система решений созрела - мы выразили абсолютно все неизвестные, не прибегая к делению, тем самым показывая, что решение точно будет целочисленным. Также не забываем, что , и нам надо ввести обратную замену. Тогда окончательная система решений следующая:

Таким образом, осталось ответить на вопрос - а любое ли подобное уравнение можно так решить? Ответ: нет, если уравнение в принципе нерешаемо. Такое возникает в тех случаях, если свободный член не делится нацело на НОД всех коэффициентов при неизвестных. Иными словами, имея уравнение:

Для его решения в целых числах достаточно выполнение следующего условия:

(где - наибольший общий делитель).

Доказательство

Доказательство в рамках этой статьи не рассматривается, так как это повод для отдельной статьи. Увидеть его вы можете, например, в чудесной книге В. Серпинского «О решении уравнений в целых числах» в §2.

Резюмируя вышесказанное, выпишем алгоритм действий для решения линейных диофантовых уравнений с любым числом неизвестных:

В заключение стоит сказать, что также можно добавить ограничения на каждый член уравнения в виде неравенства на оного (тогда к системе решений добавляется система неравенств, в соответствии с которой нужно будет скорректировать ответ), а также добавить ещё чего-нибудь интересное. Ещё не стоит забывать и про то, что алгоритм решения является строгим и поддается записи в виде программы для ЭВМ.

С вами был Петр,
спасибо за внимание.

Введение …………………………………………………………………………………………………1-2

1. Диофант и его труды ……………………………………………………………………………3-4

2. Решение Диофантовых уравнений……………………………………………………..4-7

2.1. Диофантовы уравнения с одним неизвестным ……………………………..4-5

2.2. Неопределенные уравнения II-ой степени вида x2 + y2 = z2………….5-6

2.3. Примеры решения задач………………………………………………………………….7

3. Мои исследования………………………………………………………………………………8-11

4. О «многоугольных числах» Диофанта………………………………………………11-14

5. Заключение ………………………………………………………………………………………..15

6. Список используемой литературы ……………………………………………………16

Введение.

Не много истории. О подробностях жизни Диофанта Александрийского практически ничего не известно. Диофант цитирует Гипсикла - II век до нашей эры, о Диофанте пишет Теон Александрийский - около 350 года нашей эры, можно предположить, что его жизнь протекала в границах этого периода. Возможное уточнение времени жизни Диофанта основано на том, что его «Арифметика» посвящена «достопочтеннейшему Дионисию». Полагают, что этот Дионисий - никто иной, как епископ Дионисий Александрийский, живший в середине III века нашей эры. Место жительства Диофанта хорошо известно – это знаменитая Александрия. Центр научной мысли эллинистического мира. В Палатинской антологии содержится эпиграмма–задача:

Прах Диофанта гробница покоит; дивись ей - и камень.

Мудрым искусством его скажет усопшего век.

Волей богов шестую часть жизни он прожил ребенком.

И половину шестой встретил с пушком на щеках.

Только минула седьмая. С подругой он обручился.

С нею, пять лет проведя, сына дождался мудрец;

Только полжизни отцовской, возлюбленный сын его прожил.

Отнят он был у отца ранней могилой своей.

Дважды два года родитель оплакивал тяжкое горе,

Тут и увидел предел жизни печальной своей.

(Перевод)

Используя современные методы решения уравнений можно сосчитать, сколько лет прожил Диофант.

Пусть Диофант прожил x лет. Составим и решим уравнение:

Умножим уравнение на 84, чтобы избавиться от дробей:

Таким образом, Диофант прожил 84 года.*(Энциклопедический словарь юного математика. составитель – Москва: педагогика, 1989 г.)

При исследовании диофантовых уравнений обычно ставятся следующие вопросы:

1. Имеет ли уравнение целочисленные решения;

2. Конечное, или бесконечное множество его целочисленных решений;

3. Решить уравнение на множестве целых чисел, т. е. найти все его целочисленные решения

4. Решить уравнение на множестве целых положительных чисел;

Поэтому мне представляется интересным самому исследовать на основе фактов представленных ранее «Диофантовы уравнения».

Отсюда целью моей работы является:

Исследовать варианты решения уравнений с одной неизвестной;

Исследовать варианты уравнений с двумя неизвестными;

Найти общие закономерности результатов решений поставленных задач.

Актуальность исследования обусловлена трудностями решения уравнений и задач на составление «Диофантовых уравнений»

Материал, представленный в данной работе, основывается на исследовании олимпиадных задачах и экзаменационных работах.

I . Диофант и его труды

Основное произведение Диофанта – «Арифметика» в тринадцати книгах. К сожалению, до наших дней сохранились только шесть первых книг из тринадцати. «Арифметика» Диофанта – это сборник задач их всего 189, каждая из которых снабжена решением или несколькими способами решения и необходимыми пояснениями. Поэтому, с первого взгляда, кажется, что она не является теоретическим произведением. Однако, при внимательном чтении видно, что задачи тщательно подобраны и служат для иллюстрации вполне определенных, строго продуманных методов. Как это было принято в древности, методы не формулируются в общем виде, а повторяются для решения однотипных задач. Главная проблематика «Арифметики» – это нахождение положительных рациональных решений неопределенных уравнений. Рациональные числа трактуются Диофантом так же, как и натуральные, что не типично для античных математиков. Сначала Диофант исследует системы уравнений второго порядка от двух неизвестных. Он указывает метод нахождения других решений, если одно уже известно. Затем аналогичные методы он применяет к уравнениям высших степеней. В X веке «Арифметика» была переведена на арабский язык, после чего математики стран ислама, Абу Камил и другие, продолжили некоторые исследования Диофанта. В Европе интерес к «Арифметике» возрос после того, как Рафаэль Бомбелли обнаружил это сочинение в Ватиканской библиотеке и опубликовал 143 задачи из его в своей «Алгебре» (1572 года). В 1621 году появился классический, подробно прокомментированный латинский перевод «Арифметики», выполненный Баше де Мезириаком. Методы Диофанта оказали огромное влияние на Франсуа Виета и Пьера Ферма, впрочем, в Новое время неопределенные уравнения обычно решаются в целых числах, а не в рациональных, как это делал Диофант. Известны и другие сочинения Диофанта. Трактат «О многоугольных числах» сохранился не полностью. В сохранившейся части методами геометрической алгебры выводится ряд вспомогательных теорем. Из сочинений Диофанта «Об измерении поверхностей» и «Об умножении» также сохранились лишь отрывки. Книга Диофанта «Поризмы» известна только по нескольким теоремам, используемым в Арифметике.*(Перельман математика. – Москва, 1962 г.)

Вывод: На основании вышеизложенного материала следует сделать вывод о том, что Диофант Александрийский не останавливается на одном решении, он старается обнаружить второе и последующее в поставленной задаче.

2. Решение Диофантовых уравнений.

2.1. Диофантовы уравнения с одним неизвестным.

где - целые числа.

Теорема. Если уравнение с целыми коэффициентами имеет целый корень, то этот корень является делителем числа (свободного члена уравнения). Таким образом, при отыскании целых корней уравнения с целыми коэффициентами достаточно испытать лишь делители свободного члена.*(Приглашение в элементарную теорию чисел. , .)

Задача 1

Решение. Свободный член уравнения имеет следующие делители https://pandia.ru/text/78/308/images/image009_5.gif" width="92 height=23" height="23">.

Задача 2 . Решить в целых числах уравнение

2x4 + 7x3 - 12x2 - 38x + 21 = 0.

Решение . Свободный член уравнения имеет следующие делители

Подстановкой в исходное уравнение убеждаемся, что из этого множества только

число -3 является его целым корнем.

Ответ: х=-3.

2.2. Неопределенные уравнения II -ой степени вида x 2 + y 2 = z 2

Существует еще одна частная задача на неопределенные уравнения – теперь уже второй степени, возникшая примерно за две тысячи лет до Диофанта в Древнем Египте.

Если стороны треугольника пропорциональны числам 3, 4 и 5, то этот треугольник – прямоугольный. Этот факт использовали для построения на местности прямых углов. Поступали довольно просто. На веревке на равном расстоянии друг от друга завязывали узлы (Рис. 1)

Рис. 1.

В точке С где надо было построить прямой угол, забивали колышек, веревку натягивали в направлении, нужном строителям, забивали колышек в точке В (СВ = 4) и натягивали веревку так, чтобы АС = 3 и АВ = 5. Треугольник с такими длинами сторон называют египетским. Мы, конечно, понимаем, что безошибочность такого построения следует из теоремы, обратной теореме Пифагора. Действительно,

32 + 42 = 52..gif" width="85 height=24" height="24"> в целых числах оказался довольно простым. Запишем подряд квадраты натуральных чисел, отделив их друг от друга запятой. Под каждой запятой запишем разность между последовательными квадратами:

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196 … .

3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27 … .

А теперь внимание! Нет ли и в нижней строке квадратных чисел? Есть! Первое из них 9 = 32, над ним 16 = 42 и 25 = 52, знакомая нам тройка 3, 4, 5.

Следующее квадратное число в нижней строке 25, ему соответствует 144 и 169, отсюда находим вторую известную нам тройку 5, 12, 13 и т. д. Отсюда мы имеем право сформулировать такую теорему: Каждое нечетное число есть разность двух последовательных квадратов. Составлять такие строки – довольно скучное и трудоемкое занятие. По формулам находить такие тройки чисел и проще и быстрее. Проверим что если - нечетное число, то и . Проверим также, что в этом случае равенство DIV_ADBLOCK443">

если https://pandia.ru/text/78/308/images/image019_2.gif" width="88" height="41 src=">.gif" width="37" height="18 src=">.gif" width="100" height="42 src="> - вторая тройка и т. д.*(Башмакова, и диофантовы уравнения– М.:«Наука», 1972г.)

2.3. Примеры решения задач.

Задача 1 .Найти все пары натуральных чисел, удовлетворяющих уравнению

Решение. Разложим левую часть уравнения на множители и запишем уравнение вида: https://pandia.ru/text/78/308/images/image026_0.gif" width="63" height="21">, получим две системы уравнений, решив которые мы сможем найти искомые числа:

Первая система имеет решение https://pandia.ru/text/78/308/images/image030_0.gif" width="91" height="21">.

Ответ: .

Задача 2 . Доказать, что уравнение

Не имеет целых решений.

Решение. Разложим левую часть уравнения на множители и запишем данное уравнение в виде. 1 случай..gif" width="57" height="24 src=">, но это число не является целым. Значит, при у=0 данное уравнение не имеет целых решений. 2 случай. Пусть , тогда все пять множителей в левой части уравнения различны. С другой стороны число 33 можно представить в виде произведения максиму четырёх различных множителей (33=1·3·11 или 33=-1·3·(-11)·1 и т. д.). Следовательно, при данное уравнение также не имеет целых решений.*(Новоселов курс элементарной алгебры. – М:Советская наука, 1956). Следует сделать вывод о том, что решения уравнений сводятся к нахождению натуральных чисел; с помощью «Пифагоровой тройки»

3. Мои исследования.

1. Найти все натуральные числа с, для которых уравнение Зх + 5у = с имеет решение в неотрицательных целых числах.

Ясно, что при с = 3,5, 6, 8, 9 уравнение Зх + 5 у = с имеет решение в неотрицательных числах х и у, а при с = 1, 2, 4, 7 таких решений уравнение не имеет. Заметим также, что если Зn + 5т = с, (n, m Є N), то 3(n +1) + 5т = с + 3, поэтому, так как 3*1 + 5*1 = 8, то уравнение Зх + 5у = с при с = 8, 8 + 3 = 11, 11 + 3 = 14, 17, 20, 23,... имеет решение. Аналогично, так как 3*3 = 9 и 5*2 = 10, то при с = 9, 9 + 3 = 12, 15, 18,... и при с = 10, 13, 16, 19,... уравнение Зх + 5 у = с имеет решение в неотрицательных целых числах. Но в последовательностях 8 + 3t, 9 + 3t, 10 + 3t, где t = 0,1, 2, 3,... содержатся все натуральные числа больше 7. Таким образом, при любом натуральном с > 1 уравнение Зх + 5 у = с имеет решение в неотрицательных целых числах х и у. Приведу еще один способ решения задания. Этот способ менее изощренный, чем ранее приведенный, но более универсальный. Состоит он в том, что сначала мы находим все целочисленные решения уравнения по формулам (1), а затем в силу неотрицательности х и у получаем некоторые ограничения на целочисленный параметр t. Итак, из 3*2 + 5*(-1) = 1 следует, 3*(2с) + 5*(-с) = с, то есть х0=2с и у0=-с. Откуда, по формулам (1) получаем х = 2с-5t, у = - с + 3t. Далее, из условий 2c-5t≥0 и - с+ 3t≥0 получаем t Є . Таким образом, для решения задачи нам надо указать все такие натуральные значения с, при которых отрезок содержит хотя бы одно целое число. Ясно, что если длина отрезка

2c/5 – c/3 = c/15 не менее единицы, то в нем обязательно содержится целое число. Отсюда следует, что при с ≥15 уравнение 3х +5у=с разрешимо в неотрицательных целых числах. Случаи, когда 1≤с≤14, можно легко проверить простым перебором. Найдем, что с Є {3;5;6;8;9;10;11;12;13;14}. Таким образом, получаем ответ: с Є {3;5;6} U {z Є Z │ z≥8 }.

2. Решить в целых числах уравнение:

Разделим 5 на -4 с «остатком», , преобразуем исходное уравнение к виду

Заменив https://pandia.ru/text/78/308/images/image041.gif" width="140" height="21 src=">, следовательно

DIV_ADBLOCK445">

Откуда 2х+у+7(3х-2у+z)=5. Полагая теперь и= 3х-2у+z, получаем уравнение: 2х+у+7и=5.

Таким образом, окончательно получаем: У= 5-2х-7и, z=10-7х-13и, где параметры х, и Є Z дают общее решение предположенного диофантова уравнения. Этот метод «наименьшего коэффициента» применим и для решения диофантовых уравнений вида ax+by=c.

4. Найти натуральное число, которое при делении на 3 дает остаток 2, а при делении на 5- остаток 3.

Обозначим искомое число через х. Если частное от деления х на 3 обозначим через у, а частное от деления на 5 через z, то по теореме о делении с остатком получим х=3у+2, х=5z+3. Таким образом, нам надо решить в натуральных числах уравнение 5z-3у+1=0. Применяя описанный ранее алгоритм решения этого уравнения, получаем z=1+3t, y= 2+5t (t Є Z) и, значит, x=5z+3=5(2+3t)+3= 8+15t. Так как х по условию должен быть натуральным числом, то параметр t в ответе должен принимать только неотрицательные целые значения, т. е. Х=8+15t, t Є Z.

5. Куплены фломастеры по 7 рублей и карандаши по 4 рубля за штуку, всего на сумму 53 рубля. Сколько куплено фломастеров и карандашей?

Пусть х – число фломастеров, у – число карандашей, тогда по условию 7х+ 4у=53. Частное решение этого линейного диофантова уравнения есть: х=7, у=1. Тогда общее решение его имеет вид: х= 7-4t, y= 1+7t, t Є Z. Однако, так как по условию х> 0, y>0, то значениями параметра t могут быть лишь t=0 и t=1. При t=0 получаем х=7, у=1, а при t=1 имеем: х=3, у=8. Таким образом, решений два, т. е. возможны два варианта покупки фломастеров и карандашей на сумму 53 рубля.

6. Разность двух натуральных чисел равна 66, а их НОК равно 360. Найти эти числа.

Пусть а и b данные натуральные числа, тогда, по условию, имеем систему уравнений: Так как

а| 360, b | 360, то 360 = а*n, 360 = b*т, где n, m Є N. Отсюда получаем

https://pandia.ru/text/78/308/images/image045.gif" width="27" height="15">.gif" width="31" height="41 src=">, и, подставляя эти выражения в первое уравнение системы, приведя к общему знаменателю, имеем 60m-60n=11mn, откуда находим

Так как m>0 и n - натуральное число, причем n0, то перебором находим n=4, n=5, тогда m=15, m=60, а значит, https://pandia.ru/text/78/308/images/image054.gif" width="31" height="41 src=">.gif" width="31" height="41 src=">.gif" width="31" height="41 src=">.gif" width="31" height="41 src=">=6. Таким образом, получаем, что две пары чисел удовлетворяют условию задачи:

а=90, b=24 и a=72, b=6. *(Форков олимпиады в школе. – Москва: Айрис - пресс, 2003 г.)

Вывод: На основании проведенных мною исследований по Диофантовым уравнениям следует сделать вывод о том, что можно использовать различные подходы при их решении.

4. О «многоугольных числах» Диофанта

Каждое из возрастающих от единицы чисел, начиная с трех, является первым, начиная от единицы, называется многоугольником и имеет столько углов, сколько в нем содержится единиц, стороной же его будет число, которое следует за единицей, т. е. 2. Тогда 3 будет треугольником, 4 - четырехугольником, 5 - пятиугольником и т. д. О квадратах хорошо известно, что они получаются от умножения некоторого числа на самого себя. Доказывается также, что каждый многоугольник, умноженный на число, зависящее от количества его углов, и сложенный с квадратом некоторого числа, тоже зависящего от количества его углов, может быть представлен как некоторый квадрат. Если три числа имеют одинаковые разности, то восемь раз взятое произведение наибольшего и среднего, сложенное с квадратом наименьшего, будет квадратом, сторона которого равна сумме наибольшего и двух средних.

Действительно, пусть три числа АВ, В Г и ВД имеют одинаковые разности; нужно доказать, что 8АВ*ВГ, (сложенное с АВ2, образует квадрат, сторона которого равна сумме АВ и 2ВГ.

8АВ*ВГ разложим на 8ВГ2 и 8АГ*ВГ.) Затем каждое из упомянутых разделим пополам, получим 4АВ*ВГ, 4ВГ2 и 4АГ*ВГ т. е. 4ВГ*ГД, ибо АГ равно ГД; вместе же с ДВ2 получится АВ2 . Второе из произведений 4АГ-ГВ, сложенное с ДВ2, дает В А2. Теперь остается узнать, каким образом АВ2 вместе с 4АВ*ВГ и 4ВГ2 даст в сумме квадрат. Если мы положим АЕ, равным ВГ, то 4АВ*ВГ преобразуется в 4ВА*АЕ, которое, будучи сложено с 4ГВ2 или с 4АЕ2, сделается равным 4ВЕ*ЕА (ВА*АЕ + АЕ2 = АЕ*(АЕ + АВ) = ВЕ*ЕА.), а оно, сложенное с АВ2, сделается равным квадрату на сумме BE и ЕА, как одной прямой (4ВЕ-ЕА + АВ2 = (BE + ЕА)2.). Но сумма BE и ЕА равна сумме АВ и 2АЕ, т. е. 2ВГ. Что и требовалось доказать. Если дано любое количество чисел с одинаковыми разностями, то разность между наибольшим и наименьшим равняется разности чисел, умноженной на уменьшенное, на единицу количество заданных чисел. Пусть даны любые числа АВ, ВГ, ВД, BE с одинаковыми разностями, нужно показать, что разность между

АВ и BE равна разности между АВ и ВГ, умноженной на количество АВ, ВГ, ВД, BE, уменьшенное на единицу.

Действительно, поскольку предполагается, что АВ, ВГ, ВД, BE имеют между собой одинаковые разности, то, значит, АГ, ГД, ДЕ будут между собой равными. Следовательно, ЕА равняется АГ, умноженному на количество АГ, ГД, ДЕ; количество же АГ, ГД, ДЕ будет на единицу меньше количества АВ, ВГ, ВД, BE; таким образом, ЕА кратно АГ в число раз, на единицу меньшее количества АВ, ВГ, В Д, BE. И АЕ представляет разность между наибольшим и наименьшим числами, а АГ есть их одна общая разность. Простым же языком говоря, то существуют треугольные, четырехугольные, пятиугольные и т. д.

Треугольные числа

https://pandia.ru/text/78/308/images/image064.gif" alt="\frac{n(n+1)}{2}" width="73" height="42">

Свойства:

· Сумма двух последовательных треугольных чисел даёт полный квадрат (квадратное число).

Чётность элемента последовательности меняется с периодом 4: нечётное, нечётное, чётное, чётное.

Квадратные числа

Квадратные числа представляют собой произведение двух одинаковых натуральных чисел, то есть являются полными квадратами:

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, …, n².

Пятиугольные числа

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …, *(Арифметика и книга о многоугольных числах. Перевод с древнегреческого)

Вывод: С помощью геометрической интерпретации, Диофант вывел формулы последовательностей многоугольных чисел, что вызывает интерес у математиков.

5. Заключение.

Диофант Александрийский, стремится свести решения от простого к сложному, основываясь на различных подходах к решению уравнений, а так же используя «Пифагоровы тройки».

В заключительной части своей работы мне особенно хотелось подчеркнуть, что изучив специальную литературу, посвященную диофантовым уравнениям, я расширил свои математические навыки и получил дополнительные знания о самом Диофанте, его последователях, а также о влиянии его научных трудов на дальнейшее развитие научной математической мысли. Именно благодаря методам Диофанта были разгаданы методы самого Архимеда. И если история интеграционных методов Архимеда в основном завершается созданием интегрального и дифференциального исчисления Ньютоном и Лейбницем, то история методов Диофанта растягивается еще на несколько сотен лет, переплетаясь с развитием теории алгебраических функций и алгебраической геометрии. Развитие идей Диофанта можно проследить вплоть до работ Анри Пуанкаре и Андре Вейля. Именно Диофант открыл нам мир арифметики и алгебры. Поэтому история Диофантова анализа показалась мне особенно интересной.

6. Список используемой литературы.

1. Арифметика и книга о многоугольных числах. Перевод с древнегреческого

2. Башмакова, и диофантовы уравнения– М.:«Наука», 1972г.

3. Задания городских и районных олимпиад.

4.Новоселов курс элементарной алгебры. – М:Советская наука, 1956

5. Перельман математика. – Москва, 1962 г.

6. Приглашение в элементарную теорию чисел. , .

7. Форков олимпиады в школе. – Москва: Айрис-пресс, 2003 г.

8.Черкасов. Интенсивный курс подготовки к экзамену.- М.: Рольф. 2000.

9.Энциклопедический словарь юного математика. Составитель – Москва: педагогика, 1989 г.

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение высшего

профессионального образования

«Тобольская государственная социально-педагогическая академия

им. Д.И. Менделеева»

Кафедра математики, ТиМОМ

Некоторые диофантовы уравнения

Курсовая работа

студента III курса ФМФ

Матаева Евгения Викторовича

Научный руководитель:

к.ф.-м.н.Валицкас А.И.

Оценка: ____________

Тобольск – 2011

Введение……………………………………………………………………........ 2

§ 1. Линейные диофантовы уравнения………………………………….. 3

§ 2. Диофантово уравнение x 2 – y 2 = a ………………………………….....9

§ 3. Диофантово уравнение x 2 + y 2 = a …………………………………... 12

§ 4. Уравнение х 2 + х + 1 = 3у 2 …………………………………………….. 16

§ 5. Пифагоровы тройки………………………………………………….. 19

§ 6. Великая теорема Ферма………………………………………………23

Заключение……………………………………………………………….….....29

Список литературы........... ………………………………………………..30

ВВЕДЕНИЕ

Диофантово уравнение – это уравнение вида P (x 1 , … , x n ) = 0 , где левая часть представляет собой многочлен от переменных x 1 , … , x n с целыми коэффициентами. Любой упорядоченный набор (u 1 ; … ; u n ) целых чисел со свойством P (u 1 , … , u n ) = 0 называется (частным) решением диофантова уравнения P (x 1 , … , x n ) = 0 . Решить диофантово уравнение – значит найти все его решения, т.е. общее решение этого уравнения.

Нашей целью будет научиться находить решения некоторых диофантовых уравнений, если эти решения имеется.

Для этого, необходимо ответить на следующие вопросы:

а. Всегда ли диофантово уравнение имеет решение, найти условия существования решения.

б. Имеется ли алгоритм, позволяющий отыскать решение диофантова уравнения.

Примеры: 1. Диофантово уравнение 5 x – 1 = 0 не имеет решений.

2. Диофантово уравнение 5 x – 10 = 0 имеет решение x = 2 , которое является единственным.

3. Уравнение ln x – 8 x 2 = 0 не является диофантовым.

4. Часто уравнения вида P (x 1 , … , x n ) = Q (x 1 , … , x n ) , где P (x 1 , … , x n ) , Q (x 1 , … , x n ) – многочлены с целыми коэффициентами, также называют диофантовыми. Их можно записать в виде P (x 1 , … , x n ) – Q (x 1 , … , x n ) = 0 , который является стандартным для диофантовых уравнений.

5. x 2 – y 2 = a – диофантово уравнение второй степени с двумя неизвестными x и y при любом целом a. Оно имеет решения при a = 1 , но не имеет решений при a = 2 .

§ 1. Линейные диофантовы уравнения

Пусть a 1 , … , a n , с Z . Уравнение вида a 1 x 1 + … + a n x n = c называется линейным диофантовым уравнением с коэффициентами a 1 , … , a n , правой частью c и неизвестными x 1 , … , x n . Если правая часть с линейного диофантова уравнения нулевая, то такое диофантово уравнение называется однородным.

Наша ближайшая цель – научиться находить частные и общие решения линейных диофантовых уравнений с двумя неизвестными. Очевидно, что любое однородное диофантово уравнение a 1 x 1 + … + a n x n = 0 всегда имеет частное решение (0; … ; 0).

Очевидно, что линейное диофантово уравнение, все коэффициенты которого равны нулю, имеет решение только в случае, когда его правая часть равна нулю. В общем случае имеет место следующая

Теорема (о существовании решения линейного диофантова уравнения). Линейное диофантово уравнение a 1 x 1 + … + a n x n = c , не все коэффициенты которого равны нулю, имеет решение тогда и только тогда, когда НОД(a 1 , … , a n ) | c.

Доказательство. Необходимость условия очевидна: НОД(a 1 , … , a n ) | a i (1 i n ) , так что НОД(a 1 , … , a n ) | (a 1 x 1 + … + a n x n ) , а значит, делит и

c = a 1 x 1 + … + a n x n .

Пусть D = НОД(a 1 , … , a n ) , с = Dt и a 1 u 1 + … + a n u n = D – линейное разложение наибольшего общего делителя чисел a 1 , … , a n . Умножая обе части на t , получим a 1 (u 1 t ) + … + a n (u n t ) = Dt = c , т.е. целочисленная

n -ка (x 1 t ; … ; x n t) является решением исходного уравнения с n неизвестными.

Теорема доказана.

Эта теорема даёт конструктивный алгоритм для нахождения частных решений линейных диофантовых уравнений.

Примеры: 1. Линейное диофантово уравнение 12x+21y = 5 не имеет решений, поскольку НОД(12, 21) = 3 не делит 5 .

2. Найти частное решение диофантова уравнения 12x+21y = 6 .

Очевидно, что теперь НОД(12, 21) = 3 | 6 , так что решение существует. Запишем линейное разложение НОД(12, 21) = 3 = 122 + 21(–1) . Поэтому пара (2; –1) – частное решение уравнения 12x+21y = 3 , а пара (4; –2) – частное решение исходного уравнения 12x+21y = 6 .

3. Найти частное решение линейного уравнения 12x + 21y – 2z = 5 .

Так как (12, 21, –2) = ((12, 21), –2) = (3, –2) = 1 | 5 , то решение существует. Следуя доказательству теоремы, вначале найдём решение уравнения (12,21)х–2у=5 , а затем, подставив линейное разложение наибольшего общего делителя из предыдущей задачи, получим решение исходного уравнения.

Для решения уравнения 3х – 2у = 5 запишем линейное разложение НОД(3, –2) = 1 = 31 – 21 очевидно. Поэтому пара чисел (1; 1) является решением уравнения 3 x – 2 y = 1 , а пара (5; 5) – частным решением диофантова уравнения 3х – 2у = 5 .

Итак, (12, 21)5 – 25 = 5 . Подставляя сюда найденное ранее линейное разложение (12, 21) = 3 = 122 + 21(–1) , получим (122+21(–1))5 – 25 = 5 , или 1210 + 21(–5) – 25 = 5 , т.е. тройка целых чисел (10; –5; 5) является частным решением исходного диофантова уравнения 12x + 21y – 2z = 5 .

Теорема (о структуре общего решения линейного диофантова уравнения). Для линейного диофантова уравнения a 1 x 1 + … + a n x n = c справедливы следующие утверждения:

(1) если = (u 1 ; … ; u n ), = (v 1 ; … ; v n ) – его частные решения, то разность (u 1 – v 1 ; … ; u n – v n ) – частное решение соответствующего однородного уравнения a 1 x 1 + … + a n x n = 0 ,

(2) множество частных решений линейного диофантова однородного уравнения a 1 x 1 + … + a n x n = 0 замкнуто относительно сложения, вычитания и умножения на целые числа,

(3) если M – общее решение данного линейного диофантова уравнения, а L – общее решение соответствующего ему однородного диофантова уравнения, то для любого частного решения = (u 1 ; … ; u n ) исходного уравнения верно равенство M = + L .

Доказательство. Вычитая равенство a 1 v 1 + … + a n v n = c из равенства a 1 u 1 + … + a n u n = c , получим a 1 (u 1 – v 1 ) + … + a n (u n – v n ) = 0 , т. е. набор

(u 1 – v 1 ; … ; u n – v n ) – частное решение линейного однородного диофантова уравнения a 1 x 1 + … + a n x n = 0 . Таким образом, доказано, что

= (u 1 ; … ; u n ), = (v 1 ; … ; v n ) M L .

Это доказывает утверждение (1).

Аналогично доказывается утверждение (2):

, L z Z L z L .

Для доказательства (3) вначале заметим, что M + L . Это следует из предыдущего: M+L .

Обратно, если = (l 1 ; … ; l n ) L и = (u 1 ; … ; u n ) M , то M :

a 1 (u 1 + l 1 )+ …+a n (u n + l n ) = (a 1 u 1 + … + a n u n )+(a 1 l 1 + … + a n l n ) = c + 0 = c .

Таким образом, + L M , и в итоге M = + L .

Теорема доказана.

Доказанная теорема имеет наглядный геометрический смысл. Если рассмотреть линейное уравнение a 1 x 1 + … + a n x n = c , где х i R , то как известно из геометрии, оно определяет в пространстве R n гиперплоскость, полученную из плоскости L c однородным уравнением a 1 x 1 + … +a n x n =0 , проходящей через начало координат, сдвигом на некоторый вектор R n . Поверхность вида + L называют также линейным многообразием с направляющим пространством L и вектором сдвига . Таким образом, доказано, что общее решение М диофантова уравнения a 1 x 1 + … + a n x n = c состоит из всех точек некоторого линейного многообразия, имеющих целые координаты. При этом координаты вектора сдвига тоже целые, а множество L решений однородного диофантова уравнения a 1 x 1 + … + a n x n = 0 состоит из всех точек направляющего пространства с целыми координатами. По этой причине часто говорят, что множество решений произвольного диофантова уравнения образует линейное многообразие с вектором сдвига и направляющим пространством L .

Пример: для диофантова уравнения х – у = 1 общее решение M имеет вид (1+у; у), где у Z , его частное решение = (1; 0) , а общее решение L однородного уравнения х – у = 0 запишется в виде (у; у) , где у Z . Таким образом, можно нарисовать следующую картинку, на которой решения исходного диофантова уравнения и соответствующего однородного диофантова уравнения изображены жирными точками в линейном многообразии М и пространстве L соответственно.

2. Найти общее решение диофантова уравнения 12x + 21y – 2z = 5 .

Частное решение (10; –5; 5) этого уравнения было найдено ранее, найдём общее решение однородного уравнения 12x + 21y – 2z = 0 , эквивалентного диофантову уравнению 12 x + 21 y = 2 z .

Для разрешимости этого уравнения необходимо и достаточно выполнение условия НОД(12, 21) = 3 | 2z, т.е. 3 | z или z = 3t для некоторого целого t . Сокращая обе части на 3 , получим 4x + 7y = 2t . Частное решение (2; –1) диофантова уравнения 4x + 7y = 1 найдено в предыдущем примере. Поэтому (4t ; –2t) – частное решение уравнения 4x + 7y = 2t при любом

t Z . Общее решение соответствующего однородного уравнения

(7 u ; –4 u ) уже найдено. Таким образом, общее решение уравнения 4x + 7y = 2t имеет вид: (4t + 7 u ; –2t – 4 u ) , а общее решение однородного уравнения 12x + 21y – 2z = 0 запишется так:

(4t + 7 u ; –2t – 4 u ; 3t) .

Нетрудно убедиться, что этот результат соответствует сформулированной выше без доказательства теореме о решениях однородного диофантова уравнения а 1 х 1 + … + а n х n = 0 : если Р = , то Р и

(u ; t ) P – общее решение рассматриваемого однородного уравнения.

Итак, общее решение диофантова уравнения 12x + 21y – 2z = 5 выглядит так: (10 + 4t + 7 u ; –5 – 2t – 4 u ; 5 + 3t) .

3. На примере предыдущего уравнения проиллюстрируем другой метод решения диофантовых уравнений от многих неизвестных, который состоит в последовательном уменьшении максимального значения модулей его коэффициентов.

12x + 21y – 2z = 5 12x + (102 + 1)y – 2z = 5

12x + y – 2(z – 10y) = 5

Таким образом, общее решение рассматриваемого уравнения можно записать и так: (x; 5 – 12x + 2u ; 50 – 120x + 21u) , где x, u – произвольные целые параметры.

§ 2. Диофантово уравнение x 2 – y 2 = a

Примеры: 1. При a = 0 получаем бесконечное число решений: x = y или x = – y для любого y Z .

2. При a = 1 имеем x 2 – y 2 = 1 (x + y )(x – y ) = 1 . Таким образом, число 1 разложено в произведение двух целых множителей x + y и x – y (важно, что x , y – целые!). Поскольку у числа 1 всего два разложения в произведение целых множителей 1 = 11 и 1 = (–1)(–1) , то получаем две возможности: .

3. Для a = 2 имеем x 2 – y 2 = 2 (x + y )(x – y ) = 2. Действуя аналогично предыдущему, рассматриваем разложения

2=12=21=(–1)(–2)=(–2)(–1), составляем системы: , которые, в отличие от предыдущего примера, не имеют решений. Так что нет решений и у рассматриваемого диофантова уравнения x 2 – y 2 = 2.

4. Предыдущие рассмотрения наводят на некоторые выводы. Решения уравнения x 2 – y 2 = a находятся по разложению a = km в произведение целых чисел из системы . Эта система имеет целые решения тогда и только тогда, когда k + m и k – m чётны, т.е. когда числа k и m одной чётности (одновременно чётны или нечётны). Таким образом, диофантово уравнение x 2 – y 2 = a имеет решение тогда и только тогда, когда a допускает разложение в произведение двух целых множителей одной чётности. Остаётся только найти все такие a .

Теорема (об уравнении x 2 – y 2 = a ). (1) Уравнение x 2 – y 2 = 0 имеет бесконечное множество решений .

(2) Любое решение уравнения получается имеет вид , где a = km – разложение числа a в произведение двух целых множителей одной чётности.

(3) Уравнение x 2 – y 2 = a имеет решение тогда и только тогда, когда a 2 (mod 4).

Доказательство. (1) уже доказано.

(2) уже доказано.

(3) () Пусть вначале диофантово уравнение x 2 – y 2 = a имеет решение. Докажем, что a 2 (mod 4) . Если a = km – разложение в произведение целых чисел одной чётности, то при чётных k и m имеем k = 2 l , m = 2 n и a = km = 4 ln 0 (mod 4) . В случае же нечётных k , m их произведение a также нечётно, разность a – 2 нечётна и не делится на 4 , т.е. снова

a 2 (mod 4).

() Если теперь a 2 (mod 4) , то можно построить решение уравнения x 2 – y 2 = a . Действительно, если a нечётно, то a = 1 a – разложение в произведение целых нечётных чисел, так что – решение диофантова уравнения. Если же a чётно, то ввиду a 2 (mod 4) получаем, что 4 | a , a = 4 b = 2(2 b ) – разложение в произведение целых чётных чисел, так что – решение диофантова уравнения.

Теорема доказана.

Примеры: 1. Диофантово уравнение x 2 – y 2 = 2012 не имеет решений, т.к. 2010 = 4502 + 2 2 (mod 4).

2. Диофантово уравнение x 2 – y 2 = 2011 имеет решения, т.к.

2011 3 (mod 4). Имеем очевидные разложения

2011 = 12011 = 20111 = (–1)(–2011) = (–2011)(–1),

по каждому из которых находим решения (комбинации знаков любые). Других решений нет, т.к. число 2011 простое (?!).

§ 3. Диофантово уравнение x 2 + y 2 = a

Примеры: 1. 0 = 0 2 + 0 2 , 1 = 0 2 + 1 2 , k 2 = 0 2 + k 2 . Таким образом, очевидно, любой квадрат тривиальным образом представим в виде суммы двух квадратов.

2. 2 = 1 2 + 1 2 , 5 = 1 2 + 2 2 , 8 = 2 2 + 2 2 , 10 = 1 2 + 3 2 , 13 = 2 2 + 3 2 , 17 = 1 2 + 4 2 , 18 = 3 2 + 3 2 , 20 = 2 2 + 4 2 , …

3. Решений нет для a = 3, 6 = 23, 7, 11, 12 = 2 2 3, 14 = 27, 15 = 35, 19, 21 = 37, 22 = 211, 23, 24 = 32 3 , …

Анализ приведённых результатов способен навести на мысль, что отсутствие решений каким-то образом связано с простыми числами вида

4 n +3 , присутствующими в разложении на множители чисел, не представимых в виде сумм двух квадратов.

Теорема (о представлении натуральных чисел суммами двух квадратов). Натуральное число a представимо в виде суммы двух квадратов тогда и только тогда, когда в его каноническом разложении простые числа вида 4 n + 3 имеют чётные показатели степеней.

Доказательство. Вначале докажем, что если натуральное число a представимо в виде суммы двух квадратов, то в его каноническом разложении все простые числа вида 4 n + 3 должны иметь чётные показатели степеней. Предположим, вопреки доказываемому, что a = р 2 k +1 b = x 2 + y 2 , где

р – простое число вида 4 n +3 и b p . Представим числа х и у в виде

х = Dz , y = Dt , где D = НОД(x , y ) = р s w , p w ; z , t , s N 0 . Тогда получаем равенство р 2 k +1 b = D 2 (z 2 + t 2 ) = р 2 s w 2 (z 2 + t 2 ) , т.е. р 2( k – s )+1 b = w 2 (z 2 + t 2 ) . В левой части равенства присутствует p (нечётная степень не равна нулю), значит, на простое число p делится один из множителей в правой части. Поскольку p w , то р | (z 2 + t 2 ) , где числа z , t взаимно просты. Это противоречит следующей лемме (?!).

Лемма (о делимости суммы двух квадратов на простое число вида

4 n + 3 ). Если простое число р = 4 n +3 делит сумму квадратов двух натуральных чисел, то оно делит каждое из этих чисел.

Доказательство. От противного. Пусть x 2 + y 2 0(mod p ) , но x 0(mod p ) или y 0 (mod p ) . Поскольку x и y симметричны, их можно менять местами, так что можно предполагать, что x p .

Лемма (об обратимости по модулю p ). Для любого целого числа x , не делящегося на простое число p , существует обратный элемент по модулю p – такое целое число 1 u < p , что xu 1 (mod p ).

Доказательство. Число x взаимно простое с p , поэтому можно записать линейное разложение НОД(x , p ) = 1 = xu + pv (u , v Z ) . Ясно, что xu 1(modp ) , т.е. u – обратный элемент к x по модулю p . Если u не удовлетворяет ограничению 1 u < p , то поделив u с остатком на p , получим остаток r u (mod p ) , для которого xr xu 1 (mod p ) и 0 r < p .

Лемма об обратимости по модулю p доказана.

Умножая сравнение x 2 + y 2 0 (mod p ) на квадрат u 2 обратного элемента к x по модулю p , получим 0 = 0u 2 x 2 u 2 + y 2 u 2 = (xu) 2 + (yu) 2 1 + t 2 (mod p).

Таким образом, для t = yu выполнено сравнение t 2 –1 (mod p ) , которое и приведём к противоречию. Ясно, что t p : иначе t 0 (mod p ) и 0 t 2 –1 (mod p ) , что невозможно. По теореме Ферма имеем t p –1 1 (mod p ), что вместе с t 2 –1 (mod p ) и p = 4 n + 3 приводит к противоречию:

1 t p–1 = t 4n+3–1 = t 2(2n+1) = (t 2 ) 2n+1 (–1) 2n+1 = –1 (mod p).

Полученное противоречие показывает, что допущение о x 0 (mod p ) было не верным.

Лемма о делимости суммы двух квадратов на простое число 4 n +3 доказана.

Таким образом, доказано, что число, в каноническое разложение которого входит простое число p = 4 n + 3 в нечётной степени, не представимо в виде суммы двух квадратов.

Докажем теперь, что любое число, в каноническом разложении которого простые числа p = 4 n + 3 участвуют только в чётных степенях, представимо в виде суммы двух квадратов.

Идея доказательства основана на следующем тождестве:

(а 2 + b 2 )(c 2 + d 2 ) = (ac – bd) 2 + (ad + bc) 2 ,

которое можно получить из известного свойства модуля комплексных чисел – модуль произведения равен произведению модулей. Действительно,

| z || t | = | zt | | a + bi || c + di | = |(a + bi )(c + di )|

|a + bi| 2 |c + di| 2 = |(ac – bd) + (ad + bc)i| 2

(а 2 + b 2 )(c 2 + d 2 ) = (ac – bd) 2 + (ad + bc) 2 .

Из этого тождества следует, что если два числа u, v представимы в виде суммы двух квадратов: u = x 2 + y 2 , v = z 2 + t 2 , то и их произведение uv представимо в виде суммы двух квадратов: uv = (xz – yt ) 2 + (xt + yz ) 2 .

Любое натуральное число a > 1 можно записать в виде a = р 1 … р k m 2 , где р i – попарно различные простые числа, m N . Для этого достаточно найти каноническое разложение , записать каждую степень вида r в виде квадрата (r ) 2 при чётном = 2, или в виде r = r (r ) 2 при нечётном = 2 + 1 , а затем сгруппировать отдельно квадраты и оставшиеся одиночные простые числа. Например,

29250 = 23 2 5 3 13 = 2513(35) 2 , m = 15.

Число m 2 обладает тривиальным представлением в виде суммы двух квадратов: m 2 = 0 2 + m 2 . Если доказать представимость в виде суммы двух квадратов всех простых чисел р i (1 i k ) , то используя тождество, будет получено и представление числа a. По условию, среди чисел р 1 , … , р k могут встретиться только 2 = 1 2 + 1 2 и простые числа вида 4 n + 1 . Таким образом, осталось получить представление в виде суммы двух квадратов простого числа р = 4т + 1 . Это утверждение выделим в отдельную теорему (см. ниже)

Например, для a = 29250 = 2513(15) 2 последовательно получаем:

2 = 1 2 + 1 2 , 5 = 1 2 + 2 2 , 13 = 2 2 + 3 2 ,

25 = (11 – 12) 2 + (12 + 11) 2 = 1 2 + 3 2 ,

2513 = (12 – 33) 2 + (13 + 32) 2 = 7 2 + 9 2 ,

29250 = 2513(15) 2 = (715) 2 + (915) 2 = 105 2 + 135 2 .

Теорема доказана.

§ 4. Уравнение х+ х + 1 = 3у

Займемся теперь уравнением х+x+1=Зу. Оно уже имеет свою историю. В 1950 г. Р. Облат высказал предположение, что, кроме решения

x =у=1 . оно не имеет иных решений в натуральных числах х, у , где х есть нечетное число. В том же году Т. Нагель указал решение x = 313, у =181. Метод, аналогичный изложенному выше для уравнения х+х-2у=0 , позволит нам определить все решения уравнения x +х+1=3у (1)

в натуральных числах x , у. Предположим, что (х, у) есть решение уравнения (1) в натуральных числах, причем х > 1 . Можно легко убедиться, что уравнение(18) не имеет решений в натуральных числах x , у , где х = 2, 3. 4, 5, 6, 7, 8, 9; поэтому должно быть х10.

Покажем, что 12у<7 x +3, 7у>4 x + 2. 4у> 2 x +1 . (2)

Если бы было 12y > 7x+3 , мы имели бы 144у > 49 x +42 x +9 . а так как, в виду (18), 144у= 48 x + 48 x + 48 , то было бы х < 6 x +3 9, откуда

Доказательство

С вами был Петр,
спасибо за внимание.

Наиболее изучены диофантовы уравнения первой и второй степени. Рассмотрим сначала уравнения первой степени. Так как решение линейного уравнения с одним неизвестным не представляет интереса, то обратимся к уравнениям с двумя неизвестными.Мы рассмотрим два метода решения этих уравнений.

Первый способ решения таких уравнений- алгоритм Евклида. Можно найти наибольший делитель натуральных чисел a и b, не раскладывая эти числа на простые множители, применяя процесс деления с остатком. Для этого надо разделить большее из этих чисел на меньшее, потом меньшее из чисел на остаток при первом делении, затем остаток при первом делении на остаток при втором делении и вести этот прицесс до тех пор, пока не произойдёт деление без остатка. Последний отличный от нуля остаток и есть искомый НОД(a,b). Чтобы доказать это утверждение, представим описанный процесс в виде следующей цепочки равенств:если a>b ,то

Здесь r1,….,rn-положительные остатки, убывающие с возрастанием номера. Из первого равенства следует,что общий делитель чисел a и b делит r1 и общий дилитель b и r1 делит а,поэтому НОД (a,b) = НОД (r1 ,r2)=….= НОД (rn-1, rn) = НОД (rn,0)= rn.Обратимся снова к системе(1).Из первого равенства, выразив остаток r1 чирез а и b ,получим r1=а- bq0. Подставляя его во второе равенство,найдём r2=b(1+q0q1)-aq1. Продолжая этот процесс дальше,мы сможем выразить все остатки через а и b, в том числе и последний rn=Аа+Вb. В результате нами доказано предложение:если d-наибольший общий делитель натуральных чисел а и b,то найдутся такие целые числа А и В,что d= Аа+Вb. Заметим,что коэффициенты А и В имеют разные знаки; если НОД(a,b)=1,то Аа+Вb=1. Как найти числа А и В видно из алгоритма Евклида.

Перейдём теперь к решению линейного уравнения с двумя неизвестными. Оно имеет вид:

Возможны два случая: либо c делится на d= НОД(a,b), либо нет. В первом случае можно разделить обе части на d и свести задачу к решению в целых числах уравнения a1x+b1y=c1, коэффициенты которого а1=а/d и b1=b/d взаимно просты. Во втором случае уравнение не имеет целочисленных решений: при любых целых x и y число аx+by делится на d и поэтому не может равнятся числу с,которое на d не делится. Итак, мы можем ограничиться случаем, когда в уравнении (2) коэффициенты взаимно просты. На основании предыдущего предложения найдутся такие целые числа x0 и y0,что ax0+by0=1, откуда пара (сx0,cy0) удовлетворяет уравнению (2) Вместе с ней уравнению (2) удовлетворяет бесконечное множество пар (x,y) целых чисел, которые можно найти по формулам

x=cx0+bt,y=cy0-at. (3)

Здесь t-любое целое число. Нетрудно показать,что других целочисленных решений нет уравнение ax+by=c не имеет. Решение, записанное в виде (3), называется общим решением уравнеия (2). Подставив вместо t конкретное целое число, получим его частное решение. Найдём, например, целочисленные решения уже встречавшегося нам уравнения 2x+5y=17. Применив к числам 2 и 5 алгоритм Евклида, получим 2*3-5=1. Значит пара cx0=3*17,cy0=-1*17 удовлетворяет уравнению 2x+5y=17. Поэтому общее решение исходного уравнения таково x=51+5t, y=-17-2t,где t принимает любые целые значения. Очевидно, неотрицательные решения отвечают тем t , для которых выполняются неравенства

Отсюда найдем -51 ?t? -17 . Этим неравенствам удовлетворяют числа -10, -9. 52

Соответствующие частные решения запишутся в виде пар (1,3), (6,1).

Применим этот же метод к решению одной из древних китайских задач о птицах.

Задача: Сколько можно купить на 100 монет петухов, кур и цыплят, если всего надо купить 100 птиц, причем петух стоит 5 монет, курица - 4, а 4 цыпленка - 1 монету?

Для решения этой задачи обозначим искомое число петухов через х, кур - через y, а цыплят через 4z (из условия видно, что число цыплят должно делится на 4). Составим систему уравнений:

которую надо решить в целых неотрицательных числах. Умножив первое уравнение системы на 4, а второе -- на (-- 1) и сложив результаты, придем к уравнению -- х+15z= 300 с целочисленными решениями х= -- 300+ 15t, z = t. Подставляя эти значения в первое уравнение, получим y = 400 -- 19t. Значит, целочисленные решения системы имеют вид х= --300+15t, y = 400--19t, z = t. Из условия задачи вытекает, что

откуда 20?t?21 1/19, т.е. t = 20 или t = 21. Итак, на 100 монет можно купить 20 кур и 80 цыплят, или 15 петухов, 1 курицу и 84 цыпленка

Второй метод решения диофантовых уравнений первой степени по своей сути не слишком отличается от рассмотренного в предыдущем пункте, но он связан с ещё одим интересным математическим понятием. Речь идёт о непрерывных или цепных дробях. Чтобы определить их вновь обратимся к алгоритму Евклида. Из первого равенства системы (1) вытекает, что дробь а/b можно записать в виде суммы целой части и правильной дроби: a/b=q0+r1/b . Но r1/b=1/b, и на основании второго равенства той же системы имем b/r1=q1+r2/r1. Значит, a/b=q0+1/q1+r2/r1. Далее получим a/b=q0+1/q1+1/q2+r3/r2. Продолжим этот процесс до тех пор, пока не придём к знаменателю qn. В результате мы представим обыкновенную дробь a/b в следующем виде: a/b=q0+1/q1+1/q2+1/…1/qn. Эйлер назвал дроби такого вида непрерывными. Приблизительно в то же время в Германии появился другой термин- цепная дробь. Так за этими дробями и сохранились оба названия. В качестве примера представим дробь 40/3t в виде цепной: 40/3t=1+9/3t=1/3t/9=1+1/3+4/9=1+1/3+1/9/4=1+1/3+1/2+1/4 .

Цепные дроби обладают следующим важным свойством: если действительное число а записать в виде непрерывной дроби, то подходящая дробь Pk/Qk даёт наилучщее приближение числа a среди всех дробей, знаменатели которых не превосходят Qk . Именно в процессе поиска наилучшего приблежения значений квадратных корней итальянский математик Пиетро Антонио Катальди (1552-1626) пришёл в 1623году к цепным дробям, с чего и началось их изучение. В заключение вернёмся к цепным дробям и отметим их преимущество и недостаток по сравнению, например, с десятичными. Удобство заключается в том, что их свойства не связаны ни с какой системой исчисления. По этой причине цепные дроби эффективно используются в теоретических исследованиях. Но широкого практического применения они не получили, так как для них нет удобных правил выполнения арифметических действий, которые имеются для десятичных дробей.

Рассмотрим Диофантовы уравнения и решим их.

1 Решить в целых числах уравнение 3x+5y=7.

x=7-5y/3=6-3y-2y+1/3=2-y+1-2y/3,

y=1-3k/2=1-2k-k/2=-k+1-k/2,

y=1-3(1-2t)/2=-1+3t,

x=7-5(-1+3t)/3=4-5t

(t-любое число).

2 Решить в целых числах уравнение 6xІ+5yІ=74.

6xІ-24=50-5yІ, или 6(xІ-4)=5(10-yІ), откуда xІ-4=5u,т.е. 4+5u?0, откуда u?-4/5.

Аналогично:

10-yІ=6u, т.е. 10-6u?0, u?5/3.

Целое число u удовлетворяет неравенству

4/5?u?5/3, значит. u=0 и u=1.

При u=0, получим 10=yІ, где y-не целое, что неверно. Пусть u=1, тогда xІ=9, yІ=4.

Ответ: {x1=3, {x2=3, {x3=-3, {x4=-3,

{y1=2, {y2=-2, {y3=2, {y4=-2 .

3 Решить в целых числах уравнение xі+yі-3xy=2.

Если x и y оба нечётны или одно из них нечётно, то левая часть уравнения есть нечётное число, а правая-чётное. Если же x=2m и y=2n, то 8mі+8nі-12mn=2, т.е. 2(2mі+2nі-3mn)=1, что невозможно ни при каких целых m и n.

4 Доказать, что уравнение 2xІ+5yІ=7 не имеет решений в целых числах.

Доказательство.

Из уравнения видно, что y должен быть нечётным числом. Положив y=2z+1, получим 2xІ-20zІ-20z-5=7, или xІ-10zІ-10z=6, откуда следует что x есть чётное число. Положим x=2u. Тогда 2uІ-5z(z=1)=3, что невозможно, так как z(z+1) есть чётное число.

5 Доказать, что при любом целом положительном значении а уравнение xІ+yІ=аі разрешимо в целых числах.

Доказательство.

Положим x+y=аІ, x-y=а, откуда x=a(a+1)/2 и y=a(a-1)/2. Поскольку при любом целом значении а в числителе каждой из данных дробей стоит произведение чётного и нечётного чисел, определённые таким образом x и y представляют сорбой целые числа и удовлетворяют исходному уравнению.

6 Решите в целых числах уравнение (x+1)(xІ+10=yі.

Непосредственно видим, что пары чисел (0;1) и (-1;0) являются решениями уравнения. Других решений нет, так как

xі<(x+1)(xІ+1)<(x+1)(x+1)І=(x+1) і, то (x+1)(xІ+1)?yі

ни для какого целого y (распологающегося между кубами последовательных целых чисел).