Методы решения диофантовых уравнений

Муниципальное бюджетное общеобразовательное учреждение
средняя общеобразовательная школа №1
г. Павлово.








Научно-исследовательская работа
Методы решения диофантовых уравнений.

Отделение: физико-математическое
Секция: математика
Выполнил:
ученик 8 А класса Трухин Николай (14 лет)

Научный руководитель:
учитель математики
Лефанова Н. А.





г. Павлово
2013 г.



Оглавление

I Введение3
II Обзор литературы....5
III Основная часть6
IV Заключение...15
V Список литературы16
VI Приложение..17



































Введение.

В 2011-2012 году я выполнял исследовательскую работу на тему: «Решение уравнений в Древней Греции и Индии». При работе над ней я познакомился с трудами Диофанта Александрийского и Мухаммеда аль - Хорезми. В своей прошлой работе я рассмотрел некоторые способы решения уравнений первой степени с двумя неизвестными, познакомился с некоторыми старинными задачами, приводящими к решению уравнений первой степени с двумя неизвестными.
Мухаммед Бен Мусса аль – Хорезми, - или Магомед сын Моисея Хорезмского, состоящий членом «дома мудрости» в Иране, около 820 года нашего летоисчисления написал книгу, где учил решать простые и сложные вопросы арифметики, которые необходимы людям при дележе наследства, составлении завещаний, разделе имущества и судебных делах, в торговле, всевозможных сделках. С именем аль – Хорезми связаны понятия «алгебра», «арабские цифры», «алгоритм». Он отделил алгебру от геометрии, внёс большой вклад в математику исламского средневековья. Мухаммед аль – Хорезми был известен и уважаем, как при жизни, так и после смерти.
Но мне захотелось больше узнать о Диофанте. И тема моего исследования в этом году: «Методы решения диофантовых уравнений»
Диофант Александрийский - один из самых своеобразных древнегреческих математиков, труды которого имели большое значение для алгебры и теории чисел. Из работ Диофанта самой важной является «Арифметика», из 13 книг которой, только 6 сохранились до наших дней. В сохранившихся книгах содержится 189 задач с решениями. В первой книги изложены задачи, приводящиеся к определенным уравнениям первой и второй степени. Остальные пять книг содержат в основном неопределенные уравнения (неопределенными называются уравнения, содержащие более чем одно неизвестное). В этих книгах ещё нет систематической теории неопределённых уравнений, методы решения меняются от случая к случаю. Диофант довольствуется одним решением, целым или дробным, лишь бы оно было положительным. Тем не менее, методы решения неопределённых уравнений, составляют основной вклад Диофанта в математику. В символике Диофанта был один только знак для неизвестного. Решая неопределённые уравнения, он применял в качестве нескольких неизвестных произвольные числа, вместо которых можно было взять и любые другие, что и сохраняло характер общности его решений.
Цель моей работы:
1.Продолжить знакомство с диофантовыми уравнениями.
2.Исследовать методы перебора и рассеивания (измельчения) при решении диофантовых уравнений.
3.Исследовать возможность применения диофантовых уравнений для решения некоторых практических задач.


















II. Обзор литературы.
При написании работы мной использовалась следующая литература:
Г. И. Глейзер «История математики в школе» М.: изд. «Просвещение» 1964г. 376с.
Автор этого издания рассказывает об истории математики. Книга повествует о математиках Древней Греции, Рима, Индия, Китая и. т. д.
Мной использована информация о Диофанте и аль – Хорезми.
И. Г. Башмакова «Диофант и диофантовы уравнения» М.: изд. «Наука» 1972г. 68с.
Книга посвящена методам Диофанта при решении неопределённых уравнений. В ней рассказывается о жизни и самого Диофанта. Эта информация использована мной в работе.
В. А. Никифоровский «В мире уравнений» М.: изд. «Наука» 1987г. 176с.
В книги рассказывается об истории алгебры с древних времён. Я использовал информацию о теории уравнений, начиная с древности.
А. П. Савин «Энциклопедический словарь юного математика» М.: изд. «Педагогика» 1985г.
В этой книге собрано около 200 статей, посвященных основным понятиям математики и её приложения. Мной были использованы материалы статей «Алгебра», «Уравнения», «Диофантовы уравнения»
Г. М. Возняк, В. Ф. Гусев «Прикладные задачи на экстремумы» М.: изд. «Просвещение» 1985г. 144с.
Из книги взяты тексты задач для практического использования.
По теме мной использовался сайт:
[ Cкачайте файл, чтобы посмотреть ссылку ] (информация об аль – Хорезми и Диофанте. О методах решения диофантовых уравнений).




