Решение диофантовых уравнений первой и второй степени

Министерство  образования и науки Республики Казахстан

Восточно-Казахстанская  область 
 
 

Направление: математическое моделирование экономических и социальных процессов. 
 

Секция: математика 
 

Тема: Решение диофантовых уравнений первой и второй степени 
 
 

Автор:

Жумадилов Эльдар,

Буркутова Амина,

10 класс,

ГУ  «Экономический лицей»

г.Семей. 
 

Руководитель:

Дранная Наталия Александровна

ГУ  «Экономический лицей»

г. Семей

Консультант:

Заведующий  кафедрой   математики и  методики преподавания                                                                  математики Семипалатинского                                                                       государственного педагогического                                                                                 института, кандидат физико-                                                                      математических наук, доцент                                             

Жолымбаев Оралтай Муратханович 
 
 
 
 
 

Усть-Каменогорск

2010г.

Оглавление 

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

    Глава 1.О диофантовых уравнениях.......................................................4

    Глава 2.Методы решения.........................................................................6

         2.1.Алгоритм Евклида......................................................................6

         2.2.Цепная дробь...............................................................................8

         2.3.Метод разложения на множители.............................................9

         2.4.ИСпользование четности...........................................................10

         2.5.Другие методы решения диофантовых уравнений.................10

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

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

    Приложение.............................................................................................14 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Введение 

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

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

    Таким посвящением открывается «Арифметика» Диофанта Александрийского.

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

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

    Наиболее  интересным представляется творчество Диофанта. До нас дошло 7 книг из 13, которые были объединены в “Арифметику”.

    В этой книге Диофант (3 век) суммировал и расширил накопленный до него опыт решения неопределенных алгебраических уравнений в целых или рациональных числах. С тех пор эти уравнения стали называться диофантовыми.

    Вот примеры таких уравнений : х² +у² =z² ,   х² = у³ +5у + 7.

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

    х² +у² =z² .

    Диофантовы  уравнения позволяют решать алгебраические задачи в целых числах. «Арифметика» Диофанта легла в основу теории чисел нового времени.     [1]

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

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

    Глава 1. О диофантовых  уравнениях. 

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

    К диофантовым  уравнениям  приводят задачи, по смыслу которых неизвестные значения величин могут быть только целыми числами. [2]

    Рассмотрим  одну задачу: За покупку нужно уплатить 1700 р. У покупателя имеются купюры только по 200 и 500 р. Какими способами  он может расплатиться?  Для ответа на этот вопрос достаточно решить уравнение 2х +5у = 17 с двумя неизвестными х и у. Такие уравнения имеют бесконечное множество решений. В частности, полученному уравнению отвечает любая пара чисел вида . Для нашей практической задачи годятся только целые неотрицательные значения х и у (рвать купюры на части не стоит). Поэтому приходим к постановке задачи: найти все целые  неотрицательные решения уравнения 2х +5у = 17. Ответ содержит уже не бесконечно много, а всего лишь две пары чисел (1;3) и   (6; 1).

    Таким образом, особенности диофантовых задач заключаются в том, что: 1) они сводятся к уравнениям или системам уравнений с целыми коэффициентами; 2) решения требуется найти только целые, часто натуральные. [3]

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

  Делимость

  Определение Пусть a,b Î Z, b ≠ 0. Числа q Î Z и r Î {0,1,...,|b|-1} называются соответственно неполным частным и остатком от деления a на b, если выполнено равенство

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

  Диофантовы  уравнения можно записать в  виде

P(x₁, x₂, ..., x_n) = 0,

где P(x₁, ..., x_n) - многочлен с целыми коэффициентами.

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

1. имеет ли уравнение целочисленные решения;
2. конечно или бесконечно множество его целочисленных решений;
3. решить уравнение на множестве целых чисел, т. е. найти все его целочисленные решения;
4. решить уравнение на множестве целых положительных чисел;
5. решить уравнение на множестве рациональных чисел.

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

x³ + y³ + z³ = 30

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

    Глава 2. Методы решения. 

  2.1 Алгоритм Евклида.

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

       Чтобы доказать это утверждение, представим описанный процесс в виде следующей цепочки равенств: если а>b, то 

       

 

       Здесь r₁, …, r_n – положительные остатки, убывающие с возрастанием номера. Из первого равенства следует, что общий делитель чисел а и b делит r₁ и общий делитель b и r₁ делит а, поэтому НОД (а, b) = НОД (b, r₁). Переходя к следующим равенствам системы, получаем: 

       НОД(а, b) = НОД (b, r₁) = НОД (r_1, r₂) = …

       …= НОД (r_n-1, r_n) = НОД (r_n, 0) = r_n. [3]

    Таким образом, решая диофантовы уравнения первой степени ax + by = с, можно  применять следующие теоремы:

    Теорема1.. Если НОД (a, b) = 1, то уравнение ax + by = 1 имеет, по меньшей мере, одну пару (x, y) целого решения.

    Теорема 2. Если НОД (a, b) = d > 1, и число с не делится на d, то уравнение           ах + by = с не имеет целого решения.

    Доказательство. Предположим, что уравнение ах + by = с имеет целое решение (х₀, y₀). Так как,  а d, b d, то получим, что с = (ах + by) d. Это противоречит условиям теоремы и тем самым теорема доказана.

    Теорема 3. Если НОД (a, b) = 1,то все целые решения уравнения ах + by = с определяются формулой:

    х = х₀с +  bt

    y = y₀c -  at.

    Здесь (х₀, y₀) – целое решение уравнения ах + by = 1, а t – произвольное целое число. 
 

       Пример 1.  Решить в целых числах уравнение 54х + 37у = 1.

По алгоритму Евклида а = 54, b = 37. Подставляем данные под алгоритм и получаем: