Алгоритм Евклида и математическая проблема календаря

Исследовательская работа:

Алгоритм Евклида

и математическая проблема календаря

Автор: Смирнов Артём,

обучающийся 6 б класса

МБОУСОШ № 1 г. Южи

Ивановской области

Руководитель: Чурина

Елена Вениаминовна,

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

г. Южа

Оглавление

I теоретическая часть

1. Введение……………………………………………………………………….

1.1 актуальность

1.2.Цель работы и ее задачи…………………………………………………

1.3. гипотеза

2. Наибольший общий делитель двух натуральных чисел и различные интерпретации алгоритма Евклида

2.1.Что такое НОД…………………………………………………………….

2.2. Свойства НОД…………………………………………………………….

2.3. Различные интерпретации  алгоритма Евклида

3. История создания календаря, роль алгоритма Евклида в ней

II практическая часть

4. Исследования

4.1. Математическая проблема календаря

4.2. Анкетирование учащихся 6-7 классов школы

Выводы

Заключение

Литература

I теоретическая часть

Введение

Актуальность

В начале текущего учебного года на уроках математики мы познакомились с Наибольшим Общим Делителем (в дальнейшем для удобства будем называть его коротко НОД). Мы узнали, что такое НОД двух и более натуральных чисел и два алгоритма его нахождения.

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

Мне стало интересно, а есть ли другие алгоритмы нахождения НОД и каково их практическое применение. И я решил разобраться в этом вопросе подробнее.

Цель исследования: изучить алгоритм Евклида для вычисления НОД и его роль в истории создания календаря.

Достижение поставленной цели требует решения следующих основных задач:

рассмотреть различные инерпретации алгоритма Евклида;

рассмотреть влияние алгоритма Евклида на историю создания календаря;

провести анкетирование «Знание и использование НОД ».

Объект исследования: умения и навыки вычисления НОД

Предмет исследования: алгоритм Евклида для вычисления НОД

Гипотеза: Есть практическое применение алгоритма Евклида, как и любого другого алгоритма.

Методы исследования: Изучение специальной литературы по данному вопросу: энциклопедии, справочники и учебные пособия. Анкетирование. Сравнение и анализ. Обработка полученных данных (составление обобщающих таблиц, диаграмм).

2. Наибольший общий делитель двух натуральных чисел и различные интерпретации алгоритма Евклида.

2. 1. Что такое НОД двух чисел?

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

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел a или b не ноль.

Обозначения наибольшего общего делителя чисел a и b: НОД(a; b).

2.2. Свойства наибольшего общего делителя.

Наибольший общий делитель обладает рядом свойств.

Перечислим основные  свойства наибольшего общего делителя (НОД).

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

1. Наибольший общий делитель чисел a и b равен наибольшему общему делителю чисел b и a, то есть, НОД(a; b)=НОД(b; a).

Это свойство НОД напрямую следует из определения наибольшего общего делителя.

2. Если a>b, то НОД(a; b) = НОД(a – b; b).

Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности (модуля их разности) и меньшего числа.

3.Если a делится на b, то множество общих делителей чисел a и b совпадает с множеством делителей числа b, в частности, НОД(a;b)=b.

В частности, если числа a и b равны, то  НОД(а;b)=НОД(a;a)= НОД(b;b)=a=b. К примеру, НОД(132, 132)=132.

Данное свойство наибольшего делителя позволяет нам находить НОД двух чисел, когда одно из них делится на другое. При этом НОД равен одному из этих чисел, на которое делится другое число. Например, НОД(8, 24)=8, так как 24 кратно восьми.

4. Если a=b·q+c, где a, b, c и q – целые числа, то множество общих делителей чисел a и b совпадает с множеством общих делителей чисел b и c, в частности, НОД(a, b)=НОД(b, c).

5. Если m – любое натуральное число, то НОД(m·a, m·b)=m·НОД(a, b).

6. Пусть p – любой общий делитель чисел a и b, тогда НОД(a:p, b:p)= НОД(a, b):p, в частности, если p =НОД(a, b) имеем НОД (a:НОД(a, b), b : НОД(a, b))=1, то есть, числа a : НОД(a, b) и b:НОД(a, b) - взаимно простые.

Это свойство наибольшего общего делителя лежит в основе приведения обыкновенных дробей к несократимому виду.

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

2.3. Интерпретации  алгоритма Евклида

1 алгоритм: Геометрический метод нахождения наибольшего общего делителя (НОД)  натуральных чисел с помощью квадратов.

