Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/mmks/dec08/Safin.pdf Дата изменения: Fri Dec 5 10:15:05 2008 Дата индексирования: Tue Oct 2 04:17:24 2012 Кодировка: koi8-r Поисковые слова: mercury program

ПРОГРАММА ДЛЯ ПОСТРОЕНИЯ ПРАВИЛЬНЫХ МНОГОУГОЛЬНИКОВ ЦИРКУЛЕМ И ЛИНЕЙКОЙ А. Р. Сафин1

Оглавление
Аннотация 1. Теоретическая основа программы
2.1. Выбор корня . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Точность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3. Композиция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Нахождение (s) . . . . . . Выражение не всех Au;v . . Повторное выражение Au;v Дохождение до уровня m - . . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 2
4 5 5

2. Про блемы, с которыми мы столкнулись и которые успешно решили 4

3. Сокращение времени работы программы
3.1. 3.2. 3.3. 3.4.

. . . .

6

6 8 8 8

Заключение Приложения

8

А. Связь между построимостью правильных многоугольников и квадратичными иррациональностями 10 Б. Текст программы без комментариев В. Текст программы с комментариями Г. Выражения и композиции Литература 12 13 16 19

11А класс. Лицей им. Н. И. Ло бачевского при Казанском государственном университете. Научные руководители: Скопенков А. Б., МГУ; к. ф.-м. н., доцент КГТУ Бронштейн М. Д.; к. ф.-м. н., доцент КГУ Лернер Э. Ю.

1 safinaskar@mail.ru.

1


Аннотация
С давних времён людей интересовал вопрос, как строить различные фигуры при помощи циркуля и линейки. Осо бенно интересны в этом плане были правильные многоугольники. Я написал компьютерную программу в пакете Mathematica , с помощью которой можно построить все построимые правильные многоугольники. По теореме Гаусса-Ванцеля (всюду далее m | натуральное число, p1 , p2 , p3 , . . . , pl | различные простые числа Ферма, то есть числа вида 2m + 1 и q | целое неотрицательное число) число вершин в них имеет вид 2q p1 p2 p3 : : : pl . Для построения правильного 2q p1 p2 p3 : : : pl -угольника достаточно уметь строить правильные p1 , p2 , p3 , . . . , pl -угольники. Очевидно, что для построения правильного p-угольника достаточно построить отрезок длиной cos 2p . А для этого нужно, что бы cos 2p был квадратичной иррациональностью, то есть выражался через натуральные числа при помощи арифметических операций и квадратных корней из неотрицательных чисел. Эти факты доказаны в приложении А. Моя программа выражает cos 2p в радикалах. Иоганн Густав Гермес более 10 лет разрабатывал спосо б построения правильного 65 537-угольника и описал его в рукописи размером более 200 страниц, которая хранится в библиотеке Гёттингенского университета ([?]). Моя программа находит соответствующее построение около минуты. Идея о программе и основные принципы её работы взяты из [2]. При написании программы я столкнулся с про блемами (они приводятся в параграфе 2), которые успешно решил вместе с научными руководителями. Программу и настоящий текст я написал сам. Благодарим М. А. Малахальцева за полезные о бсуждения.

1. Теоретическая основа программы
Определение 1. Будем называть действительное число построимым, если оно
является квадратичной иррациональностью. Сейчас будет показано, как выразить cos 25 . Общий случай рассмотрим позже. 4 Обозначим " = cos 25 + i sin 25 . Тогда нам нужно найти "+" = cos 25 . Мы знаем, 2 что
" + "2 + "3 + "4 = -1:

Обратим внимание, на то что (" + "4 ) + ("2 + "3 ) = (" + "4 )("2 + "3 ) = -1. Значит, по теореме Виета" + "4 и "2 + "3 | корни уравнения x2 + x - 1. Решаем его и полу чаем -1+ 5 и -1- 5 . Так как в данном случае ответ должен быть положительным, 2 2 cos 25 = -1+ 5 . 4 Перейдём к о бщему случаю. Всюду далее p = 2m + 1 | простое число и нам нужно выразить cos 2p . Обозначим " = cos 2p + i sin 2p . Разо бьём сумму
" + "2 + "3 + : : : + "
2m

= -1

2


на такие 2 части (назовём их A1;0 и A1;1 ), что бы они были построимы и " и "2m попало в A1;0 . Тогда A1;0 и A1;1 построимы. Затем аналогично разбиваем A1;0 на A2;0 и A2;2 , A1;1 | на A2;1 и A2;3 и так далее. Каждый раз v-ый осколок u-ого уровня мы будем называть Au;v и делить его на Au+1;v и Au+1;v+2u . В конце мы получим Am-1;0 = " + "-1 = 2 cos 2p . Пусть g | первоо бразный корень степени 2m из 1 по модулю 2m + 1, то есть g таково, что остатки от деления на p чисел g1 , g2 , g 3 , . . . , g p-1 различны. Будем разбивать так, что бы для любых целых u и v таких, что 0 u m - 1 и 0 v 2u - 1, было верно равенство
Au;v = "g + "g + "g + "g + : : : + "g : (1) Это возможно, так как для любых u и v, таких что v 2u-1 - 1, верно равенство Au-1;v = Au;v + Au;v+2u-1 . Также Am-1;0 = " + "-1 . Попро буем понять, что такое Au;v Au;v+2u-1 . Безусловно, это линейная комбинация от степеней ". Обозначим коэффициент при "s , где s | целое число, как (s). Очевидно, что тогда (s) | это количество решений сравнения g2 k+v + g 2 l+2 +v s (mod p) (2) относительно k и l. При этом решения, в которых корни имеют одинаковые остатки от деления на 2m-u , считаются за одно. Если бы1 оказалось, что (0) = 0 и для любого целого s0 верно равенство (s0 ) = = (s0 g2u- ), то Au;v Au;v+2u-1 было бы линейной комбинацией от Au-1;0 , Au-1;1 , Au-1;2 , Au-1;3 , . . . , Au-1;2u-1 -1 , в самом деле, Au;v Au;v
u u u-1 v

2u +v

2·2u +v

3·2u +v

2m -2u +v

= (1)

+2u-1 = 2m-u+1 -1 u-1 2 i "g 3
i=0 2m-u+1 -1 i=0 Au-1;0

