5610.Учебная работа .Тема:Диофантовы уравнения первой степени с двумя неизвестными

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...

Тема:Диофантовы уравнения первой степени с двумя неизвестными»,»

Содержание

диофантово уравнение неизвестный

Введение

1. Диофант и история диофантовых уравнений

. Сравнения первой степени с одним неизвестным и методы их решения

.1 Основные понятия

.2 Сравнения и их свойства

.3 Сравнения первой степени с одним неизвестным

.4 Методы решения линейных сравнений

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

.1 О числе решений ЛДУ

.2 Нахождение решений произвольного ЛДУ

.3 Нахождение решений для некоторых частных случаев ЛДУ

Практическая часть

Заключение

Литература

Введение

В наши дни каждый, кто занимался математикой как профессионал или как любитель, слышал о диофантовых уравнениях и даже о диофантовом анализе. За последние три десятка лет эта область стала «модной» благодаря своей близости к алгебраической геометрии властительнице дум современных математиков. Между тем, о том, кто дал имя неопределенному анализу, о самом Диофанте, одном из наиболее интересных ученых античности, почти ничего не написано. О его работах даже историки науки имеют самое превратное представление. Большинство из них считает, что Диофант занимался решением отдельных задач, равносильных неопределенным уравнениям, применяя для этого хитроумные, но частные методы.

Между тем простой разбор задач Диофанта показывает, что он не только поставил проблему решения неопределенных уравнений в рациональных числах, но и дал некоторые общие методы их решения. Надо при этом иметь в виду, что в античной математике общие методы никогда не излагались «в чистом виде», отдельно от решаемых задач.

Линейным диофантовым уравнением называется уравнение с несколькими неизвестными вида а1х1 + … + аnхn = с, где (известные) коэффициенты а1,…, аn и с целые числа, а неизвестные х1,…,xn также являются целыми числами. К решению подобных уравнений сводятся разнообразные текстовые задачи, в которых неизвестные величины выражают количество предметов того или иного рода и потому являются натуральными (или неотрицательными целыми) числами.

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

Конкретные задачи такого рода были решены еще в Древнем Вавилоне около 4 тысяч лет тому назад. Древнегреческий мыслитель Диофант, который жил около 2 тысяч лет тому назад, в своей книге «Арифметика» решил большое число таких и более сложных уравнений в целых числах и в сущности описал общие методы их решения.

Следует отметить, что каждая конкретная задача в целых числах может решаться с помощью разных методов.

Цель исследования: изучение методов решения линейных диофантовых уравнений с двумя неизвестными.

Задачи исследования:

изложить историческую справку о возникновении и развитии теории неопределенных уравнений;

рассмотреть числовые сравнения и их свойства; линейные сравнения с одним неизвестным и методы их решения;

изложить методы решения диофантовых уравнений первой степени с n неизвестными, n ? 2;

выполнить упражнения, относящиеся к теме исследования.

1. Диофант и история диофантовых уравнений

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

Нижняя грань этого промежутка определяется без труда. В своей книге «О многоугольных числах» Диофант неоднократно упоминает математика Гипсикла Александрийского, который жил в середине II в. до н. э. С другой стороны, в комментариях Теона Александрийского к «Альмагесту» знаменитого астронома Птолемея помещен отрывок из сочинения Диофанта. Теон жил в середине IV в. н. э. Этим определяется верхняя грань этого промежутка. Итак, 500 лет!

На могиле Диофанта есть стихотворение задача, решая которую нетрудно подсчитать, что Диофант прожил 84 года [2].

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

Отнят он был у отца ранней могилой своей. Дважды два года родитель оплакивал тяжкое горе, Тут и увидел предел жизни печальной своей».

Существуют различные интерпретации данной задачи. Приведем еще один перевод стихотворения о жизни Диофанта.

«Путник. Здесь прах погребен Диофанта.

И числа поведать могут, о чудо, сколь долог был век его жизни.

Часть шестую его представляло прекрасное детство.

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

Седьмую в бездетном браке провел Диофант.

Прошло пятилетие; он был осчастливлен рождением первенца сына.

Коему рок половину лишь жизни прекрасной и светлой дал на земле по сравненью с отцом.

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

Скажи, сколько лет жизни достигнув, смерть воспринял Диофант».

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

Пусть х количество лет, прожитых Диофантом, тогда х/6 лет он прожил ребенком, а х/12 лет он прожил до появления пуха на его подбородке, х/7 лет Диофант провел в бездетном браке, спустя 5 лет у него родился сын, который прожил х/2 лет. Отец пережил сына на 4 года. Составим и решим уравнение: х = х/6+х/12+х/7+5+х/2+4 [16]. Получаем: Диофант женился в 33 года, стал отцом на 38ом году, потерял сына на 80ом году и умер в 84года.

Однако для этого вовсе не нужно владеть искусством Диофанта! Достаточно уметь решать уравнение 1й степени с одним неизвестным, а это умели делать египетские писцы ещё за 2 тысячи лет до н. э.

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

При Музейоне была построена знаменитая библиотека, которая в лучшие свои дни насчитывала более 700 000 рукописей. Неудивительно, что ученые и жаждущие знаний юноши со всего мира устремились в Александрию, чтобы послушать знаменитых философов, поучиться астрономии и математике, иметь возможность в прохладных залах библиотеки углубиться в изучение уникальных рукописей. И вот именно здесь жил и трудился Диофант Александрийский [1].

Музейон пережил династию Птолемеев. В первые века до н.э. он пришёл во временный упадок, связанный с общим упадком дома Птолемеев в связи с римскими завоеваниями, но затем в первые века н. э. он снова возродился, поддерживаемый уже римскими императорами. Александрия продолжала оставаться научным центром мира. И если в III II веках до н. э. Музейон блистал именами Евклида, Аполлония, Эратосфена, Гиппарха, то в I III веках н. э. здесь работали такие учёные как Герон, Птолемей и Диофант.

Наиболее интересным представляется творчество Диофанта. О его творчестве говорили: «Труды его подобны сверкающему огню среди полной непроницаемой тьмы». До нас дошло 6 книг Диофанта из 13, которые были объединены в «Арифметику». Стиль и содержание этих книг резко отличаются от классических античных сочинений по теории чисел и алгебре, образцы которых мы знаем по «Началам» Евклида, леммам из сочинений Архимеда и Аполлония. «Арифметика», несомненно, явилась результатом многочисленных исследований, многие из которых, остались нам неизвестны.

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

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

Неопределенные уравнения 1й степени начали рассматриваться индусскими математиками позднее, примерно с V века. Некоторые такие уравнения с двумя и тремя неизвестными появились в связи с проблемами, возникшими в астрономии, например, при рассмотрении вопросов, связанных с определением периодического повторения небесных явлений [2].

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

В 1624г. в публикуется книга французского математика Баше де Мезирьяка «Probl?mes plaisans et delectables que se font par les nombres». Баше де Мезирьяк для решения уравнения фактически применяет процесс, сводящийся к последовательному вычислению неполных частных и рассмотрению подходящих дробей.

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

Цепные дроби к решению таких уравнений были применены Лагранжем, который, однако, замечает, что фактически это тот же способ, который был дан Баше де Мезирьяком и другими математиками, рассматривавшими неопределенные уравнения до него. Неопределенные уравнения 1й степени стали записываться и решаться в форме сравнения значительно позже, начиная с Гаусса [4].

В августе 1900г. в Париже состоялся II Международный конгресс математиков. 8 августа Д.Гильберт прочитал на нем доклад «»Математические проблемы»». Среди 23 проблем, решение которых (по мнению Д.Гильберта) совершенно необходимо было получить в наступающем XX в., десятую проблему он определил следующим образом:

«»Пусть задано диофантово уравнение с произвольным числом неизвестных и рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых числах»».

Гипотезу, что такого способа нет, первым выдвинул (с достаточным на то основанием) американский математик М.Дэвис в 1949г. Доказательство этой гипотезы растянулось на 20 лет последний шаг был сделан только в 1970г. Юрием Владимировичем Матиясевичем, на первом году аспирантуры он показал алгоритмическую неразрешимость 10 проблемы Гильберта.

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

Понятие «диофантово» уравнение в современной математике расширено: это уравнение, у которого разыскиваются решения в алгебраических числах <#»»22″» src=»»doc_zip6.jpg»» />, где а и b целые взаимно простые числа <#»»left»»>2. Сравнения 1й степени с одним неизвестным и методы их решения

2.1 Основные понятия

Пусть натуральное число. Тогда, по теореме о делении с остатком, для всякого целого числа существует единственная пара целых чисел и таких, что , 0 ? r < m (1). Упомянутая теорема является основой следующего определения.

Определение. Если два целых числа и при делении на целое положительное дают один и тот же остаток , так что и , 0 ? r < m (2), то они называются равноостаточными, или сравнимыми по модулю . Это записывается следующим образом: (3) и читается так: « сравнимо с по модулю ». Соотношение (3) называют сравнением. Например, 57 и 37 при делении на 5 дают один и тот же остаток 2, следовательно, они сравнимы по модулю 5.

Введенное понятие сравнимости находит свое оправдание в том, что во многих арифметических вопросах основную роль играют не числа сами по себе, а те остатки, которые получаются при их делении на третье число. Сравнимые числа по данному модулю в некотором смысле «равны» между собой, а сравнения во многом подобны равенствам [4].

Сформулируем некоторые определения и утверждения, необходимые для дальнейшего изложения.

Делимость.

Определение1. Пусть . Числа и r {0,1,…,|b|1} называются соответственно неполным частным и остатком от деления a на b, если выполнено равенство a = bq + r (4).

При этом, если r = 0, то говорят, что a делится на b, или что b делит a, или что b является делителем a (обозначение a b или ba).

Доказывается, что для любых целых чисел a, b; b ? 0, существуют единственные целые числа q, r, r {0,…,|b| 1} такие, что имеет место соотношение (4) [3].

Определение2. Наименьшим общим кратным ненулевых целых чисел a1, a2, …, an называется наименьшее положительное число, которое делится на каждое из этих чисел (обозначение [a1, a2, …, an]).

Определение3. Наибольшим общим делителем целых чисел a1, a2, …, an из которых хотя бы одно отлично от нуля, называется наибольшее натуральное число, на которое делится каждое из этих чисел (обозначение (a1, a2, …, an)).

Определение4. Числа a,b Z называются взаимно простыми, если (a,b) =1. Рассмотрим свойства делимости на множестве целых чисел. Пусть a, b, c Z.

Если a|b, b|c, то a|c (свойство транзитивности).

Если a|b, a|c, то a|(b + c).

Если a|b, то для всех целых c имеет место a|bc.

Если ac|bc и c ? 0, то a|b.

Пусть a|bc и (a,c) = 1. Тогда a|b.

Если a|c, b|c и (a,b) = 1, то ab|c.

(a,b)·[a,b] = a·b.

(a,b ± a) = (a,b). (Доказательство свойств приведено в [3])

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

Введем формулировку основной теоремы арифметики:

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

2.2 Сравнения и их свойства

Чтобы изучить свойства сравнений и научиться ими пользоваться, необходимо установить удобную связь нового аппарата с обычными для нас соотношениями и понятиями. Такая связь устанавливается при помощи формул (2) из пункта 2.1. Из них следует: , или (*), где целое число.

Пусть теперь, наоборот, имеет место (*), а при делении на дает остаток , т.е. . Тогда и при делении на даст тот же остаток . В самом деле, из (*) следует , где целое число. Обозначая его через имеем . Итак, установлена эквивалентность (3) и (*).

Отметим очевидные, но, тем не менее, очень важные факты:

) если при делении на дает остаток , т.е. то, ;

) если делится на , то , или, другими словами, кратное модуля сравнимо с нулем по данному модулю: .

Свойства

. Соотношение сравнимости рефлексивно:

Из следует, что , т.е. равные числа сравнимы по любому модулю. Рефлективность можно выразить и так: .

2. Соотношение сравнимости симметрично:

Из следует, что .

3. Соотношение сравнимости транзитивно:

Из , следует: .

Все перечисленные свойства непосредственно вытекают из определения сравнимости или равноостаточности.

4. Сравнения с одним и тем же модулем можно почленно складывать и вычитать, т.е. из и следует: .

В самом деле, из условий имеем: , , , откуда , , или . Данное свойство распространяется и на случай k сравнений.

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

Следствие 2. К любой части сравнения можно прибавить число кратное модулю. Действительно, из и следует, , где [12].

5. Сравнения с одним и тем же модулем можно почленно перемножать:

т.е. из и следует, что . Для доказательства выражаем данные сравнения в форме равенств , , где целые числа, тогда получим . В произведении этих сумм все члены, кроме содержат сомножитель , поэтому , где целое число, или . Это свойство распространяется на случай сравнений.

