XIII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Цепные дроби и диофантовы уравнения
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
ВВЕДЕНИЕ
Актуальность исследования. Применение аппарата цепных дробей к прикладным задачам, в том числе олимпиадного характера, позволяет углубить математические знания, расширить кругозор и повысить мотивацию к изучению математики. Ведь задачи на оптимизацию, которых много в ЕГЭ, предполагают решение с помощью диофантовых уравнений; также в том пресловутом справочнике прозвучала мысль, что подход Диофанта к решению уравнений особенный, и мне хотелось бы поделиться умением решать диофантовы уравнения с другими. Я предполагаю, что элементы высшей математики могут быть доступны и интересны ученикам средней школы.
Объект исследования: цепные дроби и диофантовы уравнения.
Предмет исследования: применение последовательности подходящих дробей для решения диафантовых уравнений и других задач.
Цель исследования:
Обработка теоретического материала (его отбор, а также последовательное и доступное изложение);
Поиск областей применения цепных дробей;
Составление практического материала в форме упражнений.
Гипотеза исследования: применение цепных дробей позволяет найти один из способов решения диофантовых уравнений и других задач олимпиадного характера.
Задачи исследования:
Изучить понятие цепных дробей и диофантовых уравнений;
На примерах приближения различных чисел подходящими дробями (рациональные числа, квадратичные иррациональности) понять закономерности использования аппарата цепных дробей;
Ознакомиться с историей возникновения и использования цепных дробей;
Выявить и применить возможности цепных дробей к решению разных видов олимпиадных задач.
Практическая значимость.
Действительные числа однозначно отображаются цепными дробями. Основное значение такого изображения заключается в том, что, зная цепную дробь, изображающую действительное число, можно определить это число с достаточной точностью. Умение решать диофантовы уравнения может пригодиться в реальной жизни, например, задачи на оптимизацию, которые неоднократно встречаются в ЕГЭ; также данное умение окажется как нельзя кстати при решении задач, выходящих за рамки школьной программы, олимпиадных заданий.
Глава 1. Понятие цепных дробей.
Примеры разложений действительных чисел в цепную дробь.
Дробь можно записать в виде суммы целой части и правильной дроби: . Но , а дальше: . Значит, . Далее получим .
Продолжим этот процесс до тех пор, пока не придем к знаменателю . В результате мы представим обыкновенную дробь в виде:
Эйлер назвал дроби такого вида непрерывными. Приблизительно в то же время в Германии появился другой термин – цепная дробь. Так за этими дробями и сохранились оба названия. Ввиду громоздкости развернутой записи цепной дроби применяют компактную запись .
В качестве примера представим дробь в виде цепной дроби:.
Или в компактной форме: [1; 3, 2, 4 ].
Мы познакомились с разложением в цепную дробь обыкновенной дроби, т.е. рационального числа. Любое рациональное число представимо в виде конечной цепной дроби. Конечность следует из алгоритма Евклида. Но в виде цепной дроби можно записать любое действительное число. Только конечными цепными дробями здесь не обойтись. Приведем разложение в непрерывную дробь числа .
и т.д. Видна закономерность.
Таким образом,
Т.е. в компактной форме = [1: 2, 2, 2, 2, 2…].
Оказывается, квадратичные иррациональности (т.е. числа вида , где a, b, c - рациональные числа), и только они раскладываются в бесконечные периодические дроби. На этот факт впервые указал Эйлер, строгое его доказательство дал Лагранж.
Если оборвать дробь на знаменателе , то останется дробь . Обращая ее в обыкновенную, получим . Это выражение называют k-й подходящей дробью для исходной цепной дроби.
Например, для нашей дроби имеем:
нулевая подходящая дробь: ,
первая подходящая дробь: ,
вторая подходящая дробь: ,
третья подходящая дробь: . Она равна самому числу.
Для цепной дроби, представляющей число, имеем следующие подходящие дроби:
нулевая подходящая дробь: ,
первая подходящая дробь: ,
вторая подходящая дробь: ,
третья подходящая дробь: и т.д.
Подходящие дроби удобно вычислять с помощью специальной таблицы. Для этого посмотрим, как вычисляются подходящие дроби:
и т.д. Вообще имеют место рекуррентные соотношения
Рk+1= qk+1. Pk+Pk-1 и Qk+1= qk+1.Qk+Qk-1.
Эти вычисления удобно производить последующей схеме:
|
q |
- |
q0 |
… |
qk |
qk+1 |
… |
|||
|
P |
1 |
P0 |
P1 |
P2 |
… |
Pk-1 |
Pk |
Pk+1 |
… |
|
Q |
0 |
Q0 |
Q1 |
Q2 |
… |
Qk-1 |
Qk |
Qk+1 |
… |
В первой строке этой таблицы записаны недробные элементы, с которых мы начинали строить каждый «этаж», нашей многоэтажной дроби.
Во второй строке сначала записано число 1. Это ключевое число, и надо просто запомнить, что вторая строка начинается с числа 1. Далее записаны числители подходящих дробей.
В третьей строке сначала записано число 0. Это ключевое число, и надо просто запомнить, что третья строка всегда начинается с числа 0.Далее записаны знаменатели подходящих дробей.
Оказывается, что, зная лишь нулевую подходящую дробь, следуя нашим рекуррентным соотношениям, можно найти сколь угодно много числителей и знаменателей в подходящих дробях.
Для получения очередного числителя (знаменателя) необходимо взять элемент того же столбца из первой строки умножить на предыдущий числитель (знаменатель) и прибавить к произведению «предпредыдущий» числитель (знаменатель).
Составим таблицу подходящих дробей для цепной дроби, изображающей число.
|
- |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
… |
|
1 |
1 |
3 |
7 |
17 |
41 |
99 |
239 |
… |
|
0 |
1 |
2 |
5 |
12 |
29 |
70 |
169 |
… |
При этом, если учесть, что , , , =1,41666, то можно увидеть, что чем дальше мы идем, тем лучшее приближение числа получаем.
Цепные дроби обладают следующим важным свойством: если действительное число x записать в виде непрерывной дроби, то подходящая дробь дает наилучшее приближение числа x среди всех дробей, знаменатели которых не превосходят . Т.е. чем больше k, тем k – подходящая дробь ближе к числу.
В связи с этим замечательным свойством рассмотрим применение цепных дробей в календаре.
Глава 2. Приложения цепных дробей
Календарь и подходящие дроби
Древнеримские жрецы, ведавшие исчислением времени, произвольно удлиняли некоторые года, чтобы согласовать календарные даты с сезонными явлениями природы. Впервые порядок в счете времени навел в I в. до нашей эры римский император Юлий Цезарь. Он постановил считать одни годы по 365 суток, а другие по 366 суток, чередуя их по правилу три года подряд коротких, четвертый – длинный. Гораздо позже, с введением христианского летоисчисления, високосным стали считать каждый год, порядковый номер которого делится на 4. Этот календарь в честь Юлия Цезаря называется юлианским. По нему продолжительность суток составляет 365 суток 6 ч, что больше истинной лишь на 11 мин 14 с. Однако и это решение оказалось неудовлетворительным. К XVI в. ошибка, накапливаясь, составила уже около 10 суток.
Следующую реформу календаря провел Григорий XIII – папа римский. Было решено: сдвинуть числа на 10 дней, оставить чередование простых и високосных лет, при этом, если порядковый номер года оканчивается двумя нулями, но число сотен не делится на 4, то этот год простой. В настоящее время расхождение между юлианским и новым, григорианским календарями составляет 13 дней, поскольку с тех пор накопилось еще три дня (в 1700, 1800 и 1900 гг.). Продолжительность григорианского года составляет
365, 2425 суток, т.е. 365 суток 5 ч 49 мин 12 с, т.е. она больше истинной лишь на 26с. Полученная точность очень велика и вполне достаточна для практических нужд.
Интересная система календаря была предложена среднеазиатским математиком и поэтом Омаром Хайямом (ок.1048-1122), по ней високосными годами должны были считаться 8 лет из каждых 33. Продолжительность года по О. Хайяму составляет 365 суток, его погрешность всего 19с в год.
В 1864 г. русский астроном И. Медлер предложил с XX столетия ввести в России следующую поправку к юлианскому календарю: через каждые 128 лет пропускать один високосный год из 32, которые выпадают на этот период. Этот календарь самый точный из всех перечисленных. Здесь погрешность сокращается всего до 1с. Однако календарь И. Медлера не был принят, видимо, из-за того, что период в 128 лет не является «круглым» числом.
Системы календаря оказываются связанными с записью астрономического года в виде цепной дроби:
Год продолжительностью 365 суток - это нулевая подходящая дробь этой цепной дроби, 365 - юлианский год – первая подходящая дробь, 365, 365 и 365 - вторая, третья и четвертая подходящие дроби. А именно:
,
,
.
Системой, соответствующей второй подходящей дроби: семь високосных лет из 29, никто не предложил воспользоваться, видимо, потому, что третья подходящая дробь ненамного сложнее, а точность ее гораздо больше (вспомним, что это система О. Хайяма), а четвертой подходящей дроби соответствует система И. Медлера.
Второе свойство цепных дробей
Вспомним, как вычисляются подходящие дроби.
и т.д. Имеют место рекуррентные соотношения
Рk+1= qk+1. Pk+Pk-1 и Qk+1= qk+1.Qk+Qk-1.
Второе свойство цепных дробей: для любого k = 1,2,…,n имеет место формула
Pk-1Qk – PkQk-1 = (-1)k.
Диофантовы уравнения вида ax+by=с с использованием цепных дробей.
Используем отмеченное нами свойство цепных дробей для решения уравнения ax+by=c Коэффициенты aи b взаимно просты. Разложим в цепную дробь. При этом .
Поскольку обе дроби несократимы, то a = Pn, b = Qn. По свойству имеем
bPn-1– aQn-1 = (-1)n.
Умножив обе части этого равенства на (-1)nc, получим
(-1)n+1aQn-1c + (-1)nbPn-1c =c,откуда видно, что пара чисел
x0 = (-1)n+1cQn-1, y0= (-1)ncPn-1представляет собой решение уравнения.
Общее решение запишется в виде:
x = (-1)n+1cQn -1+ bt, y = (-1)ncPn–1– at, где tпринимает целые значения
Решим уравнение 17х + 13у = 5.
Поскольку , то n= 2, ,откуда х0 = -5•3 = -15, у0= 4•5 = 20 и общее решение имеет вид
x = -15+13t, y = 20-17t.
При решении уравнений вида ax + by = c будем использовать следующий алгоритм :
1) Разложим в цепную дробь (с помощью алгоритма Евклида или с помощью соответствующих преобразований).
2) Из разложения =определяем значение n (т.е. длину цепной дроби).
3) Находим n-1 – подходящую дробь (в случае необходимости используем таблицу).
4) Применяем формулы:
Общее решение: x = (-1)n+1cQn -1+ bt, y = (-1)ncPn–1– at.
Замечания.
1) Можно находить сначала частное решение:
x0 = (-1)n+1cQn-1, y0= (-1)ncPn-1 .А затем общее решение:x= x0 + bt, y= y0 – at
2) Если уравнение имеет вид ax – by = c, то, очевидно, чтоx = (-1)n+1cQn -1+ bt,y = (-1)n+1cPn–1 +at.
3) Если a> bи =, то =[0; q0,q1,…,qn].
Глава 3. Диофантовы уравнения
Диофантовыми уравнениями называются алгебраические уравнения или системы алгебраических уравнений с целыми коэффициентами, для которых надо найти целые или рациональные решения. При этом число неизвестных в уравнениях должно быть не менее двух. Диофантовы уравнения имею, как правило, много решений, поэтому их называют неопределенными уравнениями. К диофантовым уравнениям приводят задач, по смыслу которых неизвестные значения величин могут быть только целыми числами. В качестве примера задача на составления диофантовых уравнений, может служить задача о размере рубля монетами достоинством в 1; 2; 3; 5; 10; 15 и 50 копеек. Соответствующее уравнение имеет вид:
50 Х8 + 20Х7 + 15Х6 + 10Х5 + 5Х4 + 3Х3 + 2Х2 + 1Х1 = 100
Решить такое уравнение – это значит найти все такие наборы.
Х8 Х7 Х6 Х5 Х4 Х3 Х2 Х1 удовлетворяющие 50 Х8 + 20Х7 + 15Х6 + 10Х5 + 5Х4 + 3Х3 + 2Х2 + 1Х1 = 100.
Число наборов, удовлетворяющих этому уравнению примерно равно
510 * 107. Названы эти уравнения по имени греческого математика. Его книга «Арифметика» содержала большое количество интересных задач, его изучали математики всех поколений. Книга сохранилась до наших дней, её можно найти в русском переводе в библиотеке. К диофантовым уравнениям приводят задачи, по смыслу которых неизвестные значения величин могут быть только целыми числами.
Для линейных уравнений с двумя неизвестными, т.е. уравнение вида
ax + by = c, где a, b, c – целые числа, а x, y – целочисленные решения уравнения. для данного уравнения справедливы следующие утверждения:
Если коэффициенты a и b уравнения ax + by = c являются взаимно простыми числами (их наибольший общий делитель d=1), то это уравнение имеет, по крайней мере, одно целочисленное решение.
Если d≠1, то уравнение ax + by = c не имеет целочисленных решений.
Если d=1/ то уравнение ax + by = c имеет бесконечное множество целочисленных решений, которые задаются формулами х = α + bt, y = β – at,
Где (α ; β ) – некоторое целочисленное решении уравнения ax + by = c , at t – произвольное целое число.
Долгое время надеялись отыскать общий решения любого диофантова уравнения. Однако в 1970 году ленинградский математик Ю.В. Матиясевич доказал, что такого общего способа быть не может.
Рассмотрим решение системы диофантовых уравнений первой степени на конкретном примере:
Решить в целых числах систему уравнений:
Решение: вычтем из второго уравнения первое, получим yz-y-z=5
или (y-1)(z-1)=6. Число 6 можно разложить на целые множители четырьмя способами:
Эти системы дают тройки значений
(x;y;z): (5;2;7), (5;7;2), (7;4;3), (7;3;4), (19;-5;0), (17;-2;-1), (17; -1;-2).
Диофантовы уравнения решаются методом перебора (один из самых древнейших методов решения математических задач, возникающих на практике).
А также нужно помнить, что если число d есть наибольший делитель целых чисел a и b, то существует такие числа k и 1, что d=ka + lb. Алгоритм Евклида позволяет вычислить целые числа k и 1.
Линейное диофантово уравнение ax + by = c не будет иметь решений, если числа с и d взаимно простые. Если число с кратно числу d, то одно из решений уравнения будет иметь вид: x=pk и y=pl.
Если целое число c делится на D(a;b), то уравнение ax + by = c имеет целые решения (если некоторые из чисел a, b и с отрицательны, то вместо них берем их модули).
Рассмотрим, как искать эти решения на следующем примере:
Найти целые решения уравнения: 28x – 40y=60
Это уравнение может иметь целые решения, так как D(28;40)=4, а число 60 делится на цело, на 4. Ясно, что любое целое решение уравнения 28x – 40y=60 удовлетворяют и уравнению 7x – 10y = 15 из заданного сокращения обеих частей на 4. Обратно любое целое решение уравнения 7x – 10y = 15, является и целым решением заданного уравнения. У получившегося после сокращения на 4 уравнение 7x – 10y = 15 коэффициенты при неизвестных взаимно просты, т.е. D(7;10) равно 1.
Применим к этим коэффициентам алгоритм Евклида. Мы видим, что при делении числа 7 на 3 получилось неполное частное 2 и остаток 1, а потому 7 = 2*3 + 1. Значит 1=7-2*3. таким же путем устанавливаем, что 10=1*7+3, а потому 3=10-1*7. Подставляя это выражение в равенство 1=7-2*3, получаем 1=7-2(10-1*7). Раскрывая скобки, получаем x=3 и y=2 дают целые решения уравнения 7x – 10y = 15. Чтобы получить целые решения уравнения 7x – 10y = 15, надо оба этих числа умножить на 15. Таким путем мы получим одно решение уравнения
7x – 10y = 15: х=45, y=30.
Другие целые решения того же уравнения имеют вид: х=45+10t, y=30 + 7t, где t – любое число.
Чтобы выделить целые неотрицательные решения заданного уравнения, надо найти такие значения t, при которых 45 +10t>0 и 30+7t>0. Из этих неравенств находим, что должны выполняться условия t>-4,5, t>-30/7, из которых вытекает, что t>-4.
Итак, данное уравнение имеет бесконечно много целых неотрицательных решений, задаваемых формулами х=45+10t, y=30 + 7t, где t принимает значение -4, -3,-2, …
Часть 4. Применение теории на практике
Диофантовы уравнения.
Пример 1:
x^2 + y^2 – 2x + 4y=-5
В левой части уравнения выделим полный квадрат:
x^2 – 2x + 1 + y^2 + 4y + 4=0
(x – 1)^2 + (y + 2)^2=0
Сумма квадратов равна 0 лишь в одном случае
( x – 1)^2=0
(y + 2)^2=0
Решив систему, получим, что x= 1, y= -2
Ответ: ( 1; -2)
Пример 2:
x^2 – 6x + y^2 + 6y + 18=0
Докажем, что это уравнение имеет единственное целочисленное решение.
В левой части уравнения выделим полные квадраты :
( x – 3 )^2 + ( y + 3 )^2=0
Данное уравнение имеет решение, когда
x – 3=0,
y + 3=0
Т. е. при x=3, y= -3.
Теперь я предлагаю рассмотреть графический метод решения диофантовых уравнений.
Алгоритм построения графика уравнения ах + by + с = 0:
1. Придать переменной х конкретное значение х= х1; найти из уравнения ах1 + by + c = 0 соответствующее значение y=y1.
2. Придать переменной х другое значение х=х2; найти из уравнения ах2 + by + c = 0 соответствующее значение y=y2.
3. Построить на координатной плоскости хOy две точки (х1;у1) и (х2;у2).
4. Провести через эти две точки прямую – она и будет графиком уравнения ах + by + с = 0.
Пример 3:
Необходимо найти все пары (х, у) целых чисел, удовлетворяющих системе неравенств:
x^2 + y^2 < 18x – 20y – 166(1)
32x – y^2 > x62 + 12y + 271(2)
Рассмотрим на координатной плоскости области, которые описываются заданными неравенствами. А затем выберем в них лишь точки с целочисленных координат х, у.
Получаем два случая:
1) Неравенство (1) путем выделения полных квадратов сводится к условию
(x^2 – 18x + 81) + (y^2 + 20y + 100) < 15, или (x – 9)^2 + ( y + 10)^2 < √15
Т. е. описывает внутренность круга с центром А(9; -10) и радиусом R1=√15.
2) Неравенство (2) сводится к виду
(x – 16)^2 + (y + 6)^2 < (√21)^2,
Т. е. описывает внутренность круга с центром В(16; -6) и радиусом R2=√21.
Единственной точкой, принадлежащей одновременно двум кругам, будет точка М( 12; -8). Это выясняется подстановкой в систему числовых значений координат всех узлов квадратной сетки, соседних с точкой М.
Ответ: (12; -8).
Цепные дроби
Пример 1. Для перевозки большого количества контейнеров по 170 кг и по 190 кг выделены трехтонные машины. Можно ли ими загружать машины полностью?
Решение. пусть х и у количество контейнеров по 170 и 190 кг соответственно, тогда имеем уравнение
170х+190у=3000;
17х+19у=300.
Для нахождения частного решения воспользуемся разложением дроби в цепную дробь
Свернув предпоследнюю подходящую к ней дробь в обыкновенную
Частное решение данного уравнения имеет вид:
х0= (-1)4300∙9=2700, у0=(-1)5300∙8= -2400,
а общее задается формулой х=2700 - 19k, y= - 2400 + 17k.
откуда получаем условие на параметр k: 141< ≤ k ≤ <143, т.е. k=142, x=2, y=14.
Пример 2. Разложить в цепную дробь .
Решение. Находим: a0=1, . Поскольку , будем иметь a1=a0=1, так что и так далее, то есть
.
Задания для самостоятельного решения
Пример 1. Найти значение следующих цепных дробей:
а) , б) , в)
б)
В) ,
Пример 2. Найти значение цепной дроби .
Пример 3. Решить в целых числах уравнение 54х + 37у = 1.
ЗАКЛЮЧЕНИЕ
Подведем итоги. В ходе исследования была проведена следующая работа:
1)Собран и освоен теоретический материал, составлены на основании изученных свойств алгоритм решения приведенных в данной работе диофантовых уравнений. Сформулированы замечания, использующиеся при решении данных уравнений.
2)Найдены некоторые области применения цепных дробей.
3)Составлены и выполнены практические задания по разложению действительных чисел в цепные дроби, а также по решению диофантовых уравнений вида ax+by=c , других олимпиадных задач.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Баврин И.И.,Фрибус Е.А. Занимательные задачи по математике.- М.: Гуманитарный издательский центр ВЛАДОС, 1999.- 208 с.
Басова Л.А., Шубин М.А., Эпштейн Л.А. Лекции и задачи по математике.- М.: Просвещение, 1981.- 96 с.
Виленкин Н.Я., Шибасов Л.П., Шибасова З.Ф. За страницами учебника математики: Арифметика. Алгебра. Геометрия: Книга для учащихся 10-11 кл. общеобразовательных учреждений.- М.: Просвещение, 1996.- 320 с.
Ожигова Е. П. Что такое теория чисел.- М.: Знание, 1970.- 96 с.
Пичурин Л. Ф. За страницами учебника алгебры: Книга для учащихся 7-9 кл.сред.шк.- М.: Просвещение, 1990.- 224 с.
Савин А. П. Энциклопедический словарь юного математика.- М.: Педагогика, 1989.- 352 с.
Хинчин А. Я. Цепные дроби.- М.: Наука, 1978.- 112 с.