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

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

г. Павлово.

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

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

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

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

Выполнил:

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

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

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

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

г. Павлово

2013 г.

Оглавление

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

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

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

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

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

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

I.       Введение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

          В наши дни каждый, кто занимался  математикой, слышал о диофантовых уравнениях. Алгебраические уравнения с целыми коэффициентами, решаемые во множестве целых (реже рациональных) чисел, вошли в историю математики как диофантовы. Наиболее изучены диофантовы уравнения 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х р. ему заплатили, но он разбил у тарелок, и с него вычли 2у р. Имеем уравнение 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 +        и обозначим x_l = у + x

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

у =  –x_{l .}

 Если вновь произвести замену у₁ = у + х₁, то придем к уравнению

x₁ + 2у₁ = 1001. Заметим, что коэффициенты при неизвестных уменьшились — измельчились.

 Здесь коэффициент при x₁, равен 1, а поэтому при любом целом у₁ = t число х₁ тоже целое. Остается выразить исходные переменные через t:

 х₁ = 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 является целым числом, скажем y₁. Полагая

(4) (3x- 13)/8 = y₁,

вопрос сводится к решению в целых числах уравнения (4) с двумя неизвестными x и y₁; его можно записать так:

(5) 3x – 8y₁ = 13.

Это уравнение имеет по сравнению с первоначальным (1) преимущество, что 3 – наименьшее из абсолютных величин коэффициентов при неизвестных – меньше, чем в (1), т.е. 8. Это было достигнуто благодаря тому, что коэффициент при x (19) был заменен остатком от деления на 8.

Продолжая тем же способом, мы получим из (5):

 (6)  x = (8y₁+13)/3 = 2y₁  + (2y₁ + 13)/3.

Итак, неизвестное x при целом y₁ только тогда принимает целые значения, когда (2y₁ + 13)/3 есть целое число, скажем y₂:

(7)  (2y₁ + 1)/3 = y₂,

или

(8) 3y₂ – 2y₁  = 13.

Далее,

(9) y₁ = (3y₂  - 13)/2 = y₂ + (y₂ - 13)/2

Полагая

(10) (y₂ - 13)/2 = y₃,

получаю

(11) y₂ – 2y₃ = 13.

Это самое простое из всех рассмотренных неопределенных уравнений, так как один из коэффициентов равен 1.

Из (11) получаю:

(12) y₂ = 2y₃ + 13.

Отсюда видно, что y₂ принимают целые значения при любых целых значениях y₃. Из равенств (6), (9), (12), (3) путем последовательных подстановок можно найти следующие выражения для неизвестных x и y уравнения (1):

x = 2y₁ + y₂ = 2(y₂ + y₃) + y₂ = 3y₂ + 2y₃ = 3(2y₂ + 13) + 2y₃ = 8y₃ + 39;

у = 2x + y₁ = 2(8y₃ + 39) + y₂ + y₃ = 19y₃ +91.

Таким образом, формулы

x = 8y₃ + 39,

y = 19y₃ + 91.

При y₃ = 0, +1,+2, +3, … дают все целые решения уравнения (1).

  В следующей таблице приведены примеры таких решений.

Таблица 1.

Решим эту задачу  рационально. В решении используется определённый алгоритм.

Задача 5.

Найти два числа, если разность произведений первого на 19 и второго  на 8 равна 13.

Решение.   Требуется решить уравнение 19х — 8у = 13

Перепишем его иначе:   8y=19x–13;   8y=16x+3x–13;   у = 2х +         

и обозначим y₁ = у — 2х.

В результате уравнение примет вид 8у₁ = Зx — 13 или x= 2y_1.

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

3x_l — 2у₁ = 13.

Коэффициенты при неизвестных уменьшились — измельчились.  Дальнейшее измельчение:  y₁ = x_l +, то получим  у₂ =у₁ –х₁.

В результате последнее уравнение преобразуется к виду х₁ — 2у₂^: = 13. Здесь коэффициент при х₁, равен 1, а поэтому при любом целом у₂ = t число х₁ тоже целое.

Остается выразить исходные переменные через t:

вначале выразим х₁=2t+13,  y₁ = 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.                       http://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у₄,

у = 6 – 12у₄.

Ввиду ограничений, легко констатировать, что единственным решением является

у₄ = 1, х = 12, у = 6.

Итак, дата рождения: 12-е число 6-го месяца, т.е. 12 июня.