(1)" + (2)"2 + (3)"3 + : : : + (2m )" + (g)
2m-u+1 -1
i=0

2m

"g

2u-1 i+1

+ (g2 )

2m-u+1 -1
i=0

=
2u-1 i+2

"g

+

+ (g )

2u-1 i+3 "g

+ : : : + (g

2u-1 -1

)

2m-u+1 -1
i=0

"g

2u-1 i+2u-1 -1

=

= (1)

+ (g)Au-1;1 + (g2 )Au-1;2 + (g3 )Au-1;3 + : : : + u-1 + (g2 -1 )Au-1;2u-1 -1 :

И это действительно так! Доказательства ниже.

Лемма 1. (0) = 0.
Идейное резюме доказательства. Предположим противное. Тогда у сравнения (2) есть решение (k0 ; l0 ) при s = 0. Проводим простейшие прео бразования и приходим к противоречию в связи с чётностью. Доказательство. Предположим противное. Тогда существуют такие целые k0 и l0 , что
g
2u k0 +v

+g

2u l0 +2u-1 +v

0 (mod p):

3


g g
2m-1

2u k0 +v -g 2u l0 +2u-1 +v

(mod p): (mod p):

= -1, так как g | первоо бразный корень, отсюда
g
2u k0 +v g 2m-1 +2u l0 +2u-1 +v
u-1

2u k0 + v 2m-1 + 2u l0 + 2 Разделим сравнение на 2
u-1

+ v (mod 2m ):
m-u+1

. ):