Основная часть
В наши дни каждый, кто занимался математикой, слышал о диофантовых уравнениях. Алгебраические уравнения с целыми коэффициентами, решаемые во множестве целых (реже рациональных) чисел, вошли в историю математики как диофантовы. Наиболее изучены диофантовы уравнения 1 и 2 степени. В содержании моей работы включены задачи, которые сводятся к решению уравнения первой степени с двумя неизвестными
13 EMBED Equation.3 1415 (1)
Рассмотрим задачу.
Задача 1. В клетке находится x фазанов и у кроликов. Сколько в клетке фазанов и кроликов, если общее количество ног равно 62.
Общее число ног можно записать с помощью уравнения 2х+4у=62 (2)
Это равенство, которое я составил по условию задачи, называют уравнением с двумя переменными. Данное уравнение называют линейным уравнением. Линейные уравнения играют важную роль при решении различных задач. Напомню основные положения, связанные с этим понятием.
Линейным уравнением с двумя переменными называется уравнение вида ax+by=c, где x и у – переменные, а, b и с – некоторые числа.
Однозначно определить из уравнения (2) значения x и y нельзя. Даже если ограничиться только натуральными значениями переменных, здесь могут быть такие случаи: 1 и 15, 3 и 14, 5 и 13 и т. д.
Пара чисел (a, b) называется решением уравнения с двумя переменными, если при замене x на а и y на b получаем истинное равенство.
Каждому уравнению с двумя переменными соответствует множество его решений, т. е. множество, состоящее из всех пар чисел (a, b), при подстановке которых в уравнение получается истинное равенство. При этом, конечно, если заранее указаны множества Х и Y, которые могут принимать неизвестные x и у, то надо брать лишь такие пары (a, b), для которых а принадлежит Х и b принадлежит Y.
Пару чисел (a, b) можно изобразить на плоскости точкой М, имеющей координаты а и b, М= М (a, b). Рассматривая изображения всех точек множества решений уравнения с двумя неизвестными, получим некоторое подмножество плоскости. Его называют графиком уравнения.
Можно доказать, что графиком линейного уравнения с двумя переменными, в котором хотя бы один из коэффициентов не равен нулю, является прямая линия. Для построения графика этого уравнения достаточно взять две точки с координатами и провести через них прямую. Графический метод решения я использовал в предыдущей работе.
Два уравнения с двумя переменными, имеющие одни и те же решения называются равносильными.
Например, равносильны уравнения х+2у=5 и 3х+6у=15 – любая пара чисел, удовлетворяющая одному из этих уравнений, удовлетворяет и второму.
Уравнения с двумя переменными обладают такими же свойствами, как и уравнения с одной переменной:
1) если в уравнении перенести слагаемое из одной части в другую, изменив его знак, то получится уравнение, равносильное данному;
2) если обе части уравнения умножить или разделить на одно и то же отличное от нуля число, то получится уравнение, равносильное данному.
Существует несколько способов решения диофантовых уравнений:
Метод перебора вариантов
Использование алгоритма Евклида
С использованием цепной дроби
Метод рассеивания (измельчения)
При помощи программирования на языке программирования Паскаль
В своей работе я исследовал методы – перебор вариантов и рассеивание (измельчения)
Рассматривая способ перебора вариантов, необходимо учитывать количество возможных решений уравнения. Например, этот способ можно применить, решая следующую задачу:
Задача 2 . Андрей работает летом в кафе. За каждый час ему платят 10 р. И высчитывают 2 р. за каждую разбитую тарелку. На прошедшей неделе он заработал 180 р. Определите, сколько часов он работал и сколько разбил тарелок, если известно, что он работает не более 3 ч в день.
Решение.
Пусть x часов он всего работал в неделю, тогда 10х р. ему заплатили, но он разбил у тарелок, и с него вычли 2у р. Имеем уравнение 10х – 2у =180, причем x меньше или равен 21. Получим: 5х-у=90, 5х=90+у, х=18+у:5.
Так как x целое число, то у должно нацело делится на 5, чтобы в правой части получилось целое число. Возможны четыре случая
у=0, х=18, т. е. решением является пара – (18, 0);
у=5, х=19, (19, 5);
у=10, х=20, (20, 10);
у=15, х=21, (21, 15).
Эту задачу я решил, используя способ перебора вариантов. Ответ содержит четыре возможных варианта. Я попробовал решить этим способом ещё несколько задач.
Задача 3. Из двухрублевых и пятирублевых монет составлена сумма в 23 рубля. Сколько среди этих монет двухрублевых?
Решение.
Пусть x – количество двухрублевых монет, у – количество пятирублевых монет. Составим и решим уравнение: 2х+5у=23; 2х=23–5у; x = (23 – 5у):2; x =(22+1 – 5у):2, почленно поделим 22 на 2 и (1 – 5у) на 2, получим: x = 11 + (1 – 5у):2.
Так как x и y натуральные числа по условию задачи, то левая часть уравнения есть натуральное число, значит, и правая часть должна быть натуральным числом. К тому же, чтобы получить в правой части число натуральное, нужно чтобы выражение (1 – 5у) нацело делилось на 2. Осуществим перебор вариантов.
y=1, х=9, то есть двухрублевых монет может быть 9;
у=2, при этом выражение (1 – 5у) не делится нацело на 2;
у=3, х=4, то есть двухрублевых монет может быть 4;
при у больше или равном 4 значение x не является числом натуральным.
Таким образом, ответ в задаче следующий: среди монет 9 или 4 двухрублевых.