Этот алгоритм – геометрическая иллюстрация алгоритма Евклида, описанного в 5-ем способе.

Например: Найти НОД(162;48).

Построим прямоугольник со сторонами 162мм и 48 мм.

От прямоугольника отрежем несколько квадратов со стороной 48 мм – таких квадратов три.

Остался прямоугольник со сторонами 48 мм и 162-3*48=18 мм.

От полученного прямоугольника снова отрезаем квадраты, у которых сторона равна 18 мм – таких квадратов получится два.

Остался прямоугольник со сторонами 18 мм и 48-2*18=12 мм.

От полученного прямоугольника снова отрезаем квадраты, у которых сторона равна 12 мм – такой квадрат будет единственный.

Остался прямоугольник со сторонами 12 мм и 18-12=6 мм, который , в свою очередь состоит из двух квадратов 6мм х 6 мм.

Длина стороны последнего полученного квадрата и есть наибольший общий делитель чисел 162 и 48.

Ответ: НОД(162; 48)=6.

Этот способ мне кажется нерациональным: вычерчивая прямоугольники и квадраты, легко ошибиться в построениях и получится неверный ответ. Но все же я попробовал решить этим способом несколько примеров нахождения наибольшего общего делителя двух натуральных чисел (см. приложение 2).

2 алгоритм: Алгоритм Евклида нахождения наибольшего общего делителя (НОД)  двух натуральных чисел вычитанием.

Древнегреческие математики называли этот алгоритм  ἀνθυφαίρεσις  или  ἀνταναίρεσις  — «взаимное вычитание». Этот алгоритм, видимо, не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

1. Из большего числа вычитается меньшее.

2. Если получается 0, то числа равны друг другу и являются наибольшим общим делителем.

3. Если результат вычитания не равен 0, то большее число заменяется на результат вычитания

4. Переход к пункту 1.

Например: Найти НОД(30; 18).

30 - 18 = 12;
18 - 12 = 6;
12 - 6 = 6;
6 – 6 = 0.

НОД – это уменьшаемое или вычитаемое.

НОД (30; 18) = 6.

Приведенный метод вычисления не является оптимальным. Например, для нахождения НОД(100; 2) следует выполнить 50 (!!) операций вычитания (см. приложение 1). Для ускорения вычисления НОД операцию вычитания следует заменить операцией взятия остатка от деления.

3 алгоритм: Алгоритм Евклида нахождения наибольшего общего делителя (НОД)  двух натуральных чисел делением.

1. Большее число делится на меньшее

2. Если делится без остатка, то меньшее число и есть наибольший общий делитель.

3. Если есть остаток, то большее число заменяем на остаток от деления.

4. Продолжаем деление до тех пор, пока не получим в остатке нуль. Последний неравный нулю остаток и есть НОД данных чисел.

Например: Найти НОД (273;1014).

Решение. Выполняем деление с остатком: По лемме:

1014=273*3+195

273=195*1+78

195=78*2+39

78=39*2

НОД (273;1014) = НОД(195;273) = НОД(195;78) = НОД(78;39)= 39

НОД(273;1014)=39

4 алгоритм: Бинарный алгоритм Евклида нахождения наибольшего общего делителя (НОД)  двух натуральных чисел.

Данный алгоритм быстрее обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги. Алгоритм был известен еще в Китае 1-го века, но опубликован был лишь в 1967 году израильским физиком и программистом Джозефом Стайном. Он основан на использовании следующих свойств НОД:

НОД(2a; 2b) = 2 НОД(a; b),

НОД(2a; 2b+1) = НОД(a; 2b+1),

НОД(-a; b) = НОД(a; b)

Сам алгоритм выглядит так:

Если a, b чётные, то НОД(a; b) = 2*НОД(a/2; b/2);

Если a чётное, b нечётное, то НОД(a; b) = НОД(a/2; b);

Если b чётное, a нечётное, то НОД(a; b) = НОД(a; b/2);

Если a, b нечётные и b > a, то НОД(a; b) = НОД((b-a)/2; a);

Если a, b нечётные и b < a, то НОД(a; b) = НОД((a-b)/2; b);

Например:

НОД(1978;2666)=2*НОД(989;1333)=2*НОД(989;344)=2*НОД(989;172)=2*НОД(989;86)=2*НОД(989;43)=2*НОД(946;43)=2*НОД(473;43)=2*НОД(430;43)= 2*НОД(215; 43)=2*НОД(172; 43)=2НОД*(86; 43)=2*НОД(43; 43)=2*43=86.