Следствие 1. Сравнение можно почленно возводить в любую целую положительную степень, т.е. из следует, что , .

Следствие 2. Обе части сравнения можно умножать на одно и то же целое число , т.е. из следует: . Это свойство получается, если данное сравнение почленно умножить на сравнение .

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

Так, например, по модулю m из и следует, что ; из и следует, что .

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

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

7. Обе части сравнения и модуль можно умножить на одно и то же целое положительное число, а также разделить на любой их общий положительный делитель: т.е если целое >0, то из следует, что .(Справедливо также и обратное утверждение).

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

Пусть , тогда , следовательно, или , т.е. .

Второе утверждение получается, если рассуждения провести в обратной последовательности. Согласно свойствам 6. и 7. из всегда следует . Действительно, пусть , , . Тогда первое сравнение можно записать в виде , откуда по свойству 7. и далее по свойству 6. следует, что , или [12].

8. Если сравнение имеет место по нескольким модулям, то оно имеет место по модулю, равному наименьшему общему кратному этих модулей.

В самом деле, пусть и ; тогда и , откуда , где или . Это свойство распространяется на случай нескольких модулей m1, m2,…,mk.

9. Если сравнение имеет место по модулю , то оно имеет место и по модулю , равному любому делителю числа : если , то из следует, что . Действительно, из условий следует, что , а так как , то , т.е. .

10. Общий делитель одной части сравнения и модуля является также делителем второй части. Действительно, если и , , то или , откуда получаем, что . Доказанное свойство показывает, что все делители пар чисел а и m , а также b и m являются общими. Это относится и к их общим наибольшим делителям. Таким образом, приходим к следствию.

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

Рассмотрим числовой пример на применение основных свойств сравнений. Так как , то . отсюда следует, что число делится на 3 тогда и только тогда, когда сумма цифр делится на 3 [15].

2.3 Сравнения 1ой степени с одним неизвестным

Возьмем многочлен f(x)=a0 x n + a1 x n1 +…+ an1 x + an . Рассмотрим сравнение f(x) ? ?0(mod m), которое будем называть сравнением с неизвестной величиной х. Если будем в это сравнение вместо х подставлять различные целые числа, то некоторые значения х могут удовлетворять сравнению, т. е. соответствующие значения f(x) могут оказаться делящимися на m. Поставим задачу отыскания множества всех таких значений х, причем не исключена возможность и того, что это множество может оказаться пустым. Эта задача аналогична алгебраической задаче нахождения решений уравнения f(x) = 0. В алгебре ищем значения х, при которых f(х) обращается в нуль. Решая сравнение f(х) ? 0 (mod т), мы ищем значения х, и притом целые, при которых f(x) делится на m, т. е. имеет при делении на т остаток, равный нулю.

Оказывается, что сравнение f(х) ? 0 (mod т) либо вообще не имеет места ни при каких значениях х, либо существует бесконечное множество целых чисел х, удовлетворяющих сравнению, причем все эти значения х образуют некоторое число классов по модулю т [3].

Теорема. Если некоторое число а удовлетворяет сравнению f(х) ? 0 (mod т), то весь класс состоит из чисел, удовлетворяющих этому сравнению.

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

Пусть а удовлетворяет сравнению f(х) ? 0 (mod т), т.е. f(а) ? 0 (mod т) и . Тогда b ? a(mod m) и тем самым f(а) ? f(b) ? 0 (mod т). Таким образом, вместе с а любое число b класса также удовлетворяет данному сравнению.

Согласно этой теореме, если в классе имеется хотя бы одно число, удовлетворяющее сравнению f(х) ? 0 (mod т), то весь класс состоит из чисел, удовлетворяющих сравнению, а если в классе имеется хотя бы одно число, не удовлетворяющее сравнению, то и весь класс состоит из чисел, не удовлетворяющих сравнению. Принимая это во внимание, естественно решениями сравнения называть не отдельные числа, удовлетворяющие сравнению, а соответствующие классы [17].

Определение. Решением сравнения f(х) ? 0 (mod т) называется класс по модулю т, состоящий из чисел, удовлетворяющих этому сравнению.

Если класс чисел по модулю т является решением сравнения f(х) ? 0 (mod т), то говорят, что класс удовлетворяет данному сравнению. Соответственно определению, числом решений сравнения f(х) ? 0 (mod т) называют число классов по модулю т, удовлетворяющих этому сравнению.

Задача нахождения чисел, удовлетворяющих сравнению f(x) ? 0 (mod m), сводится к нахождению классов, удовлетворяющих уравнению . Действительно, если f(а) ? 0 (mod m), то ; но тогда . Легко видеть, что и, наоборот, из следует f(а) ? 0 (mod m). Решение сравнения представляет собой частный случай общей задачи решения уравнений. Особенностью этого частного случая является то, что значениями неизвестного являются классы по некоторому фиксированному модулю.

Число классов по данному модулю конечно, а именно, по модулю т имеем т классов: . Если нам дано сравнение f(x) ? 0 (mod m), то мы можем, перебрав все эти классы, выяснить, какие классы удовлетворяют этому сравнению, а какие нет, т. е. найти все его решения. Для того чтобы узнать, удовлетворяет ли класс сравнению, достаточно взять какоелибо число, принадлежащее классу, и проверить, удовлетворяет ли оно этому сравнению.

Таким образом, чтобы решить сравнение f(x) ? 0 (mod m), можно взять любую полную систему вычетов по модулю т: , вычислить и отобрать те , при которых делятся на т. Соответствующие классы дадут все решения этого сравнения. Обычно в качестве берут полную систему наименьших по абсолютной величине вычетов. Если сравнение имеет несколько решений , иногда эти решения записывают в виде . Таким образом, означает, что х принимает любые значения, сравнимые с одним из чисел [6].

Рассмотрим сравнения вида f(x) ? ?0(mod m) с одним неизвестным, где

f(x)=a0 x n + a1 x n1 +…+ an1 x + an многочлен с целыми коэффициентами. Если m не делит a0 , то говорят, что n степень сравнения. Ясно, что если какоенибудь число х подходит в сравнение, то в это же сравнение подойдет и любое другое число, сравнимое с х по модулю m.

Решить сравнение значит найти все те решения , которые удовлетворяют данному сравнению, при этом весь класс чисел по (mod m) считается за одно решение.

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

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

