Методы решения диофантовых уравнений. Как решить линейное диофантово уравнение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чтобы решить линейное диофантово уравнение, нужно найти значения переменных «x» и «y», которые являются целыми числами. Целочисленное решение сложнее обычного и требует определенного набора действий. Сначала необходимо вычислить наибольший общий делитель (НОД) коэффициентов, а затем найти решение. Если вы нашли одно целочисленное решение линейного уравнения, можно применить простой шаблон, чтобы найти бесконечное множество других решений.

Шаги

Часть 1

Как записать уравнение

1. Запишите уравнение в стандартной форме. Линейное уравнение - это уравнение, в котором показатели степени переменных не превышают 1. Чтобы решить такое линейное уравнение, сначала запишите его в стандартной форме. Стандартная форма линейного уравнения выглядит так: A x + B y = C {\displaystyle Ax+By=C} , где A , B {\displaystyle A,B} и C {\displaystyle C} - целые числа.

   • Если уравнение дано в другой форме, приведите его к стандартной форме с помощью основных алгебраических действий. Например, дано уравнение 23 x + 4 y − 7 x = − 3 y + 15 {\displaystyle 23x+4y-7x=-3y+15} . Приведите подобные члены и запишите уравнение так: 16 x + 7 y = 15 {\displaystyle 16x+7y=15} .

2. Упростите уравнение (если можно). Когда вы запишете уравнение в стандартной форме, посмотрите на коэффициенты A , B {\displaystyle A,B} и C {\displaystyle C} . Если у этих коэффициентов есть НОД, разделите на него все три коэффициента. Решение такого упрощенного уравнения также будет решением исходного уравнения.

   • Например, если все три коэффициента четные, разделите их как минимум на 2. Например:
     • 42 x + 36 y = 48 {\displaystyle 42x+36y=48} (все члены делятся на 2)
     • 21 x + 18 y = 24 {\displaystyle 21x+18y=24} (теперь все члены делятся на 3)
     • 7 x + 6 y = 8 {\displaystyle 7x+6y=8} (это уравнение больше нельзя упростить)

3. Проверьте, можно ли решить уравнение. В некоторых случаях можно сразу заявить, что уравнение не имеет решений. Если коэффициент «С» не делится на НОД коэффициентов «А» и «В», у уравнения нет решений.

   • Например, если оба коэффициента A {\displaystyle A} и B {\displaystyle B} четные, то и коэффициент C {\displaystyle C} должен быть четным. Но если C {\displaystyle C} нечетный, то решения нет.
     • У уравнения 2 x + 4 y = 21 {\displaystyle 2x+4y=21} нет целочисленных решений.
     • У уравнения 5 x + 10 y = 17 {\displaystyle 5x+10y=17} нет целочисленных решений, так как левая часть уравнения делится на 5, а правая - нет.