НОД(1978; 2666)=86

3. История создания календаря, роль алгоритма Евклида в ней

Как и всякая добротно выполненная работа, алгоритм Евклида дает гораздо больше, чем от него первоначально ожидалось получить. Применяя к числам a и b алгоритм Евклида для определения их наибольшего общего делителя, получаем конечную систему равенств:

где неполным частным последовательных делений соответствуют остатки с условием b>>>…>>0, а соответствует остаток 0.

Несомненно, описанная Евклидом процедура определения общей меры двух величин применительно к числам (а общая мера двух натуральных чисел, очевидно, есть их наибольший общий делитель) была изобретена задолго до Евклида. Таким же образом находили НОД и древние китайские математики. И только то, что эта процедура стала известна в эпоху Возрождения именно из «Начал, дало ей название « алгоритм Евклида»

Скорее всего, она возникла из коммерческой практики древних купцов, когда им надо было сравнивать различные отношения целых чисел. Как, например, сравнивать отношения чисел 3703700 и 1234567 и чисел 22962965 и 7654321? Вполне естественна была попытка узнать, сколько раз меньшее число укладывается в большем. Легко проверить, что 3703700 = 2 · 1234567 + 1234566, а 22962965 = 3 · 7654321 + 2. Ясно теперь, что отношение 3703700 к 1234567 меньше, чем отношение 22962965 к 7654321. Таким образом, что сейчас мы записываем как

= 2,99999919 <= 3, 000000261,

Древние вычислители объясняли длинной фразой.

Если бы пришлось сравнить более близкие отношения чисел, например,  и , то вычисления были бы более сложными:

71755875 = 61735500 + 10020375;

61735500 = 6 · 10020375 + 1613250;

10020375 = 6 · 1613250 + 340875;

1613250 = 4 · 340875 + 249750;

340875 = 249750 + 91125;

249750 = 2 · 91125 + 67500;

 

91125 = 67500 + 23625;

67500 = 2 · 23625 + 20250;

23625 = 20250 + 3375;

20250 = 6 · 3375.

Алгоритм Евклида позволил определить НОД чисел 71755875 и 61735500, равный 3375, что соответствует разложению отношения 71755875 к 61735500 в цепную дробь:

 

Алгоритм Евклида оказывается эквивалентным современной процедуре разложения числа в цепную дробь и более того, позволяет «округлить» отношения чисел, т.е. заменять дробь с большим знаменателем на очень близкую к ней дробь с меньшим знаменателем.

Т.е. системе равенств (1) соответствует равносильная система

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

Такое выражение называется правильной (конечной) цепной или правильной непрерывной дробью, при этом предполагается, что – целое число, а , …,  - натуральные числа.

Имеются различные формы записи цепных дробей:

В самом деле, выражение

Сравнение > было выполнено в III в. до н.э. Аристархом Самосским в трактате «О расстоянии и размерах Луны и Солнца».

Сейчас известно, что подходящие дроби разложения любого (рационального или иррационального) числа в цепную дробь представляют собой наилучшие рациональные приближения этого числа.

Дробь представим в виде цепной дроби, данная дробь неправильная, заменяем смешанным числом, выделяем целую часть она равна 2. Далее найдем НОД (29;38) по алгоритму Евклида.

38:39=1·29+9

29:9=3·9+2

9:2=4·2+1

2:1=2·1

НОД (29;38)=1, тогда

 Как определить значение цепной дроби? Если цепная дробь конечна, то задача сводится лишь к более или менее трудоёмкому вычислению, а результат представляет собой рациональное число. Совсем другое дело, когда она бесконечна. Приблизительное значение бесконечной канонической цепной дроби можно получить, если "превратить" её в конечную, т.е. отбросить "хвостик". При этом чем больше "этажей" мы оставим , тем точнее будет результат.  Как построить цепную дробь.

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

II практическая часть

4. Исследования

4.1 Математическая проблема календаря

"День и ночь - сутки прочь", "Зима и лето - года нету": С незапамятных времён люди подметили, что важнейшие отрезки времени - год и сутки - определяются различными природными процессами.

Как сказано в одном старом учебнике космографии, «к сожалению, год не равен целому числу суток». С этим нельзя не согласиться, так как из упомянутого факта проистекает много неудобств. Зато он порождает интересную математическую проблему.

 

Узаконить в гражданской жизни такую длину года невозможно. А что получится, если принять гражданский год равным ровно 365 суткам?