Сравнение вида ax b(mod m) (1) называется сравнением 1ой степени с одним неизвестным или линейным.

Исследуем вопрос о числе решений линейного сравнения.

1. Рассмотрим сначала наиболее важный случай, когда a и m числа взаимно простые, т. е. (а,m)=1.

Если в (1) вместо x подставить все вычеты из полной системы вычетов по модулю m, то, по свойству полных систем вычетов, линейная форма ax также примет все значения из полной системы вычетов, поэтому для одного и только одного значения x1 число ax1 попадет в тот класс, к которому принадлежит b; для него будем иметь аx1 ? b(mod m).

Таким образом, приходим к выводу, что в случае, когда (а,m) = 1, для сравнения (1) существует решение, притом единственное x ? x1 (mod m) или x = x1 + mt , где t = 0, ±1, ±2… Это решение можно найти методом подбора.

Пример. 5х ? 7 (mod 8).

Решение.

Испытывая вычеты из полной системы вычетов по модулю 8, т. е. числа 0, ±1, ±2, ± 3, 4, находим решение х ? 3 (mod 8) [13].

Ответ. х ? 3 (mod 8).

2. Пусть теперь (а, m)=d >1. Тогда представляются два случая.

I. Число b в правой части на d не делится.

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

Пример. Сравнение 6x ? 7 (mod 15) неразрешимо, так как (6, 15) = 3, но 7 не делится на 3.

Следует отметить, что если (b, m) = d > 1, но не делится на d, то это еще не значит, что сравнение неразрешимо, а только лишь то, что решение, если оно существует должно удовлетворять условию .

Если, например, 7x ? 6 (mod 15), то, так как (7, 15) = 1, заключаем, что сравнение разрешимо, а на основании того, что (6, 15) = 3, можем утверждать, что 7x 3. Но так как 7 не делится на 3, то отсюда вытекает, что, x 3. Это можно использовать для упрощения решения, о чем будет сказано в дальнейшем.

II. Число b в правой части делится на d. Тогда имеем

а = a1 d , b = b1 d, m = m1 d.

Поэтому по свойству сравнений, обе части и модуль сравнения можно разделить на d, после чего получаем сравнение а1x ? b1(mod m1) (2), где, (а1, m1) = 1, которое равносильно (1).

Сравнение (2) имеет по модулю m1 единственное решение x ? x1 (mod m1). Однако на этом решение сравнения (1) еще не заканчивается, так как, согласно определению, следует указать классы решений по исходному модулю т . Чтобы найти классы решений по исходному модулю m, заметим следующее. Все вычеты …,x1 m1, x1, x1 +m1,…, x1 +(d 1)m1, x1 +dm1…(3), сравнимые с x1 по модулю m1 , принадлежат по модулю m1d = m к d различным классам, представителями которых являются вычеты: x1, x1 +m1, x1 +2m1,…, x1 +(d 1)m1 (4).

Действительно, разность любых двух вычетов из (4) не делится на m (поэтому все они принадлежат различным классам по модулю m), а для каждого другого вычета из (3) найдется среди вычетов (4) такой, что их разность будет кратна т (поэтому такие вычеты принадлежат одному классу по модулю m). Таким образом, в данном случае имеем по исходному модулю т d решений: x ? x1, x1 +m1,…, x1 +(d 1)m1 (mod m) [6].

Пример. Решить сравнение: l5x ? 35(mod 55).

Решение.

(15, 55) = 5, 35 5. Следовательно, сравнение l5x ? 35(mod 55) имеет 5 решений по mod 55. После деления обеих частей сравнения и модуля на 5, получаем 3x ? 7(mod 11). Методом подбора можем найти: x ? 6(mod 11) или x = 6 + 11t, где t = 0, ±1,… Исходное сравнение имеет 5 решений: x ? 6, 6 + 11, 6 + 2·11, 6 + 3·11, 6 + 4·11 (mod 55), т. е. ? 6, 17, 28, 39, 50 (mod 55).

Ответ. x ? 6, 17, 28, 39, 50 (mod 55).

Резюмируя, приходим к следующему критерию разрешимости и заключению о числе решений сравнения (1):

) если (а, m) = 1, то решение существует, причем единственное: по данному модулю m ;

) если (а, т) = d > 1, то:

а) если b не делится на d, решений нет;

б) если b делится на d, то существует d решений d классов вычетов по исходному модулю.

Заметим, что решение сравнения надо начинать с определения d=(а, т) и проверки того, делится ли b на d или нет.

2.4 Методы решения линейных сравнений

Один из методов метод подбора был изложен выше. Рассмотрим другие методы.

Метод преобразования коэффициентов.

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

Преобразования, о которых идет речь, следующие: замена коэффициентов абсолютно наименьшими вычетами, замена b (прибавлением кратного модулю) сравнимым по модулю т числом с тем, чтобы последнее делилось на а, переход от а и b к другим, сравнимым с ними по модулю т числам, у которых оказался бы общий делитель и т. п. [5].

Преобразованиям можно подвергать а или b, a также а и b сразу.

Отметим еще, что в случае, когда (b, m) = d >1, бывает полезным перейти к новому неизвестному. Хотя этот метод, который будем называть методом преобразования коэффициентов, не выражен в виде определенного предписания, все же для небольших модулей он является (при соответствующих навыках) довольно эффективным.

Примеры.

Решить сравнения:

х ? 7 (mod 8).

Решение.

5х ? 7 (mod 8);

5х ? 7 + 8 = 15 (mod 8);

Так как (5, 8) = 1, то х ? 3 (mod 8).

Ответ. х ? 3 (mod 8).

2) 7x ? 6 (mod 15).

Решение.

1й способ.

7x ? 6 (mod 15);

7x ? 6+15 = 21 (mod 15);

(7, 15) = 1, x ? 3(mod 15).

2й способ.

Так как (6, 15) = 3, делаем подстановку х = 3у, тогда 7·3y ? 6 (mod 15),

7y ?2(mod 5), 2у ? 2 (mod 5), у ? 1 (mod 5), 3у ? 3 (mod 15),

х = 3у ? 3 (mod 15).

Ответ. x ? 3(mod 15).

3) 17x ? 25 (mod 28).

Решение.

17x ? 25 (mod 28);

(17, 28) = 1;

17х + 28х ? 25(mod 28), т.к. (5, 28) = 1, то 45x ? 25 (mod 28);

9x ? 5 (mod 28), 9x ? 5 140 ? 135 (mod 28), x ? 15 ?13 (mod 28).

Ответ. x ?13 (mod 28).

Метод Эйлера.

Теорема. Пусть m >1, (a,m)=1. Тогда сравнение ax ? b(mod m) имеет решение: x ?? ba ??(m)1 (mod m) .

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

По теореме Эйлера, имеем: a ?? (m) ?1(mod m) , следовательно, a ba ? ?? (m)1? b(mod m) [12].

Пример. Решить сравнение 7x ? ?3(mod 10).

Решение.

Вычисляем: ??(10)=4; x ?3 · 7 41 (mod 10) ? 1029(mod 10) ?9(mod 10).

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

Пример. Решить сравнение 3х ? 6(mod 9).

Решение.

Т.к. (3, 9) = 3 и 6 делится на 3, то данное сравнение имеет три решения. Делим обе части и модуль данного сравнения на 3, получим:

х ? 2(mod 3). Тогда решениями данного сравнения будут: х ? 2(mod 9),

х ? 2 + 3 = 5(mod 9), х ? 2 + 2*3 = 8(mod 9), т.е. х ? 2, 5, 8(mod 9).

Ответ. х ? 2, 5, 8(mod 9).

Метод применения аппарата цепных дробей.

Правильные конечные цепные дроби.

Выделение целой части.

Если а целое, а m натуральное число, то существует единственное представление , 0 ? r < m (1), где q неполное частное, r остаток от деления а на т. Формула (1) равносильна соотношению

(2).

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

Разность называется дробной частью числа и обозначается . Определение целой части q согласно (2) называется выделением целой части.

Поскольку это понадобится нам в дальнейшем, отметим, что понятия целой и дробной части можно отнести к любому действительному числу а.

Целой частью действительного числа а называется наибольшее целое число k, не превосходящее а, т. е. удовлетворяющее соотношению

k ? a <k + 1.

Целая часть действительного числа а существует в единственном виде и обозначается [а]. Итак, [а]= k, так что [а]? a<[а]+1.

Дробной частью действительного числа а называется разность а [а], она тоже существует и единственна, обозначается {a}.

Таким образом, {a}= а [а], откуда а =[а]+{a}, где 0?{a}<1 [4].

. Разложение в правильную цепную дробь.

Пусть рациональное число, причем b > 0. Применяя к а и b алгоритм Евклида для определения их наибольшего общего делителя, получаем конечную систему равенств:

(1)

где неполным частным последовательных делений q1,q2,…,q n1 соответствуют остатки r2,,r3,…,rn с условием b > r2 > r3 > … > rn > 0, а q n соответствует остаток 0.

Системе равенств (1) соответствует равносильная система:

(2)

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

.

Такое выражение называется правильной (конечной) цепной или правильной непрерывной дробью; при этом предполагается, что q1 целое число, a q2 ,…, qn натуральные числа.

Имеются различные формы записи цепных дробей:

.

Числа q1,q2,…,qn называются элементами цепной дроби.

Алгоритм Евклида дает возможность найти представление (или разложение) любого рационального числа в виде цепной дроби. В качестве элементов цепной дроби получаются неполные частные последовательных делений в системе равенств (1), поэтому элементы цепной дроби называются также неполными частными. Кроме того, равенства системы (2) показывают, что процесс разложения в цепную дробь состоит в последовательном выделении целой части и перевертывании дробной части [10].

Разложение рационального числа имеет, очевидно, конечное число элементов, так как алгоритм Евклида последовательного деления а на b является конечным. Понятно, что каждая цепная дробь представляет определенное рациональное число, то есть равна определенному рациональному числу. Но возникает вопрос, не имеются ли различные представления одного и того же рационального числа цепной дробью? Оказывается, что не имеются, если потребовать, чтобы было .

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

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

1) Заметим, что при отказе от указанного условия единственность представления невозможна. В самом деле, при получаем, так что представление можно записать следующим образом: . (Например, (2, 3, 1, 4, 2) = ( 2, 3, 1, 4, 1, 1)).

2) Принимая условие , можно утверждать, что целая часть цепной дроби равна ее первому неполному частному . В самом деле:

Если n=2, то ; поэтому

Если n>2, то

где >1, т.к.

Поэтому и здесь .

Докажем то, что рациональное число однозначно представляется цепной дробью , если . Пусть с условием , . Тогда , так что . Повторным сравнением целых частей получаем , а следовательно и так далее. Если , то в продолжение указанного процесса получим также . Если же , например , то получим , что невозможно [16].

Вместе с тем мы установили, что при соблюдении условия между рациональными числами и конечными цепными дробями существует взаимно однозначное соответствие.

Замечания:

В случае разложения правильной положительной дроби первый элемент , например, .

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

Пример.

, а так как , то

Всякое целое число можно рассматривать как непрерывную дробь, состоящую из одного элемента. Например: 5=(5); .

. Подходящие дроби, некоторые их свойства.

Задаче разложения обыкновенной дроби в непрерывную дробь естественно противостоит обратная задача обращения или свертывания цепной дроби (q1,q2,…,qn) в простую дробь . При этом, а также и в других вопросах теории непрерывных дробей, основную роль играют дроби вида:

или которые называются подходящими дробями данной непрерывной дроби или соответствующего ей числа . Заметим, что .

Считается, что подходящая дробь ?k имеет порядок k. Приступая к вычислению подходящих дробей, предварительно заметим, что ?k переходит в ?k+1, если в первой заменить qk выражением . Имеем:

,

при этом принимается, что Р0 = 1, Q0=0, Р1= q1, Q1 =1, Р2 = q2 Р1+ Р0, Q2 = q2 Q1 + Q0 и т.д. Закономерность, которую замечаем в построении формулы для ?2, (ее числителя P2 и знаменателя Q2), сохраняется при переходе к ?3 и сохранится также при переходе от к к к + 1.

Поэтому на основании принципа математической индукции для любого к, где 2? k ? n, имеем: (1), причем и .

Впредь, говоря о подходящих дробях ?k , (в свернутом виде), мы будем иметь в виду их форму [4].

Соотношения (1) являются рекуррентными формулами для вычисления подходящих дробей, а также их числителей и знаменателей. Из формул для числителя и знаменателя сразу же видно, что при увеличении k они возрастают.

Применяется следующая схема, в которую последовательно записываются значения Рк, Qк, от Р1 , Q1 до Рn , Qn по формулам (1):