2k0 2m-u + 2l0 + 1 (mod 2

Противоречие в связи с чётностью. Лемма 2. Для любого целого s0 верно равенство (s0 ) = (s0 g2u-1 ). Идейное резюме доказательства. Простейшими прео бразованиями uпрео бразуем сравнение (2) при s = s0 , k = k0 и l = l0 к сравнению (2) при s = s0 g2 -1 , k = l0 + 1 и l = k0 .

Доказательство. Установим соответствие между решениями. Пусть (k0 ; l0 ) является решением сравнения (2) при s = s0 .
g g g
2u k0 +v

+g

2u l0 +2u-1 +v s 0 2u-1

(mod p): (mod p): (mod p):

Умножим о бе части сравнения на g
2u k0 +2u-1 +v

.

+g

2u (l0 +1)+v s g 2u-1 0

Поменяем местами слагаемые в левой части сравнения.
2u (l0 +1)+v

+g

2u k0 +2u-1 +v s g 2u-1 0

Это значит, что (k0 ; l0 ) | корень сравнения (2) при s u-1 s0 тогда и только = 2. тогда, когда (l0 + 1; k0 ) | корень сравнения (2) при s = s0 g Замечание 1. Все Au;v являются суммами чисел вида Am-1;v = "a + "-a R, поэтому в выражении берутся квадратные корни только из неотрицательных чисел.

2. Про блемы, с которыми мы столкнулись и которые успешно решили
2.1. Выбор корня
Когда программа выражает Au;v и Au;v+2u-1 как корни квадратного уравнения, непонятно, какой из полученных корней | Au;v , а какой | Au;v+2u-1 . Что бы определить соответствие, программа считает о ба числа непосредственно по формуле (1) и сравнивает. Если Au;v меньше, то меньший из полученных корней | Au;v и нао борот. Существует аналитический метод выбора корня, но он довольно сложен, поэтому время работы программы при аналитическом спосо бе сравнимо со временем при моём спосо бе. 4


2.2. Точность
При выборе корня (см. предыдущий параграф) нужно, что бы абсолютная погрешность разности Au;v - Au;v+2u-1 была меньше этой разности, иначе будет невозможно наверняка установить соответствие между корнями и Au;v и Au;v+2u-1 . Эта про блема легко решается, так как в пакете Mathematica реализована возможность считать с любой точностью. Более того, можно хранить вместе с числом его точность и контролировать, не превысила ли погрешность разумные пределы. Об этом можно прочитать на http://reference.wolfram.com/mathematica/ tutorial/NumericalPrecision.html. Мы использовали эту возможность. В программе предусмотрен оператор, сравнивающий абсолютную погрешность разности Au;v - Au;v+2u-1 с самой разностью. Если погрешность окажется больше, программа выдаёт соо бщение о б ошибке. Но это соо бщение не выдаётся, поэтому можно быть увереным, что корень выбирается правильно, а значит, программа выдаёт правильное выражение.

2.3. Композиция
Для p = 65 537 итоговое выражение велико: оно содержит 17 661 551 154 923 608 корней. Ясно, что выражение не может уместиться в памяти компьютера, поэтому оно хранится в виде композиции нескольких функций (далее просто композиция). Она очень удо бна, так как содержит все части, повторяющиеся в выражении, только по одному разу. Поясню сказанное на примере: для p = 17 выражением будет
0

1B 1B 1 B B 2@ 2@ 2 +
v u u u u t

0

-

1 17 + + 2 2




!

v u u t 0

1 1+ 4

-

1 17 + 2 2

!



!2

1 C A

+ 1 4 1 17 + 2 2

!2 12 1 C CC AC A

11 17 + 22 2



!

v u u - t1

+

1 4

-

1 2

-

17 2

!2

+

1B 1 4@ 2

-

1 17 + + 2 2

v u u t

1+

-

:

А вот его композиция:
A A A A A
1;0 1;1 2;0 2;1 3;0

1 17 =- + ; 2 2 1 17 =- - ; 2 2 1 1 = A1;0 + -A1;0 + A2;0 - A1;1 ; 2 41 1 1 = A1;1 + -A1;0 - A1;1 + A2;1 ; 2 41 1 12 A - A2;1 . = A2;0 + 2 4 2;0 5




Для p = 3, 5, 17 и 257 программа находит композицию и итоговое выражение, а для 65 537 | только итоговое выражение. Для больших p композиция гораздо короче самого выражения, например, для p = 65 537 она содержит всего 2 103 корня. Обратим внимание: что бы построить правильный многоугольник, не нужно предварительно превращать композицию в выражение, поэтому исходная задача решена и для p = 65 537. Программа проверяет правильность своей работы путём приближённого (с учётом погрешности) вычисления cos 2p и сравнения его с приближением косинуса, полученным стандартными средствами Mathematica . Что бы выполнить такое сравнение, тоже не о бязательно знать итоговое выражение, поэтому программа проверила се бя для всех p, в том числе для p = 65 537. Программа также считает количество сложений и вычитаний, умножений, делений и корней в композиции и итоговом выражении. При этом количество этих операций в итоговом выражении для p = 65 537 было получено нами косвенным путём, а именно анализом композиции.

3. Сокращение времени работы программы
3.1. Нахождение (s)
Это самое существенное сокращение времени работы программы. Без него запуск программы для p = 65 537 оказался бы невозможным. Как найти (s)? Можно смоделировать умножение Au;v и Au;v+2u-1 как многочленов с одной переменной ". Тогда первые 2u-1 коэффициента результата будут равны (s). Но при p = 65 537 Au;v и Au;v+2u-1 будут содержать до 32 768 слагаемых, значит, это моделирование потре бует до 1 073 741 824 операций, и всё это только для нахождения одних Au;v и Au;v+2u-1 . Понятно, что такой uпуть совершенно неприемлим. Поэтому мы моделируем -1 умножение Au+1;v на "g2 +v . Обозначим коэффициент при "s в результате этого как (s). Все (s) находятся исходя из следующей леммы.

Лемма 3. Для любого s0 верно равенство
(s0 ) = (s0 ) + (s0 g
2u-1

) + (s0 g

2·2u-1

) + (s0 g

3·2u-1

) + : : : + (s0 g

2m -2u-1

):

(3)

Идейное резюме доказательства. Составляем сравнение, количеством корней которого является (s). Тогда правая часть (3) является количеством корней некоторой совокупности сравнений. Объединяя их и вводя новые переменные, приходим к сравнению (2) при s = s0 . Доказательство. Очевидно, что (s) | это количество решений сравнения
g
2u+1 x+v

+g

2u-1 +v

s (mod p)

6


относительно x. При этом решения с одинаковыми остатками по модулю 2m-u-1 считаются за одно. Тогда правая часть (3) равна количеству решений совокупности сравнений
2u g g 2u u g2 u g2 . . .
+1 x+v +1 x+v +1 x+v +1 x+v

+ + + +

g g g g

2u 2u 2u 2u

+ + -1 + -1 +
-1

-1

v v v v



s0 s0 s0 s0

(mod p) g2u-1 (mod p) g2·2u-1 (mod p) g3·2u-1 (mod p) (mod p)

g

2u+1 x+v

+g

2u-1 +v s g 2m -2u-1 0

относительно x. Решения считаются за одно по тому же принципу. Все сравнения, номера которых имеют остаток 1 по модулю 4, о бъединим в одно, 2 | в другое, 3 | в третье, 0 | в четвёртое. Приходим к совокупности
2 g g2 g2
u+1 x+v u+1 x+v u+1 x+v 2u+1 x+v

g

+ + + +

g g g g

2 2 2 2

u-1 +v u-1 +v u-1 u-1

+v +v

s s s s

2u+1 y (mo d p) 0g 2u+1 y+2u-1 (mod 0g 2u+1 y+2·2u-1 (mo 0g 2u+1 y+3·2u-1 (mo 0g

p) d p) d p)

относительно x и y. Решения, в которых корни имеют одинаковые остатки по модулю 2m-u-1 , считаются за-1 одно. Разделим о бе части первого сравнения на 2u+1 y , втор ого | на g 2u+1 y+2u , тр етьего | на g 2u+1 y+2·2u-1 и четвёртого | на g g2u+1 y+3·2u-1 .
2u+1 (x-y)+v g + g-2u+1 y+2u-1 +v s0 (mod p) g 2u+1 (x-y)-2u-1 +v + g -2u+1 y+v s0 (mod p) u+1 g 2 (x-y)-2·2u-1 +v + g -2u+1 y-2u-1 +v s0 (mod g2u+1 (x-y)-3·2u-1 +v + g-2u+1 y-2·2u-1 +v s0 (mo

p) d p):

Введём новые переменные.


В первом сравнении: k = x - y и l = -y
3 Во втором: k = x - y - 4 и l = -y - 1 (здесь и далее 4 bc a (mod p)) 1 В третьем: k = x - y - 2 и l = -y - 1
a b

| это такое c, что

В четвёртом: k = x - y - 1 1 и l = -y - 1 4
2 g g2 g2
u+1 k+v 2u u+1 k+2u +v u+1 k+v 2u u+1 k+2u +v 2

1 4

Получим: + g +1 l+2u-1 +v s0 (mod p) + g2u+1 l+2u-1 +v s0 (mod p) + g +1 l+2u +2u-1 +v s0 (mod p) + g2u+1 l+2u +2u-1 +v s0 (mod p): 7

g


Объединим все сравнения в одно.
g
2u k+v

+g

2u l+2u-1 +v s 0

(mod p):
m-u

Решения, в которых корни имеют одинаковые остатки по модулю 2 ются одинаковыми. Сравниваем полученное сравнение с (2).

, счита-

3.2. Выражение не всех Au;v
Большинство (s) равны нулю, поэтому что бы выразить cos 2p через квадратные радикалы, нео бязательно выражать все Au;v . Поэтому находятся только те Au;v , которые используются в итоговом выражении. Для этого в программе применяется рекурсия. В программе есть процедура, к которой в качестве аргументов передаются u и v и которая выражает Au;v . Она находит все (s) и вызывает се бя рекурсивно для тех осколков более низкого уровня, для которых (s) = 0. Также она вызывает Au-1;v , так как Au;v + Au;v+2u-1 = Au-1;v . В самой программе эта процедура вызывается для Am-1;0 и результат делится на 2. В табл. 1 на с. 9 в последних двух строках отчётливо видно, насколько сокращаются вычисления, осо бенно для больщих p.

3.3. Повторное выражение A

u;v

В описанном в предыдущем параграфе алгоритме может случиться так, что указанная процедура вызовется несколько раз для одного и того же Au;v . Поэтому программа в специальном массиве отмечает каждый вызов процедуры.
- Мы находим cos 2p как Am2 1;0 , хотя можно было как Re Am;0 . Благодаря тому, что мы выбрали первый спосо б, программа доходит лишь до m - 1-го уровня и это немного сокращает время своей работы.

3.4. Дохождение до уровня m - 1

Заключение
В этом параграфе приведены наши основные результаты. лах в пакете Mathematica .


Результат 1. Я написал программу для выражения cos

2 p

в квадратных радика-

Я использовал пакет Mathematica по следующим причинам: Он позволяет работать со сложными выражениями, содержащими корни С его помощью можно производить расчёты с любой заранее заданной точностью Сложные программы на этом пакете имеют маленький код, так как: 8


{ Mathematica использует функциональное программирование { В Mathematica есть большое количество встроенных функций
Таблица 1. Результаты работы
p

Время работы Количество операций в итоговом выражении Количество операций в композиции

Количество Au;v Количество вычисленных Au;v

в секундах Сложений и вычитаний Делений Возведений в квадрат Квадратных корней Сложений и вычитаний Делений Возведений в квадрат Квадратных корней

0:2187500 0 1 0 0 0 0 0 0 0 0

3

0:2656250 1 3 0 1 1 2 0 1 1 1

5

0:2812500 23 33 4 16 10 10 3 5 7 5

17

3:9062500 24 191 31 425 3 616 15 712 188 78 37 39 127 39

257

27 35 4 17

253 323 034 661

971 102 565 551

67:7500000 763 199 999 309 847 217 273 323 608 154 923 608 86 548 4 206 2 101 2 103 32 767 2 103

65 537

Результат 2. Я опро бовал свою программу для p = 3, 5, 17, 257 и 65 537, то

есть для всех известных чисел Ферма, и всюду убедился в правильности ответов. В табл. 1 на с. 9 со браны результаты работы программы. Сами итоговые выражения и композиции находятся в приложении Г. Время работы указано для компьютера Intel Pentium 4 с частотой процессора 2:40 ГГц и оперативной памятью размером 512 МБ. А простых чисел Ферма, больших, чем 65 537 не найдено, и даже есть гипотеза, что их нет ([1]).

Программа о бладает тем существенным преимуществом, что она находит композицию, которая короче самого выражения и важнее его. Под композицией подразумевается цепочка формул, в каждой из которых используются результаты предыдущих формул. В нашем случае формулы содержат только арифметические операции и квадратные корни. Отметим, что сборка выражений из часто встречающихся составных частей | один из распространённых приёмов при аналитических вычислениях. Она эффективна за счёт многократного использования ранее вычисленных выражений. Например, для p = 65 537 композиция содержит 2103 квадратных корня, а итоговое выражение | 17 661 551 154 923 608.

Результат 3. С помощью своей программы я получил итоговое выражение для
p = 3, 5, 17 и 257 и композицию для p = 3, 5, 17, 257 и 65 537 (см. приложение Г).

Результат 4. Я оценил времы работы программы (O(2m m2 ln m)) и объём используемой ей памяти (O(p O(p)). того, что:

log2 p-3 2

ln p), если не находить итоговое выражение, то

Результат 5. Скорость моей программы была значительно увеличена за счёт
Она выражает через радикалы только те числа вида Au;v , которые о бязательно присутствуют в итоговой формуле Она выражает их только по одному разу 9




Она находит (s) через (s)

Без них программа работала бы не для всех p. Об этих сокращениях времени работы программы можно прочитать в параграфе 3.

Результат 6. В процессе работы я столкнулся со следующими сложностями, о б
успешном решении которых написано в параграфе 2:


Было непонятно, какой из двух корней уравнения выбрать Для подсчётов не хватало машинной точности Итоговое выражение для p = 65 537 не помещалось в память компьютера
Выразить cos 2n , если n не имеет вид 2q p1 p2 p3 : : : pl , через радикалы степеней, отличных от второй

Направление дальнейшей деятельности:


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

Лемма 4. Любую квадратичную иррациональность можно построить циркулем и
линейкой.

Идейное резюме доказательства. Сложение, вычитание, умножение, деление и извлечение квадратного корня можно реализовать циркулем и линейкой. Доказательство. Достаточно доказать, что если a и b можно построить циркулем и линейкой, то a + b, a - b, ab, a , a тоже. b Для a + b и a - b это очевидно. Для умножения нужно построить фигуру на рис. 1 так, что бы OA = 1, OC = a и AB = b. Очевидно, что тогда CD = ab. Деление проводится с помощью этой же фигуры. Нужно лишь построить её так, что бы OA = b, OC = a и AB = 1. Очевидно, что тогда CD = a . b Что бы извлечь корень, нужно построить фигуру на рис. 2 так, что бы AC = 1 и CB = a. Очевидно, что тогда CD = a.

Лемма 5. Если можно построить правильные p1 , p2 , p3 , . . . , pl -угольники, то можно построить и правильный 2q p1 p2 p3 : : : pl -угольник.

Идейное резюме доказательства. Применим l - 1 раз алгоритм Евклида для центральных углов многоугольников, потом q раз разделим полученный центральный угол пополам.
10


D

C

O

A

B

Рис. 1. Умножение и деление циркулем и линейкой
D

A

CO

B

Рис. 2. Извлечение квадратного корня циркулем и линейкой

Доказательство. Если можно построить правильный p-угольник, то можно построить и его центральный угол, равный 2p . По двум углам можно построить их разность, поэтому проведём алгоритм Евклида для углов 2 и 2 . Так как p1 и p1 p2 p2 взаимно просты, то можно подо брать такие целые a и b, что ap1 + bp2 = 1, но нельзя подо брать такие целые a и b, что бы 0 < ap1 + bp2 < 1. Отсюда есть такие целые a и b, что
a b 1 += ; p2 p1 p1 p2

но нет таких, что бы 0<
a b 1 +< : p2 p1 p1 p2

Таким о бразом, мы построили угол, равный p22 . Затем применим алгоритм 1p Евклида к углам p22 и 2 и так далее. Наконец, разделим результат q раз пополам. p3 1p

Лемма 6. Если 2m + 1 | простое число, то существует такое целое неотрицательное r, что m = 2
r

Доказательство. Пусть m | не степень двойки. Тогда существуют такие натуральное a и нечётное b = 1, что m = ab. Но тогда 2m + 1 = (2a + 1)(2a(b-1) - : : : - - 23a + 22a - 2a + 1). Противоречие.
11


Б. Текст программы без комментариев
createbutton[p_]:=Button[p, time=AbsoluteTime[]; SelectionMove[ButtonNotebook[],All,ButtonCell]; SelectionMove[ButtonNotebook[],Next,CellGroup]; NotebookDelete[ButtonNotebook[]]; program::aT="aT[u,v0]-aT[u,v0+2^(u-1)]==0"; post[a_,b___]:=a[b]; program[m_]:=( precision=100; Clear[aA,aT,aR,aE]; g=PrimitiveRoot[2^m+1]; Do[ gin[i]=PowerMod[g,i,2^m+1]; logg[gin[i]]=i, {i,0,2^m-1} ]; a[0,0]=aE[0,0]=-1; aR[0,0]=N[-1,precision]; aA[0,0]=Null; aC=Table[Null,{2^m}]; aEPMPrivate[0,0]=0; aEDivisionPrivate[0,0]=0; aESquarePrivate[0,0]=0; aERootPrivate[0,0]=0; aCPM=0; aCDivision=0; aCSquare=0; aCRoot=0; aT[u_,v_]:=(aT[u,v]=Sum[Cos@(N[2,10]Pi gin[2^ui+v])/(2^m+1),{i,0,2^(m-u)-1}]); aA[u_,v_]:=( aA[u-1,Mod[v,2^(u-1)]]; v0=Mod[v,2^(u-1)]; aEPMPrivate[u,v]=2aEPMPrivate[u-1,v0]+If[u!=1,1,0]; aEDivisionPrivate[u,v]=2aEDivisionPrivate[u-1,v0]+2; aESquarePrivate[u,v]=2aESquarePrivate[u-1,v0]+If[u!=1,1,0]; aERootPrivate[u,v]=2aERootPrivate[u-1,v0]+1; a1=gin[v0+2^(u-1)]; If[aT[u,v0]-aT[u,v0+2^(u-1)]==0,Message[program::aT]]; tab=( aA[u-1,#[[1]]]; aEPMPrivate[u,v]=aEPMPrivate[u,v]+aEPMPrivate[u-1,#[[1]]]+1; aEDivisionPrivate[u,v]=aEDivisionPrivate[u,v]+aEDivisionPrivate[u-1,#[[1]]]; aESquarePrivate[u,v]=aESquarePrivate[u,v]+aESquarePrivate[u-1,#[[1]]]; aERootPrivate[u,v]=aERootPrivate[u,v]+aERootPrivate[u-1,#[[1]]]; a[u-1,#[[1]]]Length@# )&/@Split@Sort@Table[Mod[logg@Mod[gin[2^ui+v0]+a1,2^m+1],2^(u-1)],{i,0,2^(m-u)-1,2}]; v0=Mod[v,2^(u-1)]; b=a[u-1,v0]/2; root=Sqrt[b^2-Plus@@tab]; aA[u,v]=Null; aCPrivate=If[(aT[u,v0]Subscript[A, u1,v1]},"="]; aR[u,v]=N[1,precision]aCPrivate/.a->aR; If[m<16,aE[u,v]=post[HoldForm,aCPrivate/.a->aE]] ); aA[m-1,0]; aEPM=aEPMPrivate[m-1,0]; aEDivision=aEDivisionPrivate[m-1,0]+1; aESquare=aESquarePrivate[m-1,0]; aERoot=aERootPrivate[m-1,0]; aC=Sort@Take[aC,aCRoot]

12


); m=Log[2,p-1]; Print["p = "<>ToString[p]<>". Пожалуйста, подождите..."]; program[m]; Print["Время счёта: "<>ToString[AbsoluteTime[]-time]<>" секунд"]; Print["Приближённое значение, полученное программой:"]; If[Precision@aR[m-1,0]>=1,Print[aR[m-1,0]/2],Print["ОШИБКА. В ответе нет ни одной значащей цифры"]]; Print["Косинус, подсчитанный другим образом:"]; Print[N[Cos@(2Pi)/p,precision]]; Print["Количество Subscript[A, u,v]: "<>ToString[2^(m-1)-1]]; Print["Количество вычисленных Subscript[A, u,v]: "<>ToString@aCRoot]; Print["---- ИТОГОВОЕ ВЫРАЖЕНИЕ ----"]; If[m<16,Print@OpenerView@{"Итоговое выражение",aE[m-1,0]/2}]; Print["Сложений: "<>ToString@aEPM]; Print["Делений: "<>ToString@aEDivision]; Print["Возведений в квадрат: "<>ToString@aESquare]; Print["Взятий корня: "<>ToString@aERoot]; Print["---- КОМПОЗИЦИЯ ----"]; Print@OpenerView@{"Композиция",Column@aC}; Print["Сложений: "<>ToString@aCPM]; Print["Делений: "<>ToString@aCDivision]; Print["Возведений в квадрат: "<>ToString@aCSquare]; Print["Взятий корня: "<>ToString@aCRoot]; Print["Полное время: "<>ToString[AbsoluteTime[]-time]<>" секунд"], Method->"Queued"]; CellPrint@ExpressionCell[Row[Join[{Выберите,p},createbutton/@{3,5,17,257,65537}]," "],"Section"]

В. Текст программы с комментариями
createbutton[p_]:=Button[p, time=AbsoluteTime[]; SelectionMove[ButtonNotebook[],All,ButtonCell]; SelectionMove[ButtonNotebook[],Next,CellGroup]; NotebookDelete[ButtonNotebook[]];(*Этот код предназначен для генерации кнопки, к выражению косинуса в радикалах отношения не имеет*) program::aT="aT[u,v0]-aT[u,v0+2^(u-1)]==0";(*Этот код нужен для вывода сообщения об ошибке в случае недостаточной точности*) post[a_,b___]:=a[b]; (*Нужен для применения оператора к аргументам после их вычисления*) program[m_]:=((*program --- это процедура, содержащая как бы всю программу в целом. К ней в качестве параметра передаётся m (см. работу). Процедура создаёт функцию aE[u_, v_] (E --- сокращение от Expression), возвращающую представление Subscript[A, u,v] через квадратные радикалы (см. работу), aR[u_, v_] (Real), возвращающую вещественное приближение для Subscript[A, u,v]. Результаты выполнения этих функций для всех возможных u и v записываются в память во время выполнения program и при обращении к функциям они ничего не считают, а сразу выдают уже посчитанное значение, как будто они не функции, а массивы. Также программа заносит в переменную aC (Constructor) список строк в композиции, в aCPM (Plus, Minus) --- количество сложений и вычитаний в композиции, aCDivision --делений, aCSquare --- возведений в квадрат, aCRoot --- корней, aEPM, aEDivision, aESquare, aERoot --- то же, но в итоговом выражении. При m >= 16 aR не работает, так как иначе память компьютера не вместила бы ответ. Но aC, aR, aCPM, ..., aEPM, ... работают при m >= 16. Более того, при p == 65537 было проверено равенство aR[m - 1, 0]/2 == Cos[2\[Pi]/65537] (кстати, аналогичное было проверено для всех возможных p), поэтому мы можем быть уверены, что и при p == 65537 программа работает верно. aEPM и тому подобные считались во время выполнения программы, поэтому и были получены для p == 65537*) precision=100;(*Количество знаков после запятой в приближении для итогового выражения. Это приближение нужно, чтобы сравнить его с косинусом, полученным другим образом*) Clear[aA,aT,aR,aE];(*Этот оператор нужен, чтобы при повторном запуске program с другим m старые значения переменных не вошли в противоречие с новыми. aA (All) --- это основная рекурентная процедура. aT (Test) вычисляет Subscript[A, u,v] непосредственно по определению (см. работу). О том для чего это нужно, см. работу. aA[u_, v_] делает следующее: 1. Выражает Subscript[A, u,v] через Subscript[A, u-1,0], Subscript[A, u-1,1], Subscript[A, u-1,2],

13


Subscript[A, u-1,3], ..., Subscript[A, u-1,2^(u-1)-1] и записывает результат в aCPrivate 2. Запускает те из aA[u - 1, 0], aA[u - 1, 1], aA[u - 1, 2], aA[u - 1, 3], ..., aA[u - 1, 2^(u-1) 1] реккурентно, которые присутствуют в выражении 3. Присваивает aA[u, v] = Null, чтобы исключить повторный вызов 4. Подставляет полученные в реккурентно вызванных процедурах aE в выражение и записывает результат в aE[u, v] 5. Подставляет полученные в реккурентно вызванных процедурах aR в выражение и записывает результат в aR[u, v] 6. Вносит вклад в вычисление aC, aCPM, ..., aEPM, ...*) g=PrimitiveRoot[2^m+1]; (*Что такое g, объяснено в работе*) Do[ gin[i]=PowerMod[g,i,2^m+1]; logg[gin[i]]=i, {i,0,2^m-1} ];(*logg --- это как бы логарифм по основанию g. В качестве аргумента к нему передаётся остаток по модулю 2^m, в качестве ответа он выдаёт остаток по модулю 2^m+1. Строго говоря, для данного a он выдаёт такое b, что g^b == a. В этом цикле считаются значения функции при всех возможных параметрах, чтобы далее пользоваться этой функцией как массивом. gin, наоборот, предназначено для возведения g в степень по модулю 2^m+1*) a[0,0]=aE[0,0]=-1;(*a --- это просто заголовок, он не считается. Внутри программы aCPrivate выражено через a, а затем вместо него подставляются aE или aR. a[0, 0] приравнивается к -1, чтобы, например, для p == 17 aC[1, 0] возвращало -1/2+Sqrt[17]/2, а не 1/2a[0,0]+Sqrt[-4a[0,0]+1/4a[0,0]^2]*) aR[0,0]=N[-1,precision]; (*Это нужно для правильной работы случая p == 3*) aA[0,0]=Null;(*Это нужно, чтобы рекурсия имела конечную глубину*) aC=Table[Null,{2^m}];(*Потом мы заполним этот массив*) aEPMPrivate[0,0]=0; aEDivisionPrivate[0,0]=0; aESquarePrivate[0,0]=0; aERootPrivate[0,0]=0; aCPM=0; aCDivision=0; aCSquare=0; aCRoot=0; aT[u_,v_]:=(aT[u,v]=Sum[Cos@(N[2,10]Pi gin[2^ui+v])/(2^m+1),{i,0,2^(m-u)-1}]); (*Конструкция aT[u_,v_]:=(aT[u,v]=...) представляет собой реализацию динамического программирования: после первого вызова aT для некоторых u и v результат запоминается и используется при повторных вызовах*) aA[u_,v_]:=( aA[u-1,Mod[v,2^(u-1)]];(*Subscript[A, u-1,v0] == Subscript[A, u,v0] + Subscript[A, u,v0+2^(u-1)], поэтому знание Subscript[A, u-1,v0] необходимо для вычисления Subscript[A, u,v]*) v0=Mod[v,2^(u-1)]; aEPMPrivate[u,v]=2aEPMPrivate[u-1,v0]+If[u!=1,1,0];(*Subscript[A, u-1,v0] дважды встречается в выражении + знак между -Subscript[A, u-1,v0]/2 и корнем. Если u == 1, то под корнем на один плюс или минус меньше, поэтому в этом случае единицу не прибавляем*) aEDivisionPrivate[u,v]=2aEDivisionPrivate[u-1,v0]+2;(*2 деления: оба отмечены здесь красным цветом: -Subscript[A, u-1,v0]/2\[PlusMinus]Sqrt[(Subscript[A, u-1,v0]/2)^2-...]*) aESquarePrivate[u,v]=2aESquarePrivate[u-1,v0]+If[u!=1,1,0];(*Если u == 1, то квадрата нет: он сразу же вычисляется*) aERootPrivate[u,v]=2aERootPrivate[u-1,v0]+1; a1=gin[v0+2^(u-1)];(*Основой алгоритма является моделирование умножения \[Epsilon]^g^v0+\[Epsilon]^g^(v0+2*2^u)+\[Epsilon]^g^(v0+4*2^u)+\[Epsilon]^g^(v0+6*2^u)+...+ \[Epsilon]^g^(v0+2^m-2*2^u) на g^(v0+2^(u-1)). Почему нужно моделировать именно это, написано в работе. Так как все вычисления, какие можно, надо выносить из цикла, почитаем g^(v0+2^(u-1)) сразу и запомним результат в a1. Сам цикл ниже*) If[aT[u,v0]-aT[u,v0+2^(u-1)]==0,Message[program::aT]];(*Здесь происходит контроль точности*)

14


(*Это самая сложная и важная часть программы. Здесь мы нахадим \[Alpha](1), \[Alpha](g), \[Alpha]( g^2), \[Alpha](g^3), ..., \[Alpha](g^(2^(u-1)-1)). tab --- это {\[Alpha](1)a[u - 1, 0], \[Alpha](g) a[u - 1, 1], \[Alpha](g^2)a[u - 1, 2], \[Alpha](g^3)a[u - 1, 3], ..., \[Alpha](g^(2^(u-1)-1))a[u 1, 2^(u-1) - 1]}. Разбор этой части см. в конце*) tab=( aA[u-1,#[[1]]]; aEPMPrivate[u,v]=aEPMPrivate[u,v]+aEPMPrivate[u-1,#[[1]]]+1; aEDivisionPrivate[u,v]=aEDivisionPrivate[u,v]+aEDivisionPrivate[u-1,#[[1]]]; aESquarePrivate[u,v]=aESquarePrivate[u,v]+aESquarePrivate[u-1,#[[1]]]; aERootPrivate[u,v]=aERootPrivate[u,v]+aERootPrivate[u-1,#[[1]]]; a[u-1,#[[1]]]Length@# )&/@Split@Sort@Table[Mod[logg@Mod[gin[2^ui+v0]+a1,2^m+1],2^(u-1)],{i,0,2^(m-u)-1,2}]; v0=Mod[v,2^(u-1)]; b=a[u-1,v0]/2;(*b --- это b из формулы корней квадратного уравнения x^2+2bx+c=0: Subscript[x, 1,2]== -b\[PlusMinus]Sqrt[b^2-c]*) root=Sqrt[b^2-Plus@@tab];(*Это Sqrt[b^2-c] из приведённой выше формулы корней*) aA[u,v]=Null;(*О необходимости этого оператора сказано выше*) aCPrivate=If[(aT[u,v0]Subscript[A, u1,v1]},"="];(*Находим новую строчку в композиции*) aR[u,v]=N[1,precision]aCPrivate/.a->aR;(*Находим aR[u,v]*) If[m<16,aE[u,v]=post[HoldForm,aCPrivate/.a->aE]](*Находим aE[u,v], если, конечно p меньше 65537. Потом "замораживаем" его при помощи HoldForm, чтобы избежать лишних сокращений и сохранить первозданный вид выражения*) ); aA[m-1,0]; aEPM=aEPMPrivate[m-1,0]; aEDivision=aEDivisionPrivate[m-1,0]+1;(*Ответ равен Subscript[A, m-1,0]/2, поэтому добавляется одно деление*) aESquare=aESquarePrivate[m-1,0]; aERoot=aERootPrivate[m-1,0]; aC=Sort@Take[aC,aCRoot] ); m=Log[2,p-1]; Print["p = "<>ToString[p]<>". Пожалуйста, подождите..."]; program[m]; Print["Время счёта: "<>ToString[AbsoluteTime[]-time]<>" секунд"]; Print["Приближённое значение, полученное программой:"]; If[Precision@aR[m-1,0]>=1,Print[aR[m-1,0]/2],Print["ОШИБКА. В ответе нет ни одной значащей цифры"]]; Print["Косинус, подсчитанный другим образом:"]; Print[N[Cos@(2Pi)/p,precision]]; Print["Количество Subscript[A, u,v]: "<>ToString[2^(m-1)-1]]; Print["Количество вычисленных Subscript[A, u,v]: "<>ToString@aCRoot];(*Оно совпадает с количеством строк в алгоритме сборки, то есть с количеством корней в ней*) Print["---- ИТОГОВОЕ ВЫРАЖЕНИЕ ----"]; If[m<16,Print@OpenerView@{"Итоговое выражение",aE[m-1,0]/2}];(*OpenerView нужен для того, чтобы скрыть итоговое выражение, так как если оно велико, попытка вывести его на экран может привести к

15


зависанию компьютера*) Print["Сложений: "<>ToString@aEPM]; Print["Делений: "<>ToString@aEDivision]; Print["Возведений в квадрат: "<>ToString@aESquare]; Print["Взятий корня: "<>ToString@aERoot]; Print["---- КОМПОЗИЦИЯ ----"]; Print@OpenerView@{"Композиция",Column@aC}; Print["Сложений: "<>ToString@aCPM]; Print["Делений: "<>ToString@aCDivision]; Print["Возведений в квадрат: "<>ToString@aCSquare]; Print["Взятий корня: "<>ToString@aCRoot]; Print["Полное время: "<>ToString[AbsoluteTime[]-time]<>" секунд"], Method->"Queued"]; CellPrint@ExpressionCell[Row[Join[{Выберите,p},createbutton/@{3,5,17,257,65537}]," "],"Section"] (*Эти строчки касаются генерации кнопки*)

Г. Выражения и композиции
p=3

Композиция: пуста. Итоговое выражение: - 1 . 2
p=5

Композиция:
A
1;0

5 1 =- + . 22
1 -1 2 2



Итоговое выражение:

+



5 2

.
p = 17

Композиция:
A A A A A
1;0 1;1 2;0 2;1 3;0

1 17 =- + ; 2 2 1 17 =- - ; 2 2 1 1 = A1;0 + -A1;0 + A2;0 - A1;1 ; 2 41 1 1 = A1;1 + -A1;0 - A1;1 + A2;1 ; 2 41 1 12 A - A2;1 . = A2;0 + 2 4 2;0 16



Итоговое выражение:


0

1B 1B 1 B B 2@ 2@ 2 +
v u u u u t

0

-

1 17 + + 2 2




!

v u u t 0

1 1+ 4

-

1 17 + 2 2

!



!2

1 C A

+ 1 4 17 1 + 2 2

!2 12 1 C CC AC A

11 17 + 22 2



!

v u u - t1

+

1 4

-

1 2

-

17 2

!2

+

1B 1 4@ 2

-

17 1 + + 2 2

v u u t

1+

-

:

p = 257

Композиция:
A A A A A A A A A A A A A A A
1;0 1;1 2;0 2;1 2;2 2;3 3;0 3;1 3;2 3;3 3;4 3;5 3;6 3;7 4;0

1 257 =- + ; 2 2 1 257 =- - ; 2 2 1 1 = A1;0 + -16A1;0 + A2;0 - 16A1;1 ; 2 41 1 1 = A1;1 + -16A1;0 - 16A1;1 + A2;1 ; 2 41 1 1 = A1;0 - -16A1;0 + A2;0 - 16A1;1 ; 2 41 1 1 = A1;1 - -16A1;0 - 16A1;1 + A2;1 ; 2 41 1 1 = A2;0 + -2A2;0 + A2;0 - 5A2;1 - 4A2;2 - 5A2;3 ; 2 42 1 1 = A2;1 - -5A2;0 - 2A2;1 + A2;1 - 5A2;2 - 4A2;3 ; 2 42 1 1 = A2;2 + -4A2;0 - 5A2;1 - 2A2;2 + A2;2 - 5A2;3 ; 2 42 1 1 = A2;3 - -5A2;0 - 4A2;1 - 5A2;2 - 2A2;3 + A2;3 ; 2 42 1 1 = A2;0 - -2A2;0 + A2;0 - 5A2;1 - 4A2;2 - 5A2;3 ; 2 42 1 1 = A2;1 + -5A2;0 - 2A2;1 + A2;1 - 5A2;2 - 4A2;3 ; 2 42 1 1 = A2;2 - -4A2;0 - 5A2;1 - 2A2;2 + A2;2 - 5A2;3 ; 2 42 1 1 = A2;3 + -5A2;0 - 4A2;1 - 5A2;2 - 2A2;3 + A2;3 ; 2 42 1 1 = A3;0 + -2A3;0 + A2;0 - 2A3;2 - A3;4 - 2A3;5 - A3;6 ; 2 43 17




A A A A A A A A A A A A A A A A A A A

1 = A3;1 2 1 4;2 = A3;2 2 1 4;3 = A3;3 2 1 4;4 = A3;4 2 1 4;5 = A3;5 2 1 4;6 = A3;6 2 1 4;7 = A3;7 2 1 4;8 = A3;0 2 1 4;9 = A3;1 2 1 4;10 = A3; 2 1 4;11 = A3; 2 1 4;12 = A3; 2 1 4;13 = A3; 2 1 4;14 = A3; 2 1 4;15 = A3; 2 1 5;0 = A4;0 2 1 5;1 = A4;1 2 1 5;15 = A4; 2 1 5;23 = A4; 2
4;1

1 + -2A3;1 + A2;1 - 2A3;3 - A3;5 - 2A3;6 - A3;7 ; 43 1 + -A3;0 - 2A3;2 + A2;2 - 2A3;4 - A3;6 - 2A3;7 ; 43 1 + -2A3;0 - A3;1 - 2A3;3 + A2;3 - 2A3;5 - A3;7 ; 43 1 + -A3;0 - 2A3;1 - A3;2 - 2A3;4 + A2;4 - 2A3;6 ; 43 1 + -A3;1 - 2A3;2 - A3;3 - 2A3;5 + A2;5 - 2A3;7 ; 43 1 - -2A3;0 - A3;2 - 2A3;3 - A3;4 - 2A3;6 + A2;6 ; 43 1 + -2A3;1 - A3;3 - 2A3;4 - A3;5 - 2A3;7 + A2;7 ; 43 1 - -2A3;0 + A2;0 - 2A3;2 - A3;4 - 2A3;5 - A3;6 ; 43 1 - -2A3;1 + A2;1 - 2A3;3 - A3;5 - 2A3;6 - A3;7 ; 43 12 2 - -A3;0 - 2A3;2 + A3;2 - 2A3;4 - A3;6 - 2A3;7 4 12 3 - -2A3;0 - A3;1 - 2A3;3 + A3;3 - 2A3;5 - A3;7 4 12 4 - -A3;0 - 2A3;1 - A3;2 - 2A3;4 + A3;4 - 2A3;6 4 12 5 - -A3;1 - 2A3;2 - A3;3 - 2A3;5 + A3;5 - 2A3;7 4 12 6 + -2A3;0 - A3;2 - 2A3;3 - A3;4 - 2A3;6 + A3;6 4 12 7 - -2A3;1 - A3;3 - 2A3;4 - A3;5 - 2A3;7 + A3;7 4 1 + -A4;0 + A2;0 - A4;1 - A4;2 - A4;5 ; 44 1 + -A4;1 + A2;1 - A4;2 - A4;3 - A4;6 ; 44 12 15 + -A4;0 - A4;1 - A4;4 - A4;15 + A4;15 ; 4 12 7 + -A4;7 + A4;7 - A4;8 - A4;9 - A4;12 ; 4 18

; ; ; ; ; ;


A A A A A

1 = A4; 2 1 5;25 = A4; 2 1 6;0 = A5;0 2 1 6;56 = A5; 2 1 7;0 = A6;0 2
5;24

1 + -A4;8 + A2;8 - A4;9 - A4;10 - A4;13 ; 44 12 9 + -A4;9 + A4;9 - A4;10 - A4;11 - A4;14 ; 4 12 + A - A5;1 - A5;23 ; 4 5;0 12 24 + -A5;15 + A5;24 - A5;25 ; 4 12 + A - A6;56 . 4 6;0
8

Итоговое выражение: слишком велико, что бы быть помещённым сюда.
p = 65 537

Композиция: слишком велика, что бы быть помещённой сюда. Итоговое выражение: не было получено, так как не помещается в памяти компьютера. Но поставленная задача всё равно решена для p = 65 537 (см. параграф 2.3).

Литература
[1] Brent R. P. Integer Factorization Algorithms Il lustrated by the Factorization of Fermat Numbers. Computer Sciences Laboratory, Australian National University, presented at CANT'97, Sydney, 5 December 1997. [2] Козлов П. Ю., Скопенков А. Б. В поисках утраченной алгебры: в направлении Гаусса (подборка задач).
http://arxiv.org/abs/0804.4357v1

[3] Гаусс К. Ф. Арифметические исследования // Труды по теории чисел. М.: Издво АН СССР, 1959. [4] Гиндикин С. Дебют Гаусса // Квант, 1, 1972. [5] Кириллов А. А. О правильных многоугольниках, функции Эйлера и числах Ферма // Квант, 7, 1977. Квант, 6, 1994.

19