Выход из этого положения есть. Надо считать, что в некоторых годах по 365 суток, а в некоторых – по 366, чередуя годы так, чтобы средняя длина года была возможно ближе к истинной. Так можно воспроизвести истинную длину года с любой точностью, но для этого может понадобиться очень сложный закон чередования коротких (простых) и длинных (високосных) годов, что нежелательно. Нужен компромисс: сравнительно простой закон чередования коротких и длинных годов, дающий среднюю длину года, достаточно близкую к истиной.

Эту задачу впервые решил Юлий Цезарь. Точнее говоря, это сделал по его поручению александрийский астроном Созиген, вызванный для этой цели в Рим. Юлий Цезарь ввёл такую систему: три года подряд коротких (простых), четвёртый – длинный (високосный). Много позже, когда было принято христианское летосчисление, високосными стали считать годы, номера которых делятся на 4.

Этот календарь называется юлианским. В России он существовал до февраля 1918 года. По юлианскому календарю средняя длина года равна 365  суток = 365 суток 6 часов.

С редняя длина юлианского года была больше истинной на 11 минут 14 секунд.

Юлианский календарь был улучшен папой Григорием ХIII. В 1582 году он произвёл следующую реформу календаря. Сохранил чередование простых и високосных лет, но добавил правило: если номер года оканчивается двумя нулями, а число сотен не делится на 4, то этот год простой, но 1600 - високосный. Кроме того, считая. Что от начала летосчисления (от «рождества Христова») уже накопилась ошибка в 10 дней, Григорий ХIII сразу прибавил 10 дней. С тех пор накопилось ещё 3 дня (в 1700,1800, 1900 годах). Он осуществил проект предложенный итальянским врачом и математиком Луиджи Лилио  Поэтому в настоящее время расхождение между юлианским и новым (григорианским) составляет 13 дней.

Какова средняя длина григорианского года? Из 400 лет по юлианскому календарю – 100 високосных. А по григорианскому – 97. Поэтому средняя длина григорианского года = 365 суток = 365,242500 суток = 365 суток 5 часов 49 минут 12 секунд, т.е. она больше истинной на 26 секунд.

Давайте взглянем  на проблему календаря с точки зрения теории цепных дробей. Целую часть опустим, так как наличие в каждом году 365 целых суток не требует напоминаний. 5 часов 48 минут 46 секунд что равно 20 926 секундам, а 1 сутки =86 400 секунд.

Находим НОД чисел 20 926 и 86 400 по алгоритму Евклида.

Исходя из нахождения НОД двух чисел по алгоритму Евклида, составим цепную дробь:

П ервая подходящая дробь дает для длины года приближенное значение
 суток. Чтобы реализовать такую длину года, надо считать високосным 1 год из 4. Вторая дробь == соответствует такому решению: 7 високосных лет из каждых 29. Средняя длина года при этом получится 365 суток. Это точнее, чем 365, но зато сложнее.

Третья дробь==. Теперь за 33 года набегает «8» лишних лет и этот календарь в 1079 году был предложен персидским математиком и поэтом Омаром Хайямом. Он даже точнее Григорианского.

Следующая дробь

=====

то получим  соответствующий ей календарь фантастической точности, по которому средняя длина года на 1 секунду

Омар Хайям

будет превышать истинную! В1864 году профессор Дерптского университета (ныне Тартуский) Иоганн Генрих Медлер предложил с 20-го века ввести такой календарь в России. В нем пришлось бы каждые 128 лет пропускать 1 високосный  год, если високосные годы отсчитывать по принятой тогда юлианской системе. Процедура простая, но то ли в силу обычного консерватизма, то ли по другим причинам этот календарь распространения не получил. Как видим, весьма простыми средствами достигнута очень большая точность.

Иоганн Генрих Медлер

Для данного алгоритма существует множество теоретических и практических применений. В частности он широко распространён в электронной коммерции. Также алгоритм используется при решении диофантовых уравнений (Уравнения в целых числах – это алгебраические уравнения с двумя или более неизвестными п еременными и целыми коэффициентами). Решениями такого уравнения являются все целочисленные (иногда натуральные или рациональные) наборы значений неизвестных переменных, удовлетворяющих этому уравнению. Такие уравнения ещё называют диофантовыми, в честь древнегреческого математика Диофанта Александрийского. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел.

Долгое время алгоритм Евклида был самым эффективным способом отыскания наибольшего общего делителя, однако с появлением электронно-вычислительных машин ситуация изменилась Учет специфических особенностей выполнения арифметических операций компьютером позволил построить более эффективную (для программной реализации) версию алгоритма Евклида.

4.2. Анкетирование учащихся 6-7 классов школы

Анкета «Знание и использование НОД»

Дорогой друг!

Ответь, пожалуйста, на ряд несложных вопросов, это не займет много времени.

1. В каком классе ты учишься? ____________

2. Как расшифровывается: НОД _______

3.Если ты ответил хотя бы частично на 2 вопрос переходи к следующим, если

нет, можно сдать анкету.

3. Какие из нижеперечисленных способов вычисления НОД ты знаешь:

1 – перебор всех делителей

2 – разложение на простые множители

3-алгоритм Евклида

4- другие способы

4. Используешь ли ты НОД при решении задач и упражнений по математике (алгебре, геометрии)?

5. Если на вопрос 5 ты ответил ДА, то укажи в каких случаях ты это делаешь:

1- сокращение дробей

2- решение задач

Какие жизненные задачи ты можешь решить с помощью НОД?

Опросил 110 человек. И получились такие результаты.

На вопрос: «Как расшифровывается: НОД»

Правильно ответили 35 шестиклассников из 55 и 21 семиклассник из 55.

Способ нахождения НОД разложением на простые множители знают 43шестиклассника и 35 семиклассников. Алгоритм Евклида известен 1 семикласснику. Знают другие способы нахождения НОД 12 шестиклассников и 15 семиклассников.

Используют НОД при решении задач и упражнений по математике (алгебре, геометрии 41 учащийся из опрошенных.

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

По результатам анкетирования можно сделать вывод, что учащийся 6-7 классов владеют знаниями по теме «Наибольший общий делитель», используют при решении математических задач, но небольшое количество учащиеся знает, как практические задачи можно решить с помощью нахождения НОД двух и более чисел.

5.Выводы

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

Большинство древних алгоритмов со временем вытеснялось из вычислительной практики более новыми алгоритмами. Алгоритм Евклида избежал этой участи прежде всего благодаря своей экономности. Тем более удивительно, что хотя почтенный алгоритм Евклида и применяется в течение столь многих столетий, он не всегда является наилучшим способом для нахождения НОД.

Алгоритм Евклида имеет практическое применение.

С помощью алгоритма Евклида вычисляется наиболее точно длина года, но это трудно реализовать в календаре.

Считаю, что цель моей работы достигнута. Гипотеза подтверждена.

6. Заключение.

Математика – царица всех наук.

Ее возлюбленный – истина, ее наряд – простота и ясность.

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

Случайный путник не обнаружит во дворце ничего привлекательного. Красота его открывается лишь разуму, любящему истину, закаленному в борьбе с трудностями, свидетельствующему о незаурядности и непреодолимой склонности человека к необычайно запутанным, но неиссякаемым и возвышенным наслаждениям ума, свойственным самой природе людей

Снядецкий Ян

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

Научиться быстро и правильно вычислять НОД чисел не так уж сложно. Вышеперечисленные алгоритмы рассчитаны на ум "обычного" человека и не требуют уникальных способностей. Главное - более или менее продолжительная тренировка.

Собранный мной материал можно использовать на факультативных занятиях, на занятиях математического кружка. Учителя математики могут использовать его при изучении данной темы. Также рекомендуем ознакомиться с моей работой тем сверстникам, которые хотят знать о математике больше, чем рядовой школьник.

В будущем я планирую продолжить исследование по данной теме и рассмотреть алгоритм Евклида для многочленов, при решении уравнений в целых числах.

7.Список используемой литературы:

Виленкин Н.Я. и др. Математика, 6 класс: учебник для общеобразовательных учреждений. – М.: Мнемозина, 2013.- 288с.

Макарычев Ю.Н., Миндюк Н.Г. Алгебра: Дополнительные главы к школьному учебнику 8 кл.: учебное пособие для школ и классов с углубленным изучением математики.- М.:Просвещение,1996.- 207 с.

Пичурин Л.Ф. За страницами учебника алгебры- Москва: Просвещение, 1990г. -

Щетников А. И. Алгоритм Евклида и непрерывные дроби. - Новосибирск: АНТ, 2003 г.

http://www.rusnauka.com

Список используемых источников информации:

1. Википедия (свободная энциклопедия), http://ru.wikipedia.org

2. Сайт "Единая коллекция цифровых образовательных ресурсов".

3. http://www.rusnauka.com