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

Восточно-Казахстанская область
Направление: математическое моделирование экономических и социальных процессов.
Секция: математика
Тема: Решение диофантовых уравнений первой и второй степени
Автор:

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

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

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, если выполнено равенство

a = bq + r.

При этом, если 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, bd, то получим, что  с = (ах + by)d. Это противоречит условиям теоремы и тем самым теорема доказана.

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

х = х₀с +  bt

y = y₀c -  at.

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

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

54=371+17, остаток от деления     17 = 54-371
Далее, следуя алгоритму, получаем:

37 = 172+3 ,    3 = 37-172

17 = 35+2 ,    2 = 17- 35

3 = 21+1 ,    1 = 3 - 21
После нахождения единицы выражаем через неё значения а и b:
                                                     1 = 3 – (17-35);

                                                     1 = 17- 34;

 1 = 17 - (37- 172) 4;

                                                     1 = 17 - 374+178;

                                                     1 = 179 – 374;

    1 = (54- 371) 9 - 374;

                                                     1 = 549 - 379 - 374;

                                                     1 = 549 - 3713

                                                     1 = 54х + 37у

Следовательно,  х₀ = 9, у₀ = -13. Значит, данное уравнение имеет следующее решение  .
Пример 2. Требуется найти целое решение уравнения 15x + 37y = 1.

1-й метод. Воспользуемся разложением единицы:

1 = 15*5 + 37*(-2).Ответ:  x = 5, y = -2.

2-й метод. Применяя алгоритм Евклида, имеем: 37 = 15*2 + 7, 15 = 2*7 + 1. Отсюда    1 = 15 – 2*7 = 15 – 2(37 – 15*2) = 15*5 + (-2)*37. Тогда  x_о = 5, y_о = - 2. Общее решение уравнения есть система .
Пример 3. В уравнении 16x + 34y = 7, НОД (16, 34) = 2  и 7 не делится на 2,то нет целых решений.  [5]

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

Одним из применений алгоритма Евклида является представление дроби  в виде  

 
Где q
₁ – целое число, а q
₂, … ,q_n – натуральные числа. Такое выражение на­зывается цепной (конечной непрерывной) дробью.

Уравнение:



с взаимно простыми коэффициентами a
и b
имеет решение

,  ,

где  - предпоследняя подходящая дробь к цепной дроби , в которую раскладывается дробь .

Доказательство:
Если для заданной цепной дроби с последовательными частными q₁, q₂,…,q_n несократимые дроби

, , …,

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

, , …, n.

При k
=
n получаем :

,

Где  - последняя подходящая дробь к цепной дроби, в которую раскладывается дробь . Так как дроби  и  несократимы, то ,  и

.

Умножая обе части последнего равенства на (-1)ⁿ, имеем

,

То есть пара чисел ,  , где n-порядок цепной дроби, является решением уравнения .

Пример.  Для перевозки большого количества контейнеров по 170 кг и по 190 кг выделены трехтонные машины. Можно ли ими загружать машины полно­стью?

Решение:

 Пусть х и у количество контейнеров по 170 и 190 кг соответственно, тогда имеем уравнение

170х+190у=3000

После сокращения на 10 уравнение выглядит так,

17х+19у=300.

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



Свернув предпоследнюю подходящую к ней дробь в обыкновенную



Частное решение данного уравнения имеет вид

х₀= (-1)⁴300*9=2700,  у₀=(-1)⁵300*8=-2400,

а общее задается формулой

х=2700-19k,       y= -2400+17k.

откуда получаем условие на параметр k



Т.е. k=142, x=2,  y=14. .[6]
2.3 Метод разложения на множители

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

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

x + y = xy.

Решение. Запишем уравнение в виде

(x - 1)(y - 1) = 1.

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

с решениями (0,0) и (2,2).
2.4 Использование четности
Задача 2. Решить в простых числах уравнение

x2 - 2y2 = 1.

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

a) Пусть x - нечетное число. Подстановка x = 2t + 1 приводит исходное уравне­ние к виду

(2t + 1)² - 2y² = 1,

или

2y² = 4t(t + 1).

Следовательно, 2 | y². Так как y - простое число, то y = 2. Отсюда

b) Пусть x - четное число. Так как x - простое число, то x = 2. Следовательно,  т. е. уравнение неразрешимо в простых числах.

Следовательно, уравнение имеет в классе простых чисел единственное реше­ние (3;2).   
2.5 Другие методы решения диофантовых уравнений
Задача 3. Доказать, что уравнение

x2 - 2y2 = 1

имеет бесконечно много решений в натуральных числах.