q1q2…qk2qk1qk…qkPkP0 =1P1 = q1P2…Pk2Pk1Pk…PnQkQ0 = 0Q1 = 0Q2…Qk2Qk1Qk…Qn

Отметим некоторые свойства подходящих дробей, которые будут использоваться далее.

1) При k=1, 2, …, n выполняется равенство .

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

Проведем индукцию по k. При k =1 равенство справедливо, так как . Пусть это равенство верно при некотором k = n ().

Докажем справедливость равенства при k = n+1.

,

то есть равенство верно при k = n+1. Согласно принципу полной математической индукции равенство верно для всех k ().

2) Числитель и знаменатель любой подходящей дроби взаимно простые числа, то есть всякая k подходящая дробь несократима.

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

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

3) Разность двух подходящих дробей при вычисляется по формулам: () , ().

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

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

, .

Докажем второе соотношение.

.

3) Знаменатели подходящих дробей к цепной дроби, начиная с первого, образуют монотонно возрастающую последовательность, то есть 1=.

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

, , так что и положительны. Соотношение , () показывает, что и все следующие знаменатели , , …, положительны. При , поскольку тогда , из , () получаем .

4) Нечетные подходящие дроби образуют возрастающую, а четные подходящие дроби убывающую последовательность: ;

. Две подходящие дроби и , у которых номер отличается на единицу, будем называть соседними.

5) Из двух соседних подходящих дробей четная дробь всегда больше нечетной.

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

По уже доказанному выше свойству имеем: . Если k четное, то

Если k нечетное, то Значит, из двух соседних дробей и четная всегда больше нечетной.

6) Разность двух соседних подходящих дробей равна: , то .

Отсюда расстояние между двумя соседними подходящими дробями [4].

Решение сравнений первой степени с помощью цепных дробей.

. Вывод формулы решения.

Пусть дано сравнение ах ? b (mod m), где (а, m) =1, а > 0 (1). Разложим в непрерывную дробь и обозначим ее подходящие дроби через , где k = 1, 2,…,n . Тогда согласно свойству несократимости подходящих дробей имеем Рn=m, Qn = a. Поэтому вместо соотношения Pn · Qn 1 Pn 1 · Qn = (1)n имеем m · Qn 1 Pn 1 · a = (1)n . Отсюда a · Pn 1 = (1)n + m · Qn 1 или (так как Qn1 целое число) a · Pn 1 ? (1)n 1(mod m). Умножая обе части этого сравнения на (1)n1b, получим a((1)n 1 Pn 1 · b) ? b(mod m). Сравнивая это сравнение с исходным (1), приходим к выводу, что оно имеет решение x ? (1)n 1Pn 1·b (mod m) (2), где Pn 1 числитель предпоследней подходящей дроби в разложении . Так как (1) имеет только одно решение, то (2) совпадает с единственным решением [11].

Пример. Решить сравнение 285 x ? 177 (mod 924).

Решение.

285 x ? 177 (mod 924), находим (285, 924)=3, 177 = 59 · 3; далее, после деления обеих частей сравнения и модуля на 3, получаем 95x ? 59 (mod 308). По схеме определяем теперь неполные частные разложения 308/95 в цепную дробь, а затем Pn 1 и (для проверки правильности вычисления) Pn . Имеем

308|95 |23 |3 |2 |13 4 7 1 21 3 13 94 107 308

Итак, Рn1 = Р4 =107, следовательно, х ?(1)4·107 ·59 (mod 308), x ? 153 (mod 308). Исходное сравнение имеет решения: ? 153, 461, 769 (mod 924).

Ответ. x ? 153, 461, 769 (mod 924).

3. Диофантовы уравнения 1й степени и методы их решения

Определение 1. Диофантовым уравнением 1ой степени или линейным диофантовым уравнением с неизвестными называется уравнение вида ,

где , , .

Условимся далее сокращать фразу « линейное диофантово уравнение » следующим образом: «ЛДУ».

Определение 2. Решением ЛДУ называется упорядоченная последовательность целых чисел , такая, что .

3.1 О числе решений ЛДУ

Теорема 1. При взаимно простых коэффициентах диофантово уравнение имеет решение в целых числах.

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

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

В множестве существует наименьшее число ( подмножество натуральных чисел), которое мы обозначим через Обозначим через целые числа, такие, что .

Пусть , где ; тогда

. Мы подобрали целые значения: , ,…, , такие, что , но , а наименьшее положительное число в , т. е. не может быть положительным, , , . Аналогично получаем: ,…,.

Мы видим, что общий делитель чисел , следовательно, поскольку , , , , то уравнение разрешимо в целых числах [11].

Теорема 2. Пусть наибольший общий делитель коэффициентов . Диофантово уравнение имеет решение тогда и только тогда, когда . Число решений такого уравнения равно либо нулю, либо бесконечности.

Докажем последовательно все три утверждения теоремы.

) Пусть . Для уравнения , где , существуют целые числа: удовлетворяющие ему, т.е. . Тогда т. е. решение уравнения.

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

) Если упорядоченная последовательность чисел, удовлетворяющих уравнению, то, например, при также удовлетворяют этому уравнению и, таким образом, либо совсем не будет решений, либо их будет бесконечное множество.

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

3.2 Нахождение решений произвольного ЛДУ

Перейдем теперь к решению ЛДУ с неизвестными, т. е. уравнений вида , где все коэффициенты и неизвестные целые числа и хотя бы одно . Для существования решения, по теореме 2, необходимо, чтобы Полагая: , перейдем к равносильному уравнению (*), где . Пусть, два ненулевых числа, таких, что Для определенности предположим, что, Разделив с остатком на , получим представление . Заменив на в уравнении (*), приведем его к виду .

Перепишем это уравнение в виде (**), где

, .

Очевидно, что решения уравнения (*) и (**) связаны между собой взаимно однозначным соответствием и, таким образом, решив уравнение (**), несложно найти все решения уравнения (*). С другой стороны отметим, что , отметим также, что

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

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

3.3 Нахождение решений для некоторых частных случаев ЛДУ

А) ЛДУ c одним неизвестным.

Рассмотрим линейное уравнение с одним неизвестным, т.е. уравнение вида . Ясно, что решением данного уравнения будет , и решение будет целым числом только в том случае, когда .

Б) ЛДУ с двумя неизвестными.

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

, .

Покажем несколько способов нахождения решения.

Способ 1.

Пусть . Рассмотрим два случая:

а) не делится на . В этом случае решений нет по теореме 2.

б) делится на , разделим на обе части уравнения:

;

.

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

Рассмотрим , . , перейдем к сравнению, , т.к. , то сравнение имеет единственное решение или . Подставляя х в уравнение, получим , ; , причем .

Обозначим . Тогда общее решение можно найти по формулам: , где .

Пример. Решить уравнение .

Решение.

Найдем решение сравнения , . Применяя метод преобразования коэффициентов, получаем: ; , т.е. , . ;

Получили общее решение: , где .

Ответ. Общее решение находится по формулам , где .

Способ 2.

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

Рассмотрим теперь уравнение , . Пусть его частное решение, а множество общее решение соответствующего ЛОДУ. Докажем предложение.

Общее решение ЛДУ , , задается формулами

, где .

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

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

однородное уравнение. Его общее решение: , откуда получаем:

, . Доказательство завершено.

Встает вопрос о нахождении частного решения ЛДУ.

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

Таким образом, для нахождения общего решения находим общее решение ЛОДУ, частное решение ЛДУ и их складываем [17].

Замечание. Особенно этот способ удобен, когда или . Если, например, , , тогда , очевидно, будет частным решением ЛДУ. Можно сразу выписывать общее решение.

Пример. Решить уравнение: .

Решение.

, найдем частное решение. Используем алгоритм Евклида. ; Получаем линейное разложение НОД:

, т.е .

,

Получили общее решение: , где .

Как видим, получили решение, не совпадающее с решением, найденным первым способом.

Обозначим , получим , , т.е эти решения равносильны [7].

Ответ. Общее решение вычисляется по формулам , , .

Способ 3. Основывается на теореме.

Теорема. Если числа а и b целые, то множество значений функции f(x; y) = ax + by от двух целочисленных аргументов х и у совпадает с множеством чисел, кратных d = НОД(а; b), то есть с множеством {…, 2d, d, 0, d, 2d, …}.

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

Так как d = НОД(а; b), числа а и b можно записать в виде: а = da’, b = db’, причем числа а’ и b’ взаимно простые. Тогда f(x; у) = d (а’х + b’у). (т.к. любое целое число n можно представить в виде а’х + b’у). Получим множество чисел, которые могут быть записаны в виде ах + by, есть {…, 2d, d, 0, d, 2d, …}.

Приведенное доказательство теоремы дает удобный метод нахождения частного (то есть конкретного) решения при решении конкретных уравнений вида ах + by = с (если а и b взаимно простые целые числа):

) нужно образовать две последовательности чисел: {…, 2а, а, 0, а, 2а, …} и {…, 2b, b, 0, b, 2b, …} (обычно достаточно выписать по несколько членов в обе стороны), и расположить их друг под другом так, чтобы положительные члены одной стояли под отрицательными членами другой;

) затем находить всевозможные суммы пар членов этих последовательностей, пока не найдем пару, дающую в сумме с.

Рассмотрим, например, уравнение 2х 5у =1. Выпишем ряды чисел, кратных коэффициентам а = 2 и b = 5:

Из этой таблицы ясно, что второе число из первой строки (то есть 4), которое соответствует х = 2, и третье число из второй строки (то есть 5), которое соответствует у = 1, и дают в сумме 1. Таким образом, уравнение 2х 5у = 1 имеет частное решение х0 = 2, у0 = 1. Конечно, эту пару можно найти и проще, просто подставляя в исходное уравнение в уме небольшие числа с тем, чтобы получить верное равенство. Для несложных уравнений обычно поступают именно так.

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

На примере следующей задачи продемонстрируем, как с помощью частного решения неоднородного ЛДУ уравнения ах + by = с и общего решения соответствующего однородного ЛДУ ах + by = 0 можно найти общее решение неоднородного ЛДУ.

Пример. Остаток от деления некоторого натурального числа n на 6 равен 4, остаток от деления n на 15 равен 7. Чему равен остаток от деления n на 30?

Решение.

По теореме о делении с остатком в кольце Z целых чисел, существуют неотрицательные целые х, у, такие, что n = 6х + 4 и n = 15у + 7. Исключая из этих равенств число n, для х и у получим уравнение 6х 15у = 3 или, после деления на 3, 2х 5у = 1.

Чтобы решить это уравнение, прежде всего, найдем какоенибудь частное решение в целых (не обязательно неотрицательных) числах. В качестве такого частного решения можно взять, например, х0 = 2, y0 = 1, так что верно равенство 2 (2)5 (1)=1. Вычитая из уравнения данное равенство, получим: 2(х + 2) = 5(y + 1). Общее решение этого уравнения в целых числах имеет вид: х + 2 = 5k, у + 1 = 2k, где k произвольное целое число. Чтобы числа х и у были неотрицательными, параметр k должен быть натуральным числом. Теперь для числа n имеем: n = 6х + 4 = 6(5k 2) + 4 = 30k 8 = 30(k 1) + 22. Поскольку целое число (k 1) неотрицательно, это равенство означает, что остаток от деления n на 30 равен 22.

Ответ. Остаток от деления n на 30 равен 22.

Практическая часть

№1. Решить уравнение: .

Решение.

Уравнение неоднородное линейное диофантово уравнение. . Уравнение имеет целые решения. Найдем их, сведя уравнение к сравнению . Решение сравнения методом преобразования коэффициентов: , , . Т.к. , то по свойству сравнений, ; , , . , , , . Общее решение исходного уравнения имеет вид: , где .

Ответ. Общее решение: , где .

№2. Решить диофантово уравнение при помощи линейного представления НОД: .

Решение.

НОД(a, b) = 1, то найдутся такие x, y, что . Тогда выполнится: ax ? c + by ? c = c. НОД(47, 111) = 1. Найдем x, y: , , , , .

Линейное представление: . Тогда выполняется: .

; , . ,

Ответ: Общее решение: , , , или , , .

№3. С помощью цепных дробей найти все целые решения уравнений: а) ; б) .

Решение.

а) (2, 5) = 1, следовательно, уравнение имеет решение в целых числах. Разложим в цепную дробь получим: =(0, 2, 2). Составим все подходящие дроби. ; ; . На основании свойства подходящих дробей получим или . Умножив обе части равенства на (7) получаем: , то есть , частное решение. Все решения могут быть найдены по формулам или , .

