Реферат: Анализ алгоритма Евклида в Евклидовых кольцах

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+ < 1 + и α=1 + > 1+ = ,

поскольку

6+ >6+.

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

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

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

Григорий XIIIне был математиком. Он был римским папой, но его имя связано с важной математической задачей – проблемой календаря.

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

1

??? = 365 ????? 5 ????? 48 ????? 46 ??????=365,2421199 ?????.

Узаконить в гражданской жизни такую длину года невозможно. А что получится, если принять гражданский год равным ровно 365 суткам? На рис. показана орбита Земля. 1 января 1980 года в 0 часов Земля находилась в точке А. за 365 суток она не дойдёт до точки А и 1 января 1981 года в 0 часов окажется в точке В, а 1 января 1982 года – в точке С и т.д. Получится, что если отмечать положение Земли на орбите, соответствующие фиксированной дате, то оно будет каждый год иное: оно будет отставать почти на 6 часов. За 4 года отставание состоит почти сутки, и фиксированная дата будет попадать на разные времена года, т.е. 1 января с зимы постепенно переместится на осень, потом на лето.

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

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

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

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

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

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

Как видим, весьма простыми средствами достигнута очень большая точность. Как получили этот результат?