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

Необходимость решения различного типа уравнений возникает у человека не только в школе на уроках математики, но и в повседневной жизни. Нам часто приходится находить что-то неизвестное по заданным известным величинам. Необходимость решать уравнения возникла уже в древнем мире при дележе наследства, составлении завещаний, разделе имущества и судебных делах, в торговле, всевозможных сделках. Но способы решения равнений были громоздки и неудобны. С развитием математики эти приемы совершенствовались... Учебно-исследовательскую работу можно рекомендовать для дальнейшего участия в научно–практической конференции «Одиссея разума».
Раздел Математика
Класс -
Тип Другие методич. материалы
Автор
Дата
Формат doc
Изображения Есть
For-Teacher.ru - все для учителя
Поделитесь с коллегами:

Муниципальное бюджетное общеобразовательное учреждение

средняя общеобразовательная школа №1

г. Павлово.









Научно-исследовательская работа

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


Отделение: физико-математическое

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

Выполнил:

ученик 8 А класса Трухин Николай (14 лет)

Научный руководитель:

учитель математики

Лефанова Н. А.


г. Павлово

2013 г.

Оглавление

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

II Обзор литературы……………………………………………………………....5

III Основная часть…………………………………………………………………6

IV Заключение…………………………………………………………………...15

V Список литературы……………………………………………………………16

VI Приложение…………………………………………………………………..17










  1. Введение.


В 2011-2012 году я выполнял исследовательскую работу на тему: «Решение уравнений в Древней Греции и Индии». При работе над ней я познакомился с трудами Диофанта Александрийского и Мухаммеда аль - Хорезми. В своей прошлой работе я рассмотрел некоторые способы решения уравнений первой степени с двумя неизвестными, познакомился с некоторыми старинными задачами, приводящими к решению уравнений первой степени с двумя неизвестными.

Мухаммед Бен Мусса аль - Хорезми, - или Магомед сын Моисея Хорезмского, состоящий членом «дома мудрости» в Иране, около 820 года нашего летоисчисления написал книгу, где учил решать простые и сложные вопросы арифметики, которые необходимы людям при дележе наследства, составлении завещаний, разделе имущества и судебных делах, в торговле, всевозможных сделках. С именем аль - Хорезми связаны понятия «алгебра», «арабские цифры», «алгоритм». Он отделил алгебру от геометрии, внёс большой вклад в математику исламского средневековья. Мухаммед аль - Хорезми был известен и уважаем, как при жизни, так и после смерти.

Но мне захотелось больше узнать о Диофанте. И тема моего исследования в этом году: «Методы решения диофантовых уравнений»

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

Цель моей работы:

1.Продолжить знакомство с диофантовыми уравнениями.

2.Исследовать методы перебора и рассеивания (измельчения) при решении диофантовых уравнений.

3.Исследовать возможность применения диофантовых уравнений для решения некоторых практических задач.







II. Обзор литературы.

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

  1. Г. И. Глейзер «История математики в школе» М.: изд. «Просвещение» 1964г. 376с.

Автор этого издания рассказывает об истории математики. Книга повествует о математиках Древней Греции, Рима, Индия, Китая и. т. д.

Мной использована информация о Диофанте и аль - Хорезми.

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

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

  1. В. А. Никифоровский «В мире уравнений» М.: изд. «Наука» 1987г. 176с.

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

  1. А. П. Савин «Энциклопедический словарь юного математика» М.: изд. «Педагогика» 1985г.

В этой книге собрано около 200 статей, посвященных основным понятиям математики и её приложения. Мной были использованы материалы статей «Алгебра», «Уравнения», «Диофантовы уравнения»

  1. Г. М. Возняк, В. Ф. Гусев «Прикладные задачи на экстремумы» М.: изд. «Просвещение» 1985г. 144с.

Из книги взяты тексты задач для практического использования.

  1. По теме мной использовался сайт:

ru.wikipedia.org (информация об аль - Хорезми и Диофанте. О методах решения диофантовых уравнений).



  1. Основная часть

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

Методы решения диофантовых уравнений(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) если обе части уравнения умножить или разделить на одно и то же отличное от нуля число, то получится уравнение, равносильное данному.

Существует несколько способов решения диофантовых уравнений:

  1. Метод перебора вариантов

  2. Использование алгоритма Евклида

  3. С использованием цепной дроби

  4. Метод рассеивания (измельчения)

  5. При помощи программирования на языке программирования Паскаль

В своей работе я исследовал методы - перебор вариантов и рассеивание (измельчения)

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

Задача 2 . Андрей работает летом в кафе. За каждый час ему платят 10 р. И высчитывают 2 р. за каждую разбитую тарелку. На прошедшей неделе он заработал 180 р. Определите, сколько часов он работал и сколько разбил тарелок, если известно, что он работает не более 3 ч в день.

Решение.

Пусть x часов он всего работал в неделю, тогда 10х р. ему заплатили, но он разбил у тарелок, и с него вычли р. Имеем уравнение 10х - 2у =180, причем x меньше или равен 21. Получим: 5х-у=90, 5х=90+у, х=18+у:5.

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

  1. у=0, х=18, т. е. решением является пара - (18, 0);

  2. у=5, х=19, (19, 5);

  3. у=10, х=20, (20, 10);

  4. у=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. Осуществим перебор вариантов.

  1. y=1, х=9, то есть двухрублевых монет может быть 9;

  2. у=2, при этом выражение (1 - 5у) не делится нацело на 2;

  3. у=3, х=4, то есть двухрублевых монет может быть 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 + Методы решения диофантовых уравненийи обозначим xl = у + x

В результате уравнение примет вид 3х1 = 1001 - 2у или

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

Если вновь произвести замену у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х + Методы решения диофантовых уравнений

и обозначим y1 = у - 2х.

В результате уравнение примет вид 8у1 = Зx - 13 или x= 2y1Методы решения диофантовых уравнений.

Если вновь произвести замену х1 = x - 2у1, то придем к уравнению

3xl - 2у1 = 13.

Коэффициенты при неизвестных уменьшились - измельчились. Дальнейшее измельчение: y1 = xl +Методы решения диофантовых уравнений, то получим у211.

В результате последнее уравнение преобразуется к виду х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)

В ходе своей работы я сделал выводы:

  1. Метод перебора требует значительные временные затраты, а значит он не очень удобен и рационален.

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

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









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

  1. Г. И. Глейзер «История математики в школе» М.: изд. «Просвещение» 1964г. 376с.

  2. И. Г. Башмакова «Диофант и диофантовы уравнения» М.: изд. «Наука» 1972г. 68с.

  3. В. А. Никифоровский «В мире уравнений» М.: изд. «Наука» 1987г. 176с.

  4. А. П. Савин «Энциклопедический словарь юного математика» М.: изд. «Педагогика» 1985г.

  5. Г. М. Возняк, В. Ф. Гусев «Прикладные задачи на экстремумы» М.: изд. «Просвещение» 1985г. 144с.

  6. ru.wikipedia.org










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

  1. На фермерском хозяйстве нужно провести водопровод длиной 167м. Имеются трубы длиной 5м и 7м. Сколько нужно использовать тех и других труб, чтобы сделать наименьшее количество соединений (трубы не резать)?

Учитывая, что количество как одних, так и других труб может изменяться, количество 7 - метровые трубы обозначаем через х, 5 - метровые - через у

Тогда 7х - длина 7 - метровых труб, 5у - длина 5 - метровых труб.

Отсюда получаем неопределённое уравнение:

7х+5у=167

Выпазив, например, переменную у через переменную х, получим:

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


Методом перебора легко найти соответствующие пары значений х и у, которые удовлетворяют уравнению 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 июня.


© 2010-2022