б) (23, 49) = 1, 531 следовательно, уравнение имеет решение в целых числах. Разложим в цепную дробь получим: =(0, 2, 7, 1, 2). Составим все подходящие дроби. ; ; ; ; . На основании свойства подходящих дробей получим или . Умножив обе части равенства на (53) получаем: , то есть , частное решение. Все решения могут быть найдены по формулам или , .

Ответ. а) , ; б) , .

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

Решение.

, . Данное уравнение равносильно уравнению , , следовательно, неоднородное линейное диофантово уравнение имеет целые решения. Разложим в цепную дробь: (1; 1, 2, 1, 2, 1, 2). Составим все подходящие дроби: ; ; ; ; ; ; . На основании свойства подходящих дробей получаем: или . Умножив обе части равенства на 3, находим: , т.е. , частное решение данного уравнения. Все решения могут быть найдены по формулам: или , .

Ответ. Общее решение: , .

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

Решение.

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

Проверка: частное решение диофантова уравнения: , истинное равенство.

Ответ. Общее решение: , .

№6. Задача.

Для настила пола шириной 3м имеются доски шириной в 11см и 13см. Сколько нужно досок того и другого размера?

Решение.

Пусть количество досок шириной в 11см, количество досок шириной в 13см. Составим уравнение: 11x + 13y = 300 и решим его.

x + 13y = 300, 11x ? 300(mod 13), (11, 13) = 1, x ? 6(mod 13), x0 = 6= (30011·6) / 13, y 0 =18; где .

Это общее решение диофантова уравнения. следовательно, и т.к. , то возможны только два случая и , т.е. (19; 7) или (6; 18).

Ответ. , , , .

№7. Задача.

Требуется найти два натуральных числа, каждое из которых не превышает 200, причем таких, что разность между ними равна 11, уменьшаемое кратно 9, а вычитаемое кратно 17.

Решение.

Пусть , , . Составим уравнение: (1); (2), , . Т.к. , то решение сравнения (2).

, ; , , . Итак, общее решение уравнения (1): , .

, ,

, ,

, ,

, ,

, , , .

Ответ. (45, 34); (198, 187).

№8. Задача.

В населенный пункт, с которым установлено лишь авиационное сообщение, требуется доставить 150 контейнеров груза. В распоряжении отправителей имеются транспортные самолеты грузоподъемностью соответственно в 8 и 13 контейнеров. Сколько понадобится самолетов того и другого типа для того, чтобы перевезти указанный груз одним рейсом? Грузоподъемность каждого самолета должна быть использована полностью.

Решение.

Пусть х, у количество транспортных самолетов грузоподъемностью соответственно 8 и 13 контейнеров. По условию, в населенный пункт требуется доставить 150 контейнеров груза. Тогда (1). Составлено диофантово уравнение первой степени с двумя неизвестными. Решим его, перейдя к сравнению (2). Т.к. (4, 13) =1, то , , . Т.к. (4, 13) =1, то или , , .

Ответ. Понадобится 9 и 6 самолетов одного и другого типов, чтобы доставить 150 контейнеров груза.

№9. Задача.

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

Решение.

Пусть число выделяемых машин грузоподъемностью 3,5т., число выделяемых машин грузоподъемностью 4,5т. Для решения задачи нужно решить уравнение т.е. (1) в целых числах с учетом того, что , . Уравнение (1) равносильно уравнению . =(0, 1, 3, 2). Посчитаем подходящие дроби:

N0123013201371149

По второму свойству подходящих дробей имеем: , , .

, . Решениями будут: , , .

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

Ответ. Автомашины можно выделить двумя способами:

) 10 автомашин грузоподъемностью 3,5т. и 4 автомашины грузоподъемностью 4,5т.

) 1 автомашину грузоподъемностью 3,5т. и 11 автомашины грузоподъемностью 4,5т.

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

Решение.

. Разделив с остатком (6) на 4, получим . Представим исходное уравнение в виде . После замены это уравнение запишется следующим образом: . Учитывая, что , преобразуем последнее уравнение: . Положив , получим .

Это уравнение имеет следующее решение: произвольные целые числа, . Следовательно, , . Таким образом, решение исходного уравнения имеет вид где произвольные целые числа.

Ответ. Решение уравнения: .

Заключение

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

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

В данной работе:

изложена историческая справка о возникновении и развитии теории неопределенных уравнений;

рассмотрены числовые сравнения и их свойства, а также линейные сравнения с одним неизвестным и методы их решения;

изучены диофантовы уравнения 1ой степени с двумя неизвестными;

разобраны методы решения линейных диофантовых уравнений с двумя неизвестными;

изложены методы решения диофантовых уравнений первой степени с n неизвестными, n ? 2;

выполнены упражнения, относящиеся к теме исследования.

Литература:

диофантовы уравнение неизвестный

1. Башмакова И.Г. «Диофант и диофантовы уравнения». М.: Наука, 1972.

2. Башмакова И.Г. «История диофантова анализа от Диофанта до Ферма». М.: Наука, 1974.

3. Банникова Т.М., Баранова Н.А. «Основы теории чисел»(учебно методическое пособие). Ижевск, 2009.

4. Бухштаб А.А. «Теория чисел». M.: Просвещение, 1966.

5. Вейль Г. «Основы теории чисел». М., 2004.

6. Виноградов И.М. «Основы теории чисел». М.: Наука, 1976.

7. Грибанов В.У., Титов П.И. «Сборник упражнений по теории чисел». М.: Просвещение, 1964.

8. Диофант Александрийский «Арифметика и книга о многоугольных числах». Перевод с древнегреческого Веселовского И.Н., под редакцией Башмаковой И.Г. М.: Наука, 1974.

9. Завало С.Т. и др. «Алгебра и теория чисел». Киев: Высшая школа, 1980.

10. Казачек И.К., Перлатов П.Н. и др. «Алгебра и теория чисел».(уч. пособие для студентов заочников физмат. факультетов пед. институтов)

11. Кудрватов А.В. «Сборник задач по теории чисел».

Куликов Л.Я. «Алгебра и теория чисел». М.: Высшая школа, 1979.

12. Куликов Л.Я. «Сборник задач по теории чисел».

13. Кушнир И. «Математическая энциклопедия».

14. Ляжен Е.С., Евсеев А.Е. «Алгебра и теория чисел». М.: Высшая школа, 1978.

15. Михелович Т.Л. «Теория чисел». М.: Наука, 1983.

Розуэн М., Айерленд К. «Классическое введение в современную теорию чисел»(перевод с английского С.П.Демушкина под редакцией А.Н.Паршина). М.: Мир, 1987.