Решение. Нетрудно заметить, что (3,2) - одно из решений исходного уравне­ния. С другой стороны из тождества

(x² + 2y²)² - 2(2xy)² = (x² - 2y²)²

следует, что если (x, y) - решение  данного уравнения, то пара (x² + 2y² , 2xy) также явля­ется его решением. Используя этот факт, рекуррентно определим бесконеч­ную последовательность (x_n , y_n) различных решений исходного уравнения:

(x₁ , y₁) = (3,2)   и   x_n+1 = x_n² + 2y_n²,     y_n+1 = 2x_ny_n,     n Î N^*.
Задача 4. Доказать, что уравнение

x(x + 1) = 4y(y + 1)

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

Решение. Нетрудно заметить, что исходное уравнение равносильно уравнению

x² + x + 1 = (2y + 1)².

Следовательно, x² < (2y + 1)² < (x + 1)² или x < 2y + 1 < x + 1. Полученное противо­речие доказывает требуемое утверждение.
Задача 5. Решить в целых числах уравнение

x + y = x² - xy + y².

Решение. Положим t = x + y. Так как



то должно выполняться неравенство     откуда t Î [0;4]. [7]
Заключение:
Современное обозначение непрерывных дробей предложил выдающийся учёный Христиан Гюйгенс (1629-1695).

К цепным дробям Гюйгенс обратился при построении планетария в Париже. Он хотел получить наилучшее приближение для отношения периодов обращения планет. Эти отношения и отношения чисел зубцов соответствующих связанных между собой шестерён планетария должны были совпадать. Но числа зубцов шестерен по техническим причинам не могут быть очень большими. Необходимо было так их подобрать, чтобы полученные отношения как можно меньше отличались от истинных. Гюйгенс обратился к цепным дробям и с их помощью нашел решение стоящей перед ним задачи.

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

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

Для начала выберем пять случайных решений: 1=< a,b,c,d=<30. Вообще го­воря, мы можем использовать меньшее ограничение для a,b,c,d.

Хромосома	(a,b,c,d)
1	(1, 28, 15, 3)
2	(14, 9, 2, 4)
3	(13, 5, 7, 3)
4	(23, 8, 16, 19)
5	(9, 13, 5, 2)

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

Главное свойство диофантовых уравнений в том, что мы не перебираем все варианты решений подряд,  а приближаемся от случайно выбранных решений к лучшим. [8]
Список  литературы
1.     Журнал «Квант» 1970г. №7

2.     «Энциклопедия юного математика» 520 с.

3.     Виленкин Н.Я. «За страницами учебника математики» (10-11 класс).- Москва:          «Просвещение» 1996-320 с.

4.     http://festival.1september.ru/articles/417558/

5.     Шыныбеков Н.А. «Алгебра 8» Алматы «Атамұра» 2004-272 с.

6.     И.Н.Сергеев «Примени математику» 1989г.- 240 с.

7.     math.ournet.md

8.     http://ilib.mirror1.mccme.ru/djvu/serp-int_eq.htm

9.     Кожегельдинов С.Ш. «Некоторые элементы теории диофантовых уравнений в упражнениях и задачах»

10.  Пичугин Л.Ф. «За страницами учебника алгебры»,  М., 1990г., 224с.

11.  Глейзер Г.И. «История математики в школе 10-11»,  351с

12.  Гусев В.А., Орлов А.И. и др. «Внеклассная работа по математике в 6-8 классах»,  М., 1984г., 286 с.

13.  Петраков И.А. «Математика для любознательных»,  М., 2000г. 256с.

14. http://bse.sci-lib.com/article028554.html

15. http://bars-minsk.narod.ru/teachers/diofant.html


Приложение

1.     Решить в целых числах уравнение 127x - 52y + 1 = 0. Ответ: x = 9 + 52t,   y = 22 + 127t,   t Î Z.

2.     Решить в целых числах уравнение  107х + 84у = 1.

3.     Решить в целых числах уравнение  3x² + 4xy - 7y² = 13. Указание. Применить разложение на множители.
Ответ: (2,1), (-2,-1).

4.     Доказать, что уравнение  y² = 5x² + 6 не имеет целочисленных решений.
Указание. Рассмотреть уравнение по модулю 4.

5.     Доказать, что уравнение  x² - 3y² = 1 имеет бесконечно много решений в целых числах.
Указание. Использовать реккурентное соотношение между решениями.

6.     Решить уравнение: 17х +13у=5.

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

8.     Требуется разлить 20,5 литра сока в банки по 0,7 литра и 0,9 литра так, чтобы все банки оказались полными. Сколько каких банок надо заготовить? Какое наименьшее количество банок при этом может понадобиться?