4. Проанализируйте полученный результат. Когда вы найдете НОД коэффициентов A {\displaystyle A} и B {\displaystyle B} , сравните его с коэффициентом C {\displaystyle C} исходного уравнения. Если C {\displaystyle C} делится на НОД A {\displaystyle A} и B {\displaystyle B} , уравнение имеет целочисленное решение; в противном случае у уравнения нет решений.

   • Например, уравнение можно решить, потому что 3 делится на 1 (НОД=1).
   • Например, предположим, что НОД=5. 3 не делится на 5 нацело, поэтому такое уравнение не имеет целочисленных решений.
   • Как показано ниже, если уравнение имеет одно целочисленное решение, оно также имеет бесконечное множество других целочисленных решений.

   Часть 3

   Как найти решение с помощью алгоритма Евклида

   1. Пронумеруйте шаги вычисления НОД. Чтобы найти решение линейного уравнения, нужно использовать алгоритм Евклида в качестве основы процесса подстановки и упрощения.

      • Начните с нумерации шагов вычисления НОД. Процесс вычисления выглядит так:
        • Шаг 1: 87 = (1 ∗ 64) + 23 {\displaystyle {\text{Шаг 1}}:87=(1*64)+23}
        • Шаг 2: 64 = (2 ∗ 23) + 18 {\displaystyle {\text{Шаг 2}}:64=(2*23)+18}
        • Шаг 3: 23 = (1 ∗ 18) + 5 {\displaystyle {\text{Шаг 3}}:23=(1*18)+5}
        • Шаг 4: 18 = (3 ∗ 5) + 3 {\displaystyle {\text{Шаг 4}}:18=(3*5)+3}
        • Шаг 5: 5 = (1 ∗ 3) + 2 {\displaystyle {\text{Шаг 5}}:5=(1*3)+2}
        • Шаг 6: 3 = (1 ∗ 2) + 1 {\displaystyle {\text{Шаг 6}}:3=(1*2)+1}
        • Шаг 7: 2 = (2 ∗ 1) + 0 {\displaystyle {\text{Шаг 7}}:2=(2*1)+0}

   2. Обратите внимание на последний шаг, где есть остаток. Перепишите уравнение этого шага так, чтобы изолировать остаток.

      • В нашем примере последний шаг с остатком - это шаг 6. Остаток равен 1. Перепишите уравнение шага 6 следующим образом:
        • 1 = 3 − (1 ∗ 2) {\displaystyle 1=3-(1*2)}

   3. Изолируйте остаток предыдущего шага. Этот процесс представляет собой пошаговое «перемещение вверх». Каждый раз вы будете изолировать остаток в уравнении предыдущего шага.

      • Изолируйте остаток уравнения шага 5:
        • 2 = 5 − (1 ∗ 3) {\displaystyle 2=5-(1*3)} или 2 = 5 − 3 {\displaystyle 2=5-3}

   4. Сделайте замену и упростите. Обратите внимание, что уравнение шага 6 содержит число 2, а в уравнении шага 5 число 2 изолировано. Поэтому вместо «2» в уравнении шага 6 подставьте выражение шага 5:

      • 1 = 3 − 2 {\displaystyle 1=3-2} (уравнение шага 6)
      • 1 = 3 − (5 − 3) {\displaystyle 1=3-(5-3)} (вместо 2 подставили выражение)
      • 1 = 3 − 5 + 3 {\displaystyle 1=3-5+3} (раскрыли скобки)
      • 1 = 2 (3) − 5 {\displaystyle 1=2(3)-5} (упростили)

   5. Повторите процесс подстановки и упрощения. Повторите описанный процесс, перемещаясь по алгоритму Евклида в обратном порядке. Каждый раз вы будете переписывать уравнение предыдущего шага и подставлять его в последнее полученное уравнение.

      • Последним рассмотренным шагом был шаг 5. Поэтому перейдите к шагу 4 и изолируйте остаток в уравнении этого шага:
        • 3 = 18 − (3 ∗ 5) {\displaystyle 3=18-(3*5)}
      • Подставьте это выражение вместо «3» в последнее уравнение:
        • 1 = 2 (18 − 3 ∗ 5) − 5 {\displaystyle 1=2(18-3*5)-5}
        • 1 = 2 (18) − 6 (5) − 5 {\displaystyle 1=2(18)-6(5)-5}

   6. Продолжите процесс подстановки и упрощения. Этот процесс будет повторяться до тех пор, пока вы не достигнете первоначального шага алгоритма Евклида. Цель процесса - записать уравнение с коэффициентами 87 и 64 исходного уравнения, которое нужно решить. В нашем примере:

      • 1 = 2 (18) − 7 (5) {\displaystyle 1=2(18)-7(5)}
      • 1 = 2 (18) − 7 (23 − 18) {\displaystyle 1=2(18)-7(23-18)} (подставили выражение из шага 3)
        • 1 = 2 (18) − 7 (23) + 7 (18) {\displaystyle 1=2(18)-7(23)+7(18)}
        • 1 = 9 (18) − 7 (23) {\displaystyle 1=9(18)-7(23)}
      • 1 = 9 (64 − 2 ∗ 23) − 7 (23) {\displaystyle 1=9(64-2*23)-7(23)} (подставили выражение из шага 2)
        • 1 = 9 (64) − 18 (23) − 7 (23) {\displaystyle 1=9(64)-18(23)-7(23)}
        • 1 = 9 (64) − 25 (23) {\displaystyle 1=9(64)-25(23)}
      • 1 = 9 (64) − 25 (87 − 64) {\displaystyle 1=9(64)-25(87-64)} (подставили выражение из шага 1)
        • 1 = 9 (64) − 25 (87) + 25 (64) {\displaystyle 1=9(64)-25(87)+25(64)}
        • 1 = 34 (64) − 25 (87) {\displaystyle 1=34(64)-25(87)}

   7. Перепишите полученное уравнение в соответствии с исходными коэффициентами. Когда вы вернетесь к первому шагу алгоритма Евклида, вы увидите, что полученное уравнение содержит два коэффициента исходного уравнения. Перепишите уравнение так, чтобы порядок его членов соответствовал коэффициентам исходного уравнения.

      • В нашем примере исходное уравнение 87 x − 64 y = 3 {\displaystyle 87x-64y=3} . Поэтому перепишите полученное уравнение так, чтобы коэффициенты привести в соответствие. Обратите особое внимание на коэффициент «64». В исходном уравнении этот коэффициент отрицательный, а в алгоритме Евклида - положительный. Поэтому множитель 34 нужно сделать отрицательным. Окончательное уравнение запишется так:
        • 87 (− 25) − 64 (− 34) = 1 {\displaystyle 87(-25)-64(-34)=1}

Пункт 5. Линейные диофантовы уравнения с двумя неизвестными.

Обычно, произвольное уравнение (но, как правило, все-таки с целыми коэффициентами) получает титул "диофантово", если хотят подчеркнуть, что его требуется решить в целых числах, т.е. найти все его решения, являющиеся целыми. Имя Диофанта - выдающегося Александрийского математика - появляется здесь не случайно. Диофант интересовался решением уравнений в целых числах еще в третьем веке нашей эры и, надо сказать, делал это весьма успешно.

Отступление про Диофанта и его исторический след.

Третий и последний период античного общества - период господства Рима. Рим завоевал Сиракузы в 212 году, Карфаген - в 146 году, Грецию - в 146, Месопотамию - в 46, Египет - в 30 году до нашей эры. Огромные территории оказались на положении колоний, но римляне не трогали их культуры и экономического устройства пока те исправно платили налоги и поборы. Установленный римлянами на столетия мир, в отличие от всех последующих великих миров и рейхов, принес всей завоеванной территории самый длинный период безвоенного существования, торговли и культурного обмена.

Александрия оказалась центром античной математики. Велись оригинальные исследования, хотя компилирование, пересказ и комментирование становились и стали основным видом научной деятельности. Александрийские ученые, если угодно, приводили науку в порядок, собирая разрозненные результаты в единое целое, и многие труды античных математиков и астрономов дошли до нас только благодаря их деятельности. Греческая наука с ее неуклюжим геометрическим способом выражения при систематическом отказе от алгебраических обозначений угасала, алгебру и вычисления (прикладную математику) александрийцы почерпнули с востока, из Вавилона, из Египта.

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

Книга Диофанта неожиданно оказала еще и огромное косвенное влияние на развитие математической науки последних трех столетий. Дело в том, что юрист из Тулузы Пьер Ферма (1601 - 1665), изучая "Арифметику" Диофанта, сделал на полях этой книги знаменитую пометку: "Я нашел воистину удивительное доказательство того, что уравнение x n + y n = z n при n > 2, не имеет решений в целых числах, однако поля этой книги слишком малы, чтобы здесь его уместить". Это одно из самых бесполезных математических утверждений получило название "Великой теоремы Ферма" и, почему-то, вызвало настоящий ажиотаж среди математиков и любителей (особенно после назначения в 1908 году за его доказательство премии в 100 000 немецких марок). Попытки добить эту бесполезную теорему породили целые разделы современной алгебры, алгебраической теории чисел, теории функций комплексного переменного и алгебраической геометрии, практическая польза от которых уже не подлежит никакому сомнению. Сама теорема, кажется, благополучно доказана в 1995 году; Пьер Ферма, конечно, погорячился на полях "Арифметики", ибо он физически не мог придумать подобного доказательства, требующего колоссальной совокупности математических знаний. Элементарного доказательства великой теоремы Ферма пока никто из жителей нашей планеты найти не смог, хотя над его поиском бились лучшие умы последних трех столетий. Однако, до сих пор тысячи психически нездоровых любителей-"ферматистов" в жажде славы и денег бомбят своими письмами академические институты и университеты и почти ежегодно один из сотрудников кафедры алгебры и дискретной математики Уральского госуниверситета, где я работаю, вынужден вести с таким психом дипломатическую переписку на заранее заготовленном бланке:

"Уважаемый.............................! В Вашем доказательстве на странице №......, в строке №........, содержится ошибка..............................................................".

Пусть требуется решить линейное диофантово уравнение:

ax + by = c ,

где 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 a

y .

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

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

Случай 2. Пусть теперь c № 0. Этот случай закрывается следующей теоремой.

Теорема. Пусть (a , b ) = 1, { x 0 , y 0 } - частное решение диофантова уравнения ax + by = c . Тогда его общее решение задается формулами:

м н о

x = x 0 - bt y = y 0 + at .

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

Доказательство. То, что правые части указанных в формулировке теоремы равенств действительно являются решениями, проверяется их непосредственной подстановкой в исходное уравнение. Покажем, что любое решение уравнения ax + by = c имеет именно такой вид, какой указан в формулировке теоремы. Пусть { x * , y *} - какое-нибудь решение уравнения 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 }, ради которого и затеяна вся возня этого пункта и которое, как теперь выясняется, нам так нужно?". Ответ до глупости прост. Мы договорились, что (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 копейки. Как это сделать? Решаем уравнение:

7 x + 12 y = 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, поэтому дубасить кассира необязательно.

Диофант Александрийский - древнегреческий математик, который жил еще в III веке н. э. О нем говорят как об «отце алгебры». Это автор «Арифметики» - книги, которая посвящена нахождению положительных рациональных решений неопределённых уравнений. Диофант - первый греческий математик, который рассматривал дроби наравне с другими числами. Он первым среди античных учёных предложил развитую математическую символику, которая позволяла формулировать полученные им результаты в достаточно компактном виде. В честь Диофанта назван кратер на видимой стороне Луны.

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

Допустим, нам необходимо решить в целых числах \[(x,y)\] уравнение:

Чтобы решить данного вида задание применим алгоритм Евклида, которое говорит, что для любых двух натуральных чисел \ таких, что \[Н.О.Д.(а,b) = 1\] существуют целые числа \ такие, что \[ах + bу = 1.\]

Этапы решения:

1. Найдем решение уравнения \ применив алгоритм Евклида.

2. Найдем частное решение уравнения (1) по правилу 2.

3. Запишем общее решение данного уравнения (1).

1. Найдем представление: \ Для решения применим алгоритм Евклида.

Из этого равенства выразим

\[ 1 = 3 - 2^1=3-(5-3)^1=3-5^1+3\cdot 1=3^2-5\cdot1=(8-5^1)^2 -5^1=8^2-5\cdot2-5^1=5^x(-3)-8\cdot(-2) \]

Итак, \

2. Частное решение уравнения \[(1): x_о = 19m; y_о =19n.\]

Отсюда получим: \[ x_о =19^x(-3)=57; у_о =19^x(-2)=-38 \]

Пара (-57; -38) - частное решение (1).

3.Общее решение уравнения (1):

\[\left\{\begin{matrix} x=-57+8n\\ y=-3+n, n \in Z \end{matrix}\right.\]

Где взять решение диофантова уравнения?

Решить уравнение вы можете на нашем сайте https://сайт. Бесплатный онлайн решатель позволит решить уравнение онлайн любой сложности за считанные секунды. Все, что вам необходимо сделать - это просто ввести свои данные в решателе. Так же вы можете посмотреть видео инструкцию и узнать, как решить уравнение на нашем сайте. А если у вас остались вопросы, то вы можете задать их в нашей групе Вконтакте http://vk.com/pocketteacher. Вступайте в нашу группу, мы всегда рады помочь вам.