Диофантовые уравнения

Размещено на http://www.allbest.ru/

2

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

Заключение

Литература

Введение

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

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

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

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

Конкретные задачи такого рода были решены еще в Древнем Вавилоне около 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 проблемы Гильберта.

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

Понятие «диофантово» уравнение в современной математике расширено: это уравнение, у которого разыскиваются решения в алгебраических числах. Диофантовы уравнения называются также неопределёнными. Простейшее диофантово уравнение , где а и b -- целые взаимно простые числа, имеет бесконечно много решений.

Общая теория решения диофантовых уравнений первой степени была создана в 17 в. французским математиком К. Г. Баше; к началу 19 в. трудами П.Ферма, Дж. Валлиса, Л. Эйлера, Ж. Лагранжа и К. Гаусса [18].

Отметим, что в первый раз сочинения Диофанта были изданы в латинском переводе, в 1575г. (Xylander, "Diophanti Alexandrini Rerum Arithmeticarum Libri sex"); затем в 1621г. Bachet de Mйziriac издал греческий текст Диофанта с переводом на латинский язык и собственными примечаниями; тот же перевод был переиздан в 1670г. с замечательными примечаниями Ферма; кроме того, имеются переводы на французский (Stevin et Girard, Пар., 1625г.) и немецкий (Otto Schulz, Берл., 1822г.).

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. Наименьшим общим кратным ненулевых целых чисел a₁, a₂, ..., a_n называется наименьшее положительное число, которое делится на каждое из этих чисел (обозначение [a₁, a₂, ..., a_n]).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Свойства

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В самом деле, пусть и ; тогда и , откуда , где или . Это свойство распространяется на случай нескольких модулей m₁, m₂,…,m_k.

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

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

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

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

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

Возьмем многочлен f(x)=a₀ x ⁿ + a₁ x ^n-1 +...+ a_n-1 x + a_n . Рассмотрим сравнение 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)=a₀ x ⁿ + a₁ x ^n-1 +...+ a_n-1 x + a_n - многочлен с целыми коэффициентами. Если m не делит a₀ , то говорят, что n - степень сравнения. Ясно, что если какое-нибудь число х подходит в сравнение, то в это же сравнение подойдет и любое другое число, сравнимое с х по модулю m.

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

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

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

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

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

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

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

Таким образом, приходим к выводу, что в случае, когда (а,m) = 1, для сравнения (1) существует решение, притом единственное x ? x₁ (mod m) или

x = x₁ + 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. Тогда имеем

а = a₁ d , b = b₁ d, m = m₁ d.

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

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

x₁, x₁ +m_1, x₁ +2m₁,…, x₁ +(d -1)m₁ (4).

Действительно, разность любых двух вычетов из (4) не делится на m (поэтому все они принадлежат различным классам по модулю m), а для каждого другого вычета из (3) найдется среди вычетов (4) такой, что их разность будет кратна т (поэтому такие вычеты принадлежат одному классу по модулю m). Таким образом, в данном случае имеем по исходному модулю т d решений:

x ? x₁, x₁ +m₁,…, x₁ +(d -1)m₁ (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), т. е.

x ? 6, 17, 28, 39, 50 (mod 55).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры.

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

1) 5х ? 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).

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

Теорема. Пусть 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 ^4-1 (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).

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

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

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

Если а -- целое, а 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].

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

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

(1)

где неполным частным последовательных делений q₁,q₂,...,q _n-1 соответствуют остатки r₂,,r₃,…,r_n с условием b > r₂ > r₃ > ... > r_n > 0, а q _n соответствует остаток 0.

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

(2)

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

.

Такое выражение называется правильной (конечной) цепной или правильной непрерывной дробью; при этом предполагается, что q₁ - целое число, a q₂ ,..., q_n -- натуральные числа. Имеются различные формы записи цепных дробей:

.

Числа q₁,q₂,...,q_n называются элементами цепной дроби.

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

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

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

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

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

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

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

b) Если n>2, то

где >1, т.к.

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

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

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

Замечания:

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

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

Пример.

, а так как , то .

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

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

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

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

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

при этом принимается, что Р₀ = 1, Q₀=0, Р₁= q₁, Q₁ =1, Р₂ = q₂ Р₁+ Р₀, Q₂ = q₂ Q₁ + Q₀ и т.д. Закономерность, которую замечаем в построении формулы для д₂, (ее числителя P₂ и знаменателя Q₂), сохраняется при переходе к д₃ и сохранится также при переходе от к к к + 1.

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

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

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

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

		q1	q2	…	qk-2	qk-1	qk	…	qk
Pk	P0 =1	P1 = q1	P2	…	Pk-2	Pk-1	Pk	…	Pn
Qk	Q0 = 0	Q1 = 0	Q2	…	Qk-2	Qk-1	Qk	…	Qn

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

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

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

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

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

,

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

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

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

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

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

() , ().

...