Задача 4. Шехерезада рассказывает свои сказки великому правителю. Всего она должна рассказать 1001 сказку. Сколько ночей потребуется Шехерезаде, чтобы рассказать все свои сказки, если x ночей она будет рассказывать по 3 сказки, а остальные сказки по 5 за у ночей
Решение.
Сказочнице потребуется x + у ночей, где x и у – натуральные корни уравнения 3х+5у=1001
x = (1001 – 5у):3; так как x – натуральное число, то и в правой части равенства также должно быть натуральное число, а значит выражение (1001 – 5у) должно нацело делиться на 3.
Осуществим перебор вариантов.
у=1, 1001 – 5у=1001-5= 996, 996 делится на 3, следовательно, х=332; решение (332;1);
у=2, 1001– 10=991, 991 не делится на 3;
у=3, 1001 – 15 = 986; 986 не делится на3;
у =4, 1001 – 20 = 981, 981 делится на 3, следовательно, x = 327, решение (327;4) и т. д.
В этой задаче существует 67 пар возможных корней, я не стал показывать все решения данной задачи, т. к. это занимает много времени.
Уравнение ax+by=c (1) в приведённых задачах я решал способом перебора вариантов. Я уяснил для себя, что способ перебора вариантов не всегда эффективен для решения данной задач, так как для нахождения всех решений уравнения требуются значительные временные затраты. И, на мой взгляд, в настоящее время он неактуален.
Поэтому я решил задачу про Шехерезаду, используя метод рассеивания (измельчения).
Метод рассеивания – это общий метод для решения в целых числах неопределённых уравнений первой степени с целыми коэффициентами.
Итак, решим задачу про Шехерезаду методом рассеивания:
Обратимся к уравнению 3х + 5у = 1001.
Перепишем его иначе: 3х= 1001- 5у; 3х= 1001 - 2у - 3у;
x = – y + 13 EMBED Equation.3 1415 и обозначим xl = у + x
В результате уравнение примет вид 3х1 = 1001 – 2у или
у = –xl 13 EMBED Equation.3 1415.
Если вновь произвести замену у1 = у + х1, то придем к уравнению
x1 + 2у1 = 1001. Заметим, что коэффициенты при неизвестных уменьшились измельчились.
Здесь коэффициент при x1, равен 1, а поэтому при любом целом у1 = t число х1 тоже целое. Остается выразить исходные переменные через t:
х1 = 1001 – 2 t, следовательно, у = – 1001 + 3 t , а x = 2002 – 5 t. Итак, получаем бесконечную последовательность (2002 – 5 t , – 1001 + 3 t) целочисленных решений. Внешний вид формул для нахождения значений переменных отличается от решений, полученных ранее, но с учетом условия задачи, корни получаются те же самые. Так, пара (332;1) получается при t =334.
На мой взгляд, этот метод не только более удобный (у него есть алгоритм действий), но и интересный. Известно, что этот метод впервые применил в начале VI в. индийский математик Ариабхатта.
В прошлом году я показывал решение древней индийской задачи Брахмагупты методам рассеивания, которое предложил сам Брахмагупта. Решение было нерациональным.
Оно представлено ниже:
«Найти два целых числа, зная, что разность произведений первого на 19 и второго на 8 равно 13. »
В задаче требуется найти все целые решения уравнений.
Решение:
(1) 19x – 8y = 13
Выражаю y – неизвестное с наименьшим по абсолютной величине коэффициентом через x, получаю:
(2) y = (19x – 13)/8
Нужно теперь узнать, при каких целых значениях x соответствующие значения y являются тоже целыми числами. Перепишу уравнение (2) следующим образом:
(3) y = 2x + (3x – 13)/8
Из (3) следует, что y при целом x принимает целое значение только в том случае, если выражение (3x -13)/8 является целым числом, скажем y1. Полагая
(4) (3x- 13)/8 = y1,
вопрос сводится к решению в целых числах уравнения (4) с двумя неизвестными x и y1; его можно записать так:
(5) 3x – 8y1 = 13.
Это уравнение имеет по сравнению с первоначальным (1) преимущество, что 3 – наименьшее из абсолютных величин коэффициентов при неизвестных – меньше, чем в (1), т.е. 8. Это было достигнуто благодаря тому, что коэффициент при x (19) был заменен остатком от деления на 8.
Продолжая тем же способом, мы получим из (5):
(6) x = (8y1+13)/3 = 2y1 + (2y1 + 13)/3.
Итак, неизвестное x при целом y1 только тогда принимает целые значения, когда (2y1 + 13)/3 есть целое число, скажем y2:
(7) (2y1 + 1)/3 = y2,
или
(8) 3y2 – 2y1 = 13.
Далее,
(9) y1 = (3y2 - 13)/2 = y2 + (y2 - 13)/2
Полагая
(10) (y2 - 13)/2 = y3,
получаю
(11) y2 – 2y3 = 13.
Это самое простое из всех рассмотренных неопределенных уравнений, так как один из коэффициентов равен 1.
Из (11) получаю:
(12) y2 = 2y3 + 13.
Отсюда видно, что y2 принимают целые значения при любых целых значениях y3. Из равенств (6), (9), (12), (3) путем последовательных подстановок можно найти следующие выражения для неизвестных x и y уравнения (1):
x = 2y1 + y2 = 2(y2 + y3) + y2 = 3y2 + 2y3 = 3(2y2 + 13) + 2y3 = 8y3 + 39;
у = 2x + y1 = 2(8y3 + 39) + y2 + y3 = 19y3 +91.
Таким образом, формулы
x = 8y3 + 39,
y = 19y3 + 91.
При y3 = 0, +1,+2, +3, дают все целые решения уравнения (1).
В следующей таблице приведены примеры таких решений.



Таблица 1.
y3
-4
3
-2
-1
0
1
2
3
4

x
7
15
23
31
39
47
55
63
71

y
15
34
53
72
91
110
129
148
167


Решим эту задачу рационально. В решении используется определённый алгоритм.
Задача 5.
Найти два числа, если разность произведений первого на 19 и второго на 8 равна 13.
Решение. Требуется решить уравнение 19х 8у = 13
Перепишем его иначе: 8y=19x–13; 8y=16x+3x–13; у = 2х + 13 EMBED Equation.3 1415
и обозначим y1 = у 2х.
В результате уравнение примет вид 8у1 = Зx 13 или x= 2y113 EMBED Equation.3 1415.
Если вновь произвести замену х1 = x 2у1, то придем к уравнению
3xl 2у1 = 13.
Коэффициенты при неизвестных уменьшились измельчились. Дальнейшее измельчение: y1 = xl +13 EMBED Equation.3 1415, то получим у2 =у1 –х1.
В результате последнее уравнение преобразуется к виду х1 2у2: = 13. Здесь коэффициент при х1, равен 1, а поэтому при любом целом у2 = t число х1 тоже целое.
Остается выразить исходные переменные через t:
вначале выразим х1=2t+13, y1 = 3t+13; а затем x = 8 t +39, y= 19 t + 91.
Итак, получаем бесконечную последовательность (39 + 8 t, 91 + 19 t) целочисленных решений. Уравнение ax+by=c (1) в приведённых задачах я решал способом рассеивания (измельчения).
























IV. Заключение.
Изучая диофантовы уравнения для их решения, я использовал методы перебора вариантов и рассеивания (измельчения). Этими методами я решал, как современные, так и древние задачи. В содержании моей работы были включены задачи, которые сводятся к решению уравнений первой степени с двумя переменными ах+bу=с (1)
В ходе своей работы я сделал выводы:
Метод перебора требует значительные временные затраты, а значит он не очень удобен и рационален.
Более рациональным, на мой взгляд, является метод рассеивания. Когда я решал старинную индийскую задачу этим методом, я понял, что существует определённый алгоритм решения. Мне было достаточно полученных в школе знаний. Я убедился, что методы решения дофантовых уравнений с развитием математики постоянно совершенствуются.
На следующий год я хочу продолжить изучение методов решения диофантовых уравнений.















V. Список литературы
Г. И. Глейзер «История математики в школе» М.: изд. «Просвещение» 1964г. 376с.
И. Г. Башмакова «Диофант и диофантовы уравнения» М.: изд. «Наука» 1972г. 68с.
В. А. Никифоровский «В мире уравнений» М.: изд. «Наука» 1987г. 176с.
А. П. Савин «Энциклопедический словарь юного математика» М.: изд. «Педагогика» 1985г.
Г. М. Возняк, В. Ф. Гусев «Прикладные задачи на экстремумы» М.: изд. «Просвещение» 1985г. 144с.
[ Cкачайте файл, чтобы посмотреть ссылку ]




























VI. Приложение.
На фермерском хозяйстве нужно провести водопровод длиной 167м. Имеются трубы длиной 5м и 7м. Сколько нужно использовать тех и других труб, чтобы сделать наименьшее количество соединений (трубы не резать)?
Учитывая, что количество как одних, так и других труб может изменяться, количество 7 – метровые трубы обозначаем через х, 5 – метровые – через у
Тогда 7х – длина 7 – метровых труб, 5у – длина 5 – метровых труб.
Отсюда получаем неопределённое уравнение:
7х+5у=167
Выпазив, например, переменную у через переменную х, получим:
13 EMBED Equation.3 1415

Методом перебора легко найти соответствующие пары значений х и у, которые удовлетворяют уравнению 7х+5у=167

(1;32), (6;25), (11;18), (16;11), (21;4).

Из этих решений наиболее выгодное последнее, т. е. х=21; у=4.

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

2. Пусть сумма произведений, о которых идёт речь, равна 330. Найти дату рождения.
Решим неопределённое уравнение
12х + 31у = 330.
С помощью метода рассеивания получим:
х = 43 – 31у4,
у = 6 – 12у4.
Ввиду ограничений, легко констатировать, что единственным решением является
у4 = 1, х = 12, у = 6.
Итак, дата рождения: 12-е число 6-го месяца, т.е. 12 июня.









13PAGE 15


13PAGE 141715