%8.08.07
\input amstex
\input amsppt.sty
%\magnification=\magstep4 
\magnification=\magstep1 
\advance\vsize0.5cm \voffset=-1.5cm \advance\hsize2cm \advance\hoffset-0.5cm
\NoBlackBoxes
\define\R{{\Bbb R}} \define\Q{{\Bbb Q}} \define\Z{{\Bbb Z}} \define\C{{\Bbb C}}
\def\dist{\mathop{\fam0 dist}}
\define\fix{\operatorname{fix}}
\define\stab{\operatorname{stab}}
\define\Spin{\operatorname{Spin}}
\define\SO{\operatorname{SO}}
\define\pr{\operatorname{pr}}
\define\rk{\operatorname{rk}}
\define\id{\operatorname{id}}
\def\arg{\mathop{\fam0 arg}}
\def\a{\mathop{\fam0 ачп}}
\def\sgn{\mathop{\fam0 sgn}}
\def\ctg{\mathop{\fam0 ctg}}
\def\st{\mathop{\fam0 st}}
\def\t{\widetilde}
\def\id{\mathop{\fam0 id}}
\def\Int{\mathop{\fam0 Int}}
\def\Con{\mathop{\fam0 Con}}
\def\Cl{\mathop{\fam0 Cl}}
\def\Im{\mathop{\fam0 Im}}
\define\sgrad{\operatorname{sgrad}}



\newpage
\centerline{\uppercase{\bf Квадратичные иррациональности}}
\smallskip 
\centerline{\bf А. Белов-Канель, П. Козлов и А. Скопенков}
\smallskip 
%\centerline{\it www.mccme.ru/circles/oim/materials/construc.pdf}
%\bigskip

\hfill{\it Понял ты или нет,} 

\hfill{\it Отчего мы жили так странно две тысячи лет?}  

\hfill{\it Б. Гребенщиков, Вавилон.} 


%\bigskip{\bf Аннотация.}


\bigskip
{\bf Введение.}

\smallskip
{\bf Теорема Гаусса.} 
{\it Калькулятор (вычисляющий числа с абсолютной точностью) имеет кнопки 
$$1,\quad +,\quad -,\quad \times,\quad :\quad\text{и}\quad \sqrt{}$$ 
(и неограниченную память).  
На этом калькуляторе можно вычислить число $\cos\dfrac{2\pi}n$ тогда и только 
тогда, когда $n=2^\alpha p_1\dots p_l$, где $p_1,\dots,p_l$ --- различные 
простые числа вида $2^{2^s}+1$.}  

\smallskip
(Переформулировка теоремы Гаусса в терминах построений циркулем и линейкой 
правильных многоугольников приводится 
%во втором 
в отступлении и не используется в остальном тексте. 
История этой знаменитой теоремы приводится в [Gi]. 
{\it Невозможность} в этой теореме не была явно доказана Гауссом [Ga], однако 
второе доказательство невозможности в настоящей заметке можно принять за 
рассуждение Гаусса.) 

В этой заметке предлагается набросок {\it элементарного доказательства 
приведенной теоремы}.
Оно не использует терминов 'группа Галуа' (даже термина 'группа') и 
%; доказательство {\it возможности} не использует также термина 
'поле' (доказательство невозможности использует квадратичные расширения 
только {\it множества рациональных чисел}). 
Несмотря на отсутствие {\it терминов}, {\it идеи} приводимых доказательств  --- 
{\it группируй и властвуй} или {\it объединяй и властвуй} --- 
%--- для возможности,  {\it рассмотри инвариант 'размерность'} --- для 
%невозможности) 
являются отправной точкой для теории Галуа (см. философское отступление).

Приводимое доказательство известно в математическом фольклоре, однако авторам 
не удалось найти его в явном виде в литературе.  

(Элементарное доказательство {\it возможности} для $n=17$ приводится в [Ch, Gi, 
Po, PS, Ko]. 
Для общего случая оно намечено в [Ga, Gi], где ясности мешает построение общей 
теории вместо доказательства конкретного результата.)  
%рассмотрение более общей задачи неструктурированность в [Ga] и использование 
%термина 'группа' в [Gi]. 
Относительно простое доказательство {\it невозможности} в [Vi, гл. 5] 
использует понятие 'расширения поля'. 
Это доказательство, наряду с элементарным, изложено в настоящей заметке, 
при этом 
%Отличие приводимого изложения в том, что 
необходимые термины не вводятся 
немотивированно впрок, а естественно появляются в процессе размышления над 
проблемой. 
% (и в том, что невозможность доказана для произвольного $n$, а не 
%только для простого). 
Элементарное изложение идеи другого неэлементарного доказательства 
невозможности см. в [Ki]. 
Первое приводимое доказательство невозможности в теореме Гаусса является 
алгебраическим выражением этой идеи.)

Приводимые доказательства возможности и невозможности независимы друг от друга, 
что отражено и в нумерации задач. 
В этих доказательствах используется определение построимости из второго 
отступления и эквивалентность теоремы Гаусса аналогичной теореме для 
{\it комплексного} калькулятора (задача D). 
%ниже). 

Доказательства представлены в виде циклов задач.  
%(большинство задач о невозможности снабжены указаниями или решениями;  ). 
Решение задач потребует от многих читателей усилий (впрочем, опытный математик, 
не знакомый с теорией Галуа, с легкостью восстановит решения по приведенным 
указаниями или даже без них). 
Однако эти усилия будут сполна оправданы тем, что вслед за великими 
математиками в процессе изучения интересной проблемы читатель познакомится 
с некоторыми основными идеями алгебры.
Надеюсь, это поможет читателю совершить собственные настолько же полезные
открытия (не обязательно в математике)!

Если условие задачи является утверждением, то в задаче требуется это 
утверждение доказать. 

Эта заметка представлялась П. Дергачом и авторами в виде цикла задач на Летней 
Конференции Турнира Городов в августе 2007 (до промежуточного финиша 
предлагалось первое отступление и доказательство построимости, а после --- 
доказательство непостроимости). 
Сокращенный английский перевод (выполненный П. Дергачом и А. Скопенковым) 
доступен на 
www.mccme.ru/circles/oim/materials/constreng.pdf.  

Благодарим Э. Б. Винберга, М. Н. Вялого, А. С. Голованова, П. А. Дергача, 
А. И. Ефимова, А. А. Казначеева, В. В. Прасолова и Г. Челнокова за полезные 
обсуждения. 


\bigskip
{\bf Философское отступление.} 

Изложение доказательства теоремы Гаусса на языке 'групп Галуа' делает его 
менее доступным. 
Более того, мне кажется, что именно с доказательств, подобных приведенным 
здесь (а не с терминов), полезно начинать изучение теории Галуа. 

{\it 'При изложении материала нужно ориентироваться на объекты, которые 
основательнее всего укореняются в человеческой памяти. 
Это --- отнюдь не системы аксиом и не логические приемы в доказательстве 
теорем. 
Изящное решение красивой задачи, формулировки которой ясна и доступна, имеет 
больше шансов удержаться в памяти студента, нежели абстрактная теория. 
Скажем больше, именно по такому решению, при наличии некоторой математической 
культуры, студент впоследствии сможет восстановить теоретический материал. 
Обратное же, как показывает опыт, практически невозможно'} [Ko, предисловие].   

Мне кажется, такой стиль изложения не только сделает материал более 
доступным, но позволит сильным студентам (для которых доступно даже абстрактное 
изложение) приобрести математический вкус и стиль с тем, чтобы разумно выбирать 
проблемы для исследования, а также ясно излагать собственные открытия, не 
скрывая ошибки (или известности полученного результата) за чрезмерным 
формализмом. 
К сожалению, такое (бессознательное) сокрытие ошибки часто происходит с 
молодыми математиками, воспитанные на чрезмерно формальных курсах (происходило 
и с автором этих строк; к счастью, почти все мои ошибки исправлялись {\it 
перед} публикациями). 

Приводимые порой в качестве приложений теории Галуа доказательство теоремы 
Гаусса и другие результаты о разрешимости уравнений в радикалах неубедительны 
для мотивировки этой теории (как и приложение к решению уравнений степени не 
выше четырех неубелительно для мотивировки общей теории разрешимости уравнений 
произвольной степени в радикалах). 
Действительно, теорема Гаусса имеет элементарное доказательство, не 
использующее 'групп Галуа'. 
Теорема Руффини-Абеля о неразрешимости в радикалах {\it общего} алгебраического 
уравнения степени 5 и выше (как и достаточность условия Кронекера 
неразрешимости в радикалах {\it конкретного} уравнения простой степени) также 
имеет алгебраическое доказательство, не использующее 'групп Галуа' [Ko, Pr] 
(и {\it топологическое} доказательство [Al]). 
В терминах теории Галуа формулируется общий критерий разрешимости 
{\it конкретного} алгебраического уравнения в радикалах, но этот критерий не 
дает настоящего решения проблемы разрешимости, а лишь сводит ее к трудной 
задаче вычисления группы Галуа уравнения. 

(Возможно, именно поэтому работы Галуа были забыты на 20 лет после их выхода 
--- пока не появилось важных задач, при решении которых уже трудно обойтись без 
теории Галуа. 
% (математика 19-го века была гораздо ближе к естествознанию). 
Конечно, приведенная гипотеза нуждается в серьезной проверке.)

Однако теория Галуа выходит далеко за рамки проблемы разрешимости уравнений в
радикалах. 
Ее популяризации послужит дальнейшая публикация интересных теорем, 
формулируемых без понятий теории Галуа, но при попытках доказать которые она 
естественно возникает. 
Примеры таких теорем мне сообщили А. Я. Белов, С. М. Львовский и Г. Р. Челноков
(к сожалению, в доступной мне начальной учебной литературе по теории Галуа мне 
не удалось найти такие теоремы, формулировка которых не была бы скрыта под 
толщей обозначений и терминов).  

%(процитирую отрывок из письма С. М. Львовского ко мне с разрешения автора). 
%{\it Teoriya Galois lezhit v osnove algebraicheskpi teorii chisel, i tem samym vse
%yeye dostizheniya teroiyu Galois ispo'zuyut. Hot' teorema Fermat, v konce 
%koncov. Galois lezhit gluboko-gluboko v fundamente, no bez neye tam nikuda. 
%Mozhno privesti, konechno, i kuda menee vozvyshennye primery. Skazhem, takoy: 
%mozhno li kubicheskiy koren' iz 2 predstavit' v vide lineynoy kombinacii s
%racional'nymi koefficientami sinusov uglov ot racional'nogo chisla gradusov? 
%Iz elementarnoy chasti teorii Galois (Lang, glava VII i nachalo glavy VIII) 
%reshenie poluchaetsya odnim shchelchkom, a kak sdelat' bez etogo --- ne znayu. 
%Ili tak: dan neprivodimiy mnogochlen stepeni $n$ s celymi koefficientami; 
%mnogo li takih prostyh $p$, chto po modulyu $p$ on raspadatetsya na $n$ 
%lineynyh mnozhiteley? (Tut uzhe tem, chto v Lang'e, ne oboydesh'sya.)}  

%Polemika o teorii Galua v dukhe Arnoljda uvlekatejna, khotja voznikaet
%oshhushhenie, chto odnim ne vpolne tochnym utverzhdenijam 
%protivopostavljaujtsja drugie, stolj zhe netohnyje. Naprimer, nejavno
%podrazumevaetsja, chto vsem chitateljam odinakovo ponjaten smysl termina
%`teorija Galua'. Otkryv uchebnik Lenga, vidim, chto osnovnym soderzhaniem 
%teorii Galua (dlja udobstva chitatelja izlozhennym na odnoj stranitse) 
%objavljaetsja vovse ne to, chto imeetsja v vidu v tvoem tekste. 
%Ignorirovatj ehto obstojateljstvo dovoljno stranno.




\bigskip
{\bf Отступление: связь с построениями циркулем и линейкой.}

\smallskip
{\bf A.} Используя отрезки длины $a$, $b$ и $c$, можно построить циркулем и 
линейкой отрезки длины $a+b$, $a-b$, $ab/c$, $\sqrt{ab}$.

\smallskip
Вещественное число называется {\it квадратичной иррациональностью}, 
%(над $Q$)
или {\it построимым}, если его можно получить на нашем калькуляторе 
(т.е. получить из 1 при помощи сложения, вычитания, умножения, деления и 
извлечения квадратного корня из положительного числа). 
Например, числа 
$$1+\sqrt2,\quad ^4\sqrt2=\sqrt{\sqrt2},\quad \sqrt{2\sqrt3},\quad 
\sqrt2+\sqrt3,\quad \sqrt{1+\sqrt2},\quad 
%1+\sqrt{3-2\sqrt2},\quad 
\frac1{1+\sqrt2}\quad\text{и}\quad \cos 3^\circ$$
построимы.
Про последние два числа это не совсем очевидно. 
% и будет доказано далее. 

\smallskip
{\bf B.} Любое построимое число построимо циркулем и линейкой (далее слова 
'циркулем и линейкой' опускаютя).

\smallskip
Этот простой (вытекающий из A) результат был известен еще древним грекам. 
Он показывает, что из 
{\it выразимости} в теореме Гаусса вытекает {\it построимость} соответствующих 
$n$-угольников. 

\smallskip
{\bf C*.} {\it Основная теорема теории геометрических
построений.} Обратное тоже верно.  

\smallskip
Этот несложный результат [Pr, Ko] (доказанный лишь в 19-м веке) 
показывает, что из {\it невыразимости} в теореме Гаусса вытекает 
{\it непостроимость} соответствующих $n$-угольников. 

Для его доказательства рассмотрите все возможные случаи появления новых 
объектов (точек, прямых, окружностей). 
Покажите, что координаты всех построенных точек и коэффициенты уравнений всех 
проведённых прямых и окружностей являются квадратичными иррациональностями.
См. детали в [Ko, Pr]. 


\smallskip
{\bf D.} Если комплексное число комплексно построимо (определение аналогично, 
только квадратные корни извлекаются из произвольных уже выраженных чисел и 
можно брать любое значение квадратного корня), то его вещественная и 
мнимая части (вещественно) построимы.

Указание. Если $\sqrt{a+bi}=u+vi$, то $u,v$ выражаются через 
квадратные радикалы через $a$ и $b$.

\smallskip
{\bf E.} Если правильный $mn$-угольник построим, то и правильный
$m$-угольник построим.

\smallskip
{\bf F.} Правильные 3-угольник и 5-угольник построимы.

\smallskip
{\bf G.} Правильный 120-угольник построим.
Или, эквивалентно, угол $3^\circ$ построим. 

Указание. Если не получается, то см. далее. 

\smallskip
{\bf H.} Если правильный $n$-угольник построим, то и правильный
$2n$-угольник построим.

Указание. Получается делением угла пополам или применением формулы 
половинного угла.


\smallskip
{\bf I.} Пусть правильные $m$- и $n$-угольники построимы, причем $GCD(m,n)=1$. 
Тогда правильный $mn$-угольник построим.

Указание. Так как $GCD(m,n)=1$, то существуют целые $a,b$ такие, что $am+bn=1$. 
%Поэтому из построимости углов $\frac{2\pi}m$ и $\frac{2\pi}n$ следует 
%построимость угла $\frac{2\pi}{mn}$.





\bigskip
{\bf Доказательство возможности в теореме Гаусса.}

\smallskip
Нетрудно доказать возможность в теореме Гаусса для $n\le16$. 

\smallskip
{\it Доказательство возможности в теореме Гаусса для $n=5$.} 
Видимо, приводимый способ сложнее придуманного Вами. 
Зато из него будет видно, что делать в общем случае. 
Достаточно выразить число $e=\cos\frac{2\pi}5+i\sin\frac{2\pi}5$. 
Сразу это сделать трудно, поэтому сначала построим некоторые многочлены от $e$. 
Мы знаем, что $e+e^2+e^3+e^4=-1$. 
Легко проверить, что $(e+e^4)(e^2+e^3)=e+e^2+e^3+e^4=-1$. 
Обозначим $A_0:=e+e^4$ и $A_1:=e^2+e^3$. 
Тогда по теореме Виета числа $A_0$ и $A_1$ являются корнями уравнения 
$t^2+t-1=0$. 
Поэтому можно выразить $A_0$ (и $A_1$). 
Поскольку $e\cdot e^4=1$, то по теореме Виета числа $e$ и $e^4$ являются 
корнями уравнения $t^2-A_0t+1=0$. 
Поэтому можно выразить $e$ (и $e^4$). 

\smallskip
{\bf 1.} Если число $2^m+1$ простое, то $m$ --- степень двойки.

\smallskip
{\it Идея доказательства построимости в теореме Гаусса.} 
Достаточно выразить число $e=\cos\frac{2\pi}n+i\sin\frac{2\pi}n$ для простого 
$n=2^m+1$ (тогда $m$ обязано быть степенью двойки). 

Сначала хорошо бы разбить сумму 
$$e+e^2+\dots+e^{n-1}=-1$$ 
на два слагаемых $A_0$ и $A_1$, {\it произведение} которых построимо (иными 
словами, {\it сгруппировать} хитрым образом корни уравнения 
$1+e+e^2+\dots+e^{n-1}=0$). 
Тогда $A_0$ и $A_1$ построимы по теореме Виета.  
Затем хорошо бы разбить сумму $A_0$ на два слагаемых $A_0=A_{00}+A_{01}$, 
произведение которых построимо, и аналогично разбить $A_1=A_{10}+A_{11}$. 
И так далее, пока не построим $A_{0\dots0}=e$. 

Однако придумать нужные группировки корней уравнения $1+e+e^2+\dots+e^{n-1}=0$ 
совершенно нетривиально и возможно не для всех $n$. 
Как это можно придумать, описано в [Ka]. 
Здесь я приведу лишь ответ, который очень прост. 

\smallskip
{\it Теорема о первообразном корне.} Для любого простого $p$ существует число 
$g$, для которого остатки от деления на $p$ чисел $g^1,g^2,g^3,\dots,g^{p-1}=1$ 
различны.

\smallskip
Как строить нужные группировки, видно из задач 3a, 4a и 5a ниже. 

\smallskip
{\bf 2.} {\it Доказательство теоремы о первообразном корне.} 
Пусть $p$ простое и $a$ не делится на $p$. 

(a) $p-1$ делится на наименьшее $k>0$, для которого $a^k\equiv1\ (p)$. 

Указание: используйте малую теорему Ферма. 

(b) Для любых целых $n$ и $a$ сравнение $x^n\equiv a\ (p)$ имеет не более $n$ 
решений.
%(b) Многочлен степени $n$ над $Z_p$ имеет не более $n$ корней.

(c) Если $p-1$ делится на $d$, то сравнение $x^d\equiv1\ (p)$
имеет ровно $d$ решений.

(d) Докажите теорему о первообразном корне для $p=2^m+1$. 
(Только этот частный случай нужен для теоремы Гаусса.)

(e)* Докажите теорему о первообразном корне для $p=2^m\cdot3^n+1$. 

(f)* Докажите теорему о первообразном корне для {\it произвольного} простого 
$p$. 

(g)* Верно ли, что число 3 является первообразным корнем по
модулю любого простого числа вида $p=2^m+1$?

\smallskip
Начиная с этого момента $p=2^m+1\ge5$ --- простое число и $g$ --- (любой) 
первообразный корень по модулю $p$.

\smallskip
{\bf 3.} 
(a) Положим   
$$A_0:=e^{g^2}+e^{g^4}+e^{g^6}+\dots+e^{g^{2^m}}\quad\text{и}\quad 
A_1:=e^{g^1}+e^{g^3}+e^{g^5}+\dots+e^{g^{2^m-1}}.$$ 
Докажите, что $A_0A_1=-\frac{p-1}4$.
(Следующие задачи являются подсказками.)  

(b) $g^k+g^l\equiv0\ (p)$ тогда и только тогда, когда 
$k-l\equiv\frac{p-1}2\ (p-1)$. 

(c) $A_0A_1=\sum\limits_{s=1}^{2^m}e^s\alpha(s),$ где $\alpha(s)$ 
равно числу решений $(k,l)$ (в вычетах по модулю $p-1$) сравнения 
$g^{2k}+g^{2l+1}\equiv s\ (p).$  

(d) $\alpha(s)=\alpha(gs)$.  

(e) $\alpha(s)$ не зависит от $s=1,\dots,2^m$. 

%Сравнение $g^{2k}+g^{2l+1}\equiv1\ (p)$ имеет столько же
%решений $(k,l)$ (в вычетах по модулю $p-1$), сколько сравнение
%$g^{2k}+g^{2l+1}\equiv g\ (p)$.


\smallskip
{\bf 4.}
(a) Положим 
$$A_{00}:=e^{g^4}+e^{g^8}+e^{g^{12}}+\dots+e^{g^{2^m}}\quad\text{и}
\quad A_{01}:=e^{g^2}+e^{g^6}+e^{g^{10}}+\dots+e^{g^{2^m-2}}.$$ 
Докажите,
что $A_{00}A_{01}=sA_0+tA_1$ 
%=\frac{p-1}8\pm\frac{s-t}2\sqrt p$ 
для некоторых целых чисел $s$ и $t$ ($s+t=\frac{p-1}8$).
(Следующая задача является подсказкой.)  

(b) Сравнение $g^{4k}+g^{4l+2}\equiv1\ (p)$ имеет столько же решений $(k,l)$ (в 
вычетах по модулю $p-1$), сколько сравнение $g^{4k}+g^{4l+2}\equiv g^2\ (p)$.

(c) Положим 
$$A_{10}:=e^{g^1}+e^{g^5}+e^{g^9}+\dots+e^{g^{2^m-3}}\quad\text{и}
\quad A_{11}:=e^{g^3}+e^{g^7}+e^{g^{11}}+\dots+e^{g^{2^m-1}}.$$ 
Докажите,
что $A_{10}A_{11}=uA_0+vA_1$ для некоторых целых чисел $u$ и $v$ 
($u+v=\frac{p-1}8$).

(d) Закончите доказательство возможности в теореме Гаусса. 

\smallskip
{\bf 5.} Найдите явно выражение через квадратные радикалы числа

(a) $A_0$ из задачи 3a. \quad (b) $\cos\dfrac{2\pi}{17}$. 
\quad (c)* $\cos\dfrac{2\pi}{257}$. \quad (d)* $\cos\dfrac{2\pi}{65537}$.

\smallskip
{\it При помощи приведенного метода и компьютера эту задачу можно решить 
быстро}, несмотря на следующую историю [Li].
"Один слишком навязчивый аспирант довел своего руководителя до
того, что тот сказал ему: "Идите и разработайте построение
правильного многоугольника с 65 537 сторонами". Аспирант удалился,
чтобы вернуться через 20 лет с соответствующим построением
(которое хранится в архивах в Геттингене)."

\smallskip
{\it Замечание.}
Построимость можно доказывать по тому же плану без использования комплексных 
чисел. 
Указание к случаю правильного 17-угольника. 
Положим $a_k=\cos(2\pi k/17)$. 
Тогда $a_k=a_{17-k}$, \ $2a_ka_l=a_{k+l}+a_{k-l}$ \ и 
\ $a_1+a_2+a_3+\dots+a_8=-1/2$. 
Сначала выразите $a_1+a_2+a_4+a_8$ и $a_3+a_5+a_6+a_7$. 
Затем выразите $a_1+a_4$, $a_2+a_8$, $a_3+a_5$ и $a_6+a_7$. 
Наконец, выразите $a_1$.






\bigskip
{\bf Указания и решения к некоторым задачам о построимости.}

\smallskip
{\it Указание к 1.} Если $n$ нечётно, то $2^{kn}+1$ делится на $2^k+1$.

\smallskip
{\it Указание к 2b.} 
Докажем более общее утверждение: {\it многочлен степени $n$ над $\Z_p$ не может 
иметь более $n$ корней в $\Z_p$.} 
Здесь многочленом называется набор его коэффициентов, а не функция. 
%('Доказательство', основанное на разложении 
%$P(x)=Q(x)(x-x_0)(x-x_1)\dots(x-x_n)$, обычно включает в себя порочный круг: 
%проанализируйте, как доказывается такое разложение.) 

Пусть многочлен $P(x)$ степени $n$ имеет в $\Z_p$ 
различные корни $x_1,\dots,x_n,x_{n+1}$. 
Представьте его в виде 
$$P(x)=b_n(x-x_1)\dots(x-x_n)+b_{n-1}(x-x_1)\dots(x-x_{n-1})+\dots+b_1(x-x_1)+
b_0$$ 
('{\it интерполяция Ньютона}'). 
Последовательно подставляя в сравнение $P(x)\equiv0\ (p)$ вычеты 
$x_1,\dots,x_n,x_{n+1}$, получим 
$b_0\equiv b_1\equiv \dots \equiv b_{n-1} \equiv b_n \equiv 0\ (p)$.

То же самое решение можно записать и так. 
Пусть $P$ --- многочлен. 
Тогда многочлен $P-P(a)$ делится на $x-a$, т.е. $P-P(a)=(x-a)Q$ для некоторого 
многочлена $Q$ с $\deg Q<\deg P$. 
Поэтому если $P(a)=0$, то $P=(x-a)Q$ для некоторого многочлена $Q$ степени 
меньше $\deg P$.
Теперь требуемое в задаче утверждение доказывается индукцией по степени 
многочлена $P$. 

\smallskip
{\it Первое указание к 2c.} Заметьте, что многочлен $x^{p-1}-1$ над $\Z_p$ имеет ровно 
$p-1$ корень и делится на $x^d-1$. 
Докажите, что если многочлен степени $a$ имеет ровно $a$ корней и делится на 
многочлен степени $b$, то этот многочлен степени $b$ имеет ровно $b$ корней. 

%=(x-1)(x-2)\dots(x-p+1)$ и $x^d-1|x^{p-1}-1$.
%Если $p-1=kd$, то вычеты $x^k,x^{2k},\dots,x^{kd}\equiv1$ являются корнями. 
%pochemu razlichny?
%Больше корней быть не может по вышедоказанной теореме. 

\smallskip
{\it Второе указание к 2c.} Если $p=kd$, то для любого $a$ сравнение 
$y^k\equiv a\ (p)$ имеет не более $k$ решений. 


\smallskip
{\it Указание к 2d.} Если первообразного корня нет, то по 2a сравнение 
$x^{2^{m-1}}\equiv1\ (p)$ имеет $p-1=2^m>2^{m-1}$ решений. 

\smallskip
{\it Указание к 2ef.} Аналогично 2d. 

\smallskip
{\it Замечание к 2f.} Из существования первообразного корня легко вывести, что 
для $p-1=p_1^{a_1}\dots p_k^{a_k}$
%. Пользуясь 2c и формулой включений-исключений, можно доказать, что 
первообразных корней ровно 
%$$(p-1)(1-\frac{1}{p_1}-\dots-\frac{1}{p_k}+\frac{1}{p_1p_2}+\dots+
%\frac{1}{p_{k-1}p_k}-\dots+(-1)^k \frac{1}{p_1p_2\dots p_k})=$$
$(p-1)(1-\frac{1}{p_1})\dots (1-\frac{1}{p_k})=\varphi(p-1)$.  

\smallskip
{\it Указание к 3c.} Раскройте скобки и сгруппируйте равные слагаемые.

\smallskip
{\it Указание к 3d.} Если $(a,b)$ --- решение сравнения 
$g^{2k}+g^{2l+1}\equiv s\ (p)$, то $(b+1,a)$ --- решение сравнения 
$g^{2k}+g^{2l+1}\equiv gs\ (p)$.
Если $(a,b)$ --- решение сравнения 
$g^{2k}+g^{2l+1}\equiv gs\ (p)$, то $(b,a-1)$ --- решение сравнения 
$g^{2k}+g^{2l+1}\equiv s\ (p)$.

\smallskip
{\it Указание к 5c.} (Написано с использованием текста И. Лукьянеца и 
В. Соколова.)
Положим 
$$\overline{i_0\dots i_x}:=i_02^0+\dots+i_x2^x \quad\text{и}\quad
A_{i_0\dots i_x}:=\sum\limits_{s=0}^{2^{m-s}} 
e^{g^{\overline{i_0\dots i_x}+s2^{x+1}}}.$$
Тогда $A_{i_0\dots i_x0}+A_{i_0\dots i_x1}=A_{i_0\dots i_x}$. 
При $x<m$ имеем 
$$A_{i_0\dots i_x0}A_{i_0\dots i_x1}=\sum\limits_{s=0}^{2^m}\alpha(s)e^s
=\sum_{(j_0\dots j_x)}b_{j_0\dots j_x}
A_{j_0\dots j_x}\quad\text{для некоторых}\quad b_{j_0\dots j_x}\in\Z.$$
Здесь в первом равенстве $\alpha(s)$ равно числу решений $(k,l)$ (в вычетах по 
модулю $p-1$) 
сравнения 
$$g^{\overline{i_0\dots i_x}+k2^{x+1}}+g^{\overline{i_0\dots i_x}+l2^{x+1}+2^x}
\equiv s\ (p).$$   
По 3b $\alpha(0)=0$ при $x<m$. 
Аналогично 3c $\alpha(s)=\alpha(sg^{2^x})$. 
Отсюда вытекает второе равенство. 




\bigskip
{\bf Доказательство невозможности в теореме Гаусса.}

\smallskip
Перед доказательствами теоремы Гаусса некоторые их идеи демонстрируются по 
одной и на простейших примерах (задачи 1, 2c и 3). 
Эти примеры, впрочем, дают решение классических задач древности об удвоении 
куба и трисекции угла, ждавших своего решения 2000 лет. 
Первое доказательство невозможности в теореме Гаусса намечено в задачах  
2ab и 4--7. 
Внешне другие (но по сути такие же) доказательства намечены в 
задачах 8-11 (используя 4, но не используя 6) и 13--16. 
Второе доказательство наиболее близко к идеям самого Гаусса. 
Задачи 17, 18 и 19 приводятся для общего развития. 
По поводу невыразимости через {\it вещественные} корни произвольной целой 
степени см. [Va]. 

%{\bf 6*.} Будет ли построимо число $\cos\frac{2\pi}n$, если к 
%{\it вещественному} 
%калькулятору добавить извлечение корня произвольной целой степени 
%(только положительного из положительных вещественных чисел)?  
%Ответ неизвестен автору даже для $n=9$. 
 
%калькулятору добавить извлечение корня произвольной целой степени 
%(только положительного из положительных вещественных чисел)?  
%Ответ неизвестен автору даже для $n=9$. 
%Рассмотрим 'первый нетривиальный случай' $n=13$ 
%(а потом посмотрим, как приведенная идея работает для произвольного $n$). 

\smallskip
{\bf 1.} Не существует рациональных чисел $a,b,c,d$, для которых
$^3\sqrt2=$

(a) $a+\sqrt b$; \quad (b) $a-\sqrt b$; \quad (c) $\dfrac1{a+\sqrt b}$; 
\quad (d) $a+\sqrt b+\sqrt c$;
\quad (e) $a+\sqrt b+\sqrt c+\sqrt{bc}$; \quad 

(f) $a+\sqrt{b+\sqrt c}$; \quad (g) $a+\sqrt b+\sqrt c+\sqrt d$. 

\smallskip
{\bf 2.} 
(a) Оторвем у (комплексного аналога) калькулятора из теоремы Гаусса кнопку 
'$:$', но разрешим использовать все рациональные числа. 
Тогда множество чисел, которые можно реализовать на калькуляторе, 
не изменится. 

(b) Число $A$ построимо тогда и только тогда, когда
существуют такие положительные $r\in\Z$ и $a_1,\ldots a_r\in\R$, что
$$\Q=Q_1\subset Q_2\subset Q_3\subset \ldots\subset Q_{r-1}\subset Q_r\supset
A,\quad\text{где}\quad a_k\in Q_k,\quad\sqrt a_k\not\in Q_k,$$
$$Q_{k+1}=Q_k[\sqrt a_k]:=\{\alpha+\beta\sqrt a_k\ |\ \alpha,\beta\in Q_k\}
\quad\text{для любого}\quad k=1,\dots,r-1.$$ 
Такая последовательность называется {\it цепочкой квадратичных расширений}
(это единый термин, термин 'квадратичное расширение' мы не используем). 

%Пусть $F\subset\R$ и уравнение $x^2=a$ не имеет решений в $F$
%(т.е. либо $a<0$, либо $\sqrt a\not\in F$). 
%число $a\in F$ {\it неквадратичное}
%{\it Квадратичным расширением поля $F$ по числу $a$} называется поле 
%начинающаяся с $\Q$ и захватывающая $\alpha$, т.е. когда

(c) $^3\sqrt2$ непостроимо. 
(Значит, удвоение куба циркулем и линейкой невозможно.) 

\smallskip
{\bf 3.} (a) Число $\cos(2\pi/9)$ является корнем уравнения $8x^3-6x+1=0$.

(b) Не существует рациональных чисел $a$ и $b$, для которых
$\cos(2\pi/9)=a+\sqrt b$. 

%(c) Не существует рациональных чисел $a,b,c$, для которых
%$\cos(2\pi/9)=a+\sqrt{b+\sqrt c}$.

(c) Число $\cos(2\pi/9)$ не построимо (значит, трисекция угла $\pi/3$ циркулем 
и линейкой невозможна и правильный 9-угольник не построим).

(d) Корни кубического уравнения с рациональными коэффициентами 
построимы тогда и только тогда, когда один из них рационален.


\smallskip
{\bf 4.} {\it Лемма о сопряжении.} 
%Пусть $F$ --- поле и $F[\sqrt a]$ --- его квадратичное расширение. 
В обозначениях задачи 2b положим $a=a_k$ и определим отображение сопряжения
$\overline\cdot:Q_k[\sqrt a]\to Q_k[\sqrt a]$ формулой 
$\overline{x+y\sqrt a}=x-y\sqrt a$. Тогда

(a) Это определение корректно.

(b) $\overline{z+w}=\overline z+\overline w$, \quad 
$\overline{zw}=\overline z\overline w$ \quad и \quad 
$\overline z=z\Leftrightarrow z=x+0\sqrt a\in Q_{k-1}$.

(c) Если $z\in Q_k[\sqrt a]$ --- корень многочлена $P$ с
рациональными коэффициентами, то $P(\overline z)=0$.

(Сравните с леммой о комплексных корнях многочлена с вещественными 
коэффициентами.) 


\smallskip
{\bf 5.} 
(a) Многочлен $\Phi(x):=x^{12}+x^{11}+\dots+x+1$ неприводим над $\Q$. 

Указание: если не получается, то используйте лемму Гаусса и признак Эйзенштейна 
(см. ниже). 

(b) Если $e=\cos(2\pi/13)+i\sin(2\pi/13)$ построимо, то существует такая 
цепочка $\Q=Q_1\subset Q_2\subset\ldots\subset Q_k\subset Q_{k+1}$
квадратичных рассширений, что $\Phi$ приводим над $Q_{k+1}$ и неприводим над 
$Q_k$.   

(c) Если $\Phi$ делится на многочлен $P$ с коэффициентами в $Q_{k+1}$, то 
$\Phi$ делится на сопряженный (относительно $Q_k$) многочлен $\overline P$. 

(d) Если многочлен $R$ c коэффициентами из $Q_{k+1}$ неприводим, то сопряженный 
(относительно $Q_k$) многочлен $\overline R$ неприводим.

%$GCD(R,\overline R)=1$.
%c) либо $P=Q$, либо $P=Q\bar{Q}$.  d) либо $deg(Q)=n$, либо $deg(Q)=n/2$.
%($\gamma$) Если $n$ не степень двойки, то корни многочлена $P$ не построимы.

(e) Разложение многочлена $\Phi(x)$ над $Q_{k+1}$ на неприводимые над $Q_{k+1}$ 
множители cсостоит из двух сопряженных (относительно $Q_k$) множителей. 

(f) Для каждого из этих множителей существует цепочка, аналогичная (b), но, 
возможно, с другим $k$. 

(g) Число $\cos(2\pi/13)$ не построимо. 

\smallskip
{\bf 6.} (a) {\it Лемма Гаусса.} Если многочлен с целыми коэффициентами 
неприводим над $\Z$, то он неприводим и над $\Q$ [Pr]. 

(b) {\it Признак Эйзенштейна.} Пусть $p$ простое. Если для многочлена с целыми 
коэффициентами старший коэффициент не делится на $p$, остальные делятся 
на $p$, а свободный член не делится на $p^2$, то этот многочлен неприводим над 
$\Z$
[Pr]. 


\smallskip
{\bf 7.} 
(a) Минимальная степень многочлена, корнем которого 
является данное построимое число, является степенью двойки.  
%Выведите из этого невозможность в теореме Гаусса.  

(b) Число $\cos(2\pi/n)$ не построимо для $n$ простого, $n\ne2^m+1$. 

(c) Многочлен $\Phi(x)=1+x^{17}+x^{34}+x^{51}+\dots+x^{272}$ неприводим над 
$\Q$. 

Указание: используйте лемму Гаусса и признак Эйзенштейна. 

(d) Число $\cos(2\pi/289)$ не построимо.

(e) Докажите невозможность в теореме Гаусса.  



\bigskip
{\bf Другие доказательства невозможности в теореме Гаусса.}

\smallskip
{\bf 8.} Число $\cos(2\pi/7)$ не построимо 
(значит, правильный 7-угольник не построим). 

\smallskip
{\bf 9.} Пусть $n=4k+3$ простое. Обозначим $f_s=e^s+e^{-s}$. 
Назовем {\it рангом} квадратичной иррациональности наименьшую длину 
минимальной цепочки из 2b. 
%Наименьшее из таких чисел $n$ называется {\it рангом}
%квадратичной иррациональности $\alpha$ и обозначается $\rk\alpha$.

(a) Для любого $k$ число $f_1^k+f_2^k+\dots+f_{(p-1)/2}^k$ рационально. 

(b) После раскрытия скобок и приведения подобных в выражении 
$(x-f_1)(x-f_2)\dots(x-f_{(p-1)/2})$ получается многочлен с рациональными 
коэффициентами. 

(c) Ранги чисел $e,e^2,\dots,e^{p-1}$ одинаковы. 

(d) Ранги чисел $f_1,\dots,f_{(p-1)/2}$ одинаковы. 

(e) Число $\cos(2\pi/n)$ не построимо

\smallskip
{\bf 10.} Обозначим $e=\cos(2\pi/13)+i\sin(2\pi/13)$, $g=2$ --- 
первообразный корень по модулю 13, 
$$A_0=e^{g^0}+e^{g^3}+e^{g^6}+e^{g^9},
\quad A_1=e^{g^1}+e^{g^4}+e^{g^7}+e^{g^{10}}\quad\text{и}
\quad A_2=e^{g^2}+e^{g^5}+e^{g^8}+e^{g^{11}}.$$ 
$$(a)\quad A_0^2=4+A_1+2A_2,\quad A_1^2=4+A_2+2A_0\quad\text{и}
\quad A_2^2=4+A_0+2A_1.$$
(b) Числа $A_0,A_1,A_2$ являются корнями неприводимого кубического уравнения с 
рациональными коэффициентами. 

(c) Числа $A_0,A_1,A_2$ имеют одинаковый ранг. 

(d) Число $\cos(2\pi/13)$ не построимо. 

\smallskip
{\bf 11.} Число $\cos(2\pi/p)$ не построимо для 

(a) $p=3\cdot 2^k+1$ простого.

(b) $p$ простого, $p\ne2^m+1$. 

(c) $p=289$.

(d) числа $p$, не являющегоеся произведением степени двойки и различных 
простых чисел вида $2^m+1$.


\smallskip
Идея еще одного доказательства невозможности в теореме Гаусса выражается 
понятиями {\it поля} и {\it размерности поля}.

\smallskip
{\bf 13.} 
{\it Полем} (числовым) называется подмножество множества $\C$ комплексных 
чисел, замкнутое относительно сложения, вычитания, умножения и деления.

(a) Следующие множества являются полями: $\Q$, множество построимых 
чисел, множество вещественных чисел, 
$\Q[\sqrt2]:=\{\alpha+\beta\sqrt 2\ |\ \alpha,\beta\in\Q\}$, 
каждое $Q_k$ в цепочке квадратичных расширений и 
$$\Q[e]:=\{\alpha_0+\alpha_1e+\alpha_2e^2+\alpha_3e^3+\dots+\alpha_{12}e^{12}
\ |\ \alpha_i\in\Q\},\quad\text{где}
\quad e=\cos\dfrac{2\pi}{13}+i\sin\dfrac{2\pi}{13}.$$
(b) Любое поле содержит поле $\Q$.

(c) Любое поле, содержащее $\sqrt2$, содержит $\Q[\sqrt2]$. 

(d) Любое поле, содержащее $e$, содержит $\Q[e]$. 

\smallskip
{\bf 14.} {\it Размерностью} $\dim F$ поля $F$ называется наименьшее $k$, для 
которого существуют такие 
$$b_2,b_3\dots,b_k\in F,\quad\text{что}
\quad F=\{\alpha_1+\alpha_2b_2+\alpha_3b_3+\dots+\alpha_kb_k\ |
\ \alpha_i\in\Q\},$$ 
если такое $k$ существует. 

(a) $\dim\Q=1$. 

(b) $\dim\Q[\sqrt2]=2$. 

(c) В цепочке квадратичных расширений $\dim Q_k=2\dim Q_{k-1}$ при $k\ge1$. 

(d) В цепочке квадратичных расширений $\dim Q_k=2^{k-1}$. 

(e)* Если $G\subset F$ --- поля, то $\dim F$ делится на $\dim G$. 

\smallskip
{\bf 15.} (a) $\dim\Q[\cos\dfrac{2\pi}{13}+i\sin\dfrac{2\pi}{13}]\le12$. 

(b) Если $\dim\Q[\cos\dfrac{2\pi}{13}+i\sin\dfrac{2\pi}{13}]<12$, то $P(e)=0$ 
для некоторого многочлена $P$ с рациональными коэффициентами степени меньше 12.

(c) Выведите из предыдущих пунктов, что число $\cos(2\pi/13)$ не построимо. 

\smallskip
{\bf 16.} (a) $\dim\Q[\cos\dfrac{2\pi}{289}+i\sin\dfrac{2\pi}{289}]=272$. 

(b) Выведите из предыдущих пунктов, что число $\cos(2\pi/289)$ не построимо. 

(c) Докажите невозможность в теореме Гаусса. 

\smallskip
{\bf 17.} (a) Многочлены $P$ и $Q$ с рациональными коэффициентами
имеют общий корень, $\deg P=3$, $\deg Q=2$. 
Докажите, что многочлен $P$ имеет рациональный корень.

(b) То же с заменой рациональных коэффициентов и корня на коэффициенты и 
корень из произвольного поля. 

(c) %{\it Лемма о четности.} 
Если все корни неприводимого многочлена нечетной степени с рациональными 
коэффициентами построимы, то один из них рационален. 

(d)* Корни многочлена 4-ой степени с рациональными коэффициентами 
построимы тогда и только тогда, когда его {\it кубическая резольвента} 
[Ko, Pr] имеет рациональный корень.


\smallskip
{\bf 18.} Любое построимое число является алгебраическим, т.е. корнем 
некоторого многочлена с целыми коэффициентами. 
(Из этого и доказанной в 1883 г. Линдеманом трансцендентности числа $\pi$, 
влекущей трансцендентность числа $\sqrt{\pi}$, вытекает, что задача о 
квадратуре круга неразрешима циркулем и линейкой.) 

%\bigskip
%\centerline{\uppercase{\bf Дополнительные задачи}}

\smallskip
{\bf 19.}
(a) (Г. Челноков) Лешин калькулятор получается из комплексного гауссова 
добавлением кнопки извлечения кубического корня из комплексных чисел (которая 
дает все три значения корня). 
Гришин калькулятор получается из комплексного гауссова 
добавлением кнопки нахождения по комплексному числу $a$ всех трех комплексных 
корней уравнения $a=\dfrac{3x-4x^3}{1-3x^2}$. 
Будет ли множество 'Лешиных' чисел совпадать с множеством 'Гришиных'? 

(b) (Г. Челноков) Неприводимый над $\Q$ многочлен раскладывается над 
$\Q[^4\sqrt2]$ ровно на четыре множителя.  
Докажите, что степень этого многочлена делится на 8. 
%(a) 4; \quad (b) 8. 








\bigskip 
{\bf Указания и решения к некоторым задачам о невозможности.}

\smallskip
{\it Указание к 1c.} Домножьте на сопряженное. 

\smallskip
{\it Указание к 2a.} 
Индукция по количеству операций калькулятора, необходимых для получения числа, 
с применением домножения на сопряженное. 

\smallskip
{\it Указание к 2b.} Это несложное следствие задачи 2a. 

\smallskip
{\it Решение 2c.}
Предположим, что $ ^3\sqrt2$ построимо. 
Тогда существует такая цепочка квадратичных расширений
$$\Q=Q_1\subset Q_2\subset Q_3\subset\ldots\subset Q_{r-1}\subset Q_r,\quad
\text{что}\quad ^3\sqrt2\in Q_r\setminus Q_{r-1}.$$ 
Поскольку $^3\sqrt2\not\in \Q$, то $r\ge2$. 
Значит, $$^3\sqrt2=\alpha+\beta\sqrt a,\quad \text{где}\quad \alpha,\beta,a\in Q_{r-1},
\quad \sqrt a\not\in Q_{r-1}
\quad \text{и} \quad \beta\ne0.$$ 
Отсюда
$$2=(^3\sqrt2)^3=(\alpha^3+3\alpha\beta^2a)+(3\alpha^2\beta+\beta^3a)\sqrt a=
u+v\sqrt a.$$ 
Поскольку $2\in\Q\subset Q_{r-1}$, то $2-u\in Q_{r-1}$. 
Так как $$v\sqrt a=2-u \quad \text{и} \quad 
v\in Q_{r-1}, \quad \text{то} \quad 0=v=3\alpha^2\beta+\beta^3a.$$ 
Так как $3\alpha^2+\beta^2a>0$, получаем $\beta=0$ --- противоречие!

\smallskip
{\it Указание к 3a.} Выразите $\cos3\alpha$ через $\cos\alpha$. 

\smallskip
{\it Указание к 3b.} Если $\cos(2\pi/9)=a+\sqrt b$, то число $a-\sqrt b$ 
тоже является корнем уравнения $8x^3-6x+1=0$. Тогда по теореме Виета третий корень равен 
$-(a+\sqrt b)-(a-\sqrt b)=-2a\in\Q$. 

\smallskip
{\it Решение 3c.} Следует из 3a и 3d. 

\smallskip
{\it Доказательство теоремы 3d о кубических уравнениях для уравнений, все три корня которых вещественны
(этот частный случай достаточен для непостроимости правильного 9-угольника).} 
Часть 'тогда' очевидна. 
Чтобы доказать часть 'только тогда', предположим, что хотя бы один из корней построим. 
Для каждого из построимых корней $z$ рассмотрим минимальную цепочку расширений  
$$\Q=Q_1\subset Q_2\subset Q_3\subset\ldots\subset Q_{r-1}\subset Q_r,\quad
\text{для которой}\quad z_1\in Q_r\setminus Q_{r-1}.$$ 
Возьмем корень $z=z_1$ с наименьшей длиной минимальной цепочки $l$. 

Если уравнение не имеет рациональных корней, то $l\ge2$. 
Значит, $$z_1=\alpha+\beta\sqrt a,\quad\text{где}\quad \alpha,\beta\in Q_{l-1},\quad\sqrt a\not\in Q_{r-1}\quad \quad\text{и}\quad \beta\ne0.$$

Тогда число $\overline z_1=\alpha-\beta\sqrt a$ также является
корнем рассматриваемого уравнения (по лемме о сопряжении). 
Поскольку $\beta\ne0$, то $\alpha-\beta\sqrt a\ne\alpha+\beta\sqrt a$, т. е. 
$\overline z_1\ne z_1$. 
Обозначим $z_2:=\overline z_1$. 
Из первой формулы Виета для нашего уравнения находим:
$$z_1+z_2+z_3=(\alpha+\beta\sqrt a)+(\alpha-\beta\sqrt a)+z_3=2\alpha+z_3\in\Q,
\quad\text{поэтому}\quad z_3\in Q_{l-1}.$$ 
Следовательно, для корня $z_3$ существует цепочка меньшей длины, чем для $z_1$. 
Противоречие.  
%(удобно считать, что для $z\not\in\Q_\infty$ соответствующая длина равна бесконечности).
\qed


\smallskip
{\it Указание к 5a.} Примените признак Эйзенштейна к многочлену 
$((x+1)^{13}-1)/x$ и лемму Гаусса.  

\smallskip
{\it Решение 5b.} Рассмотрим цепочку квадратичных расширений 
$\Q=Q_1\subset Q_2\subset\ldots\subset Q_{r-1}\subset Q_r\supset e$.
Заметим, что многочлен $\Phi$ приводим над $Q_r$ (поскольку имеет корень $e$).
Поэтому существует $l$, для которого многочлен $\Phi$ приводим над $Q_{l+1}$.
Обозначим через $k$ наименьшее такое $l$.
Из пункта 5a следует, что $k\ge1$. 
Теперь легко видеть, 
что цепочка  $\Q=Q_1\subset Q_2\subset\ldots\subset Q_k\subset Q_{k+1}$ искомая.

\smallskip
{\it Указание к 5c.} Сопрягите относительно $Q_k$ равенство $\Phi(x)=P(x)R(x)$.

\smallskip
{\it Указание к 5d.} Достаточно доказать, что если многочлен $P$ с коэффициентами в $Q_{k+1}$
делит $\Phi$, то $P$ и $\overline P$ взаимно просты. Для этого покажите, что 
$НОД(P,\overline P)$ имеет коэффициенты из $Q_k$ и воспользуйтесь неприводимостью
многочлена $\Phi$ в $Q_k$. 

\smallskip
{\it Решение 5e.} Аналогично решению 5b.

\smallskip
{\it Указание к 5f.} Докажите, что указанное в пункте 5d разложение многочлена $\Phi(x)$ 
состоит ровно из двух множителей (воспользуйтесь тем, что если коэффициенты многочлена $P$ 
лежат в $Q_{k+1}$, то коэффициенты многочлена $P \overline P$ лежат в $Q_k$). 
То же самое будет верно и для разложения получившихся множителей и т.д. 
Исходя из этого получите, что степень многочлена $\Phi(x)$ должна быть степенью двойки.

\smallskip
{\it Указание к 5g.} Аналогично 5f.

\smallskip
{\it Указание к 6b.} Предположите противное и воспользуйтесь методом
неопределённых коэффициентов.

\smallskip
{\it Указание к 7a.} 
Примените признак Эйзенштейна к многочлену $\Phi(x+1)$ и лемму Гаусса. 

\smallskip
{\it Указание к 7b.} Аналогично решению задачи 5 докажите, что если 
число $\cos\dfrac{2\pi}{289}$ построимо, то степень многочлена $\Phi(x)$ 
должна быть степенью двойки. А это неверно.

\smallskip
{\it Решение 8.} 
Рассмотрим комплексное число $e=\cos(2\pi/7)+i\sin(2\pi/7)$. 
Так как $e\ne1$, то число $e$ удовлетворяет уравнению 6-ой степени
$e^6+e^5+e^4+e^3+e^2+e+1=0$. 
Разделим обе части уравнения на $e^3$. 
Положим
$$f:=e+e^{-1},\quad\text{тогда}\quad e^2+e^{-2}=f^2-2\quad\text{и}
\quad e^3+e^{-3}=f(e^2+e^{-2}-1).$$ 
Получим кубическое уравнение
$$f(f^2-3)+(f^2-2)+f+1=0,\quad\text{то есть}\quad f^3+f^2-2f-1=0.$$
Кандидаты на рациональные корни этого уравнения $f=\pm1$
отвергаются проверкой. 
Согласно теореме 3d о кубических уравнениях число $f=e+e^{-1}$ не построимо. 
Поэтому и $e$ не построимо (поясните). 

\smallskip
{\it Указание к 9a.} Индукция по $k$.

\smallskip
{\it Указание к 9b.} Следует из пункта 9a и из того, что любой 
симметрический многочлен от переменных $f_1, f_2, \dots, f_{(p-1)/2}$ рационально выражается через многочлены вида $f_1^k+f_2^k+\dots+f_{(p-1)/2}^k$.

\smallskip
{\it Решение 9c.} 
Так как для любых $s,t\in\{1,2,\dots,p-1\}$ существует такое $k$, что 
$e^s=(e^t)^k$, то ранги чисел $e,e^2,\dots,e^{p-1}$ одинаковы. 

\smallskip
{\it Решение 9d.} 
Так как $e^s+e^{-s}$ рационально выражается через $e+e^{-1}$, то для любых 
$s,t\in\{1,2,\dots,p-1\}$ число $e^s+e^{-s}$ рационально выражается через 
$e^t+e^{-t}$ (аналогично приведенному решению задачи 8). 
Поэтому ранги чисел $f_1,\dots,f_{(p-1)/2}$ одинаковы. 

(Заметим, что $rk(e+e^{-1})=rk e-1$.)

\smallskip
{\it Решение 9e.} 
Пусть $r:=\rk f_s$. 
Значит, для некоторой цепочки квадратичных рассширений 
$$f_s=\alpha_s+\beta_s\sqrt a,\quad\text{где}\quad
\alpha_s,\beta_s,a\in Q_{r-1},\quad 
\sqrt a\not\in Q_{r-1}\quad\text{и}\quad\beta_s\ne0.$$
Тогда число $\overline f_s=\alpha_s-\beta_s\sqrt a$ также является
корнем рассматриваемого многочлена (по лемме о сопряжении). 
Поскольку 
$$\beta_s\ne0,\quad\text{то}\quad
\alpha_s-\beta_s\sqrt a\ne\alpha_s+\beta_s\sqrt a,
\quad\text{т. е.}\quad \overline f_s\ne f_s.$$ 
Итак, корни $f_1,\dots,f_{(p-1)/2}$ разбиваются на пары сопряженных. 
Значит, $(p-1)/2$ четно --- противоречие. 

Другое окончание решения. 
Числа $f_1,\dots,f_{(p-1)/2}$ являются корнями многочлена с рациональными 
коэффициентами. 
Так как $p=4k+3$, то по задаче 17с одно из них $f_s$ является 
рациональным. 
Но тогда $e^s$ является корнем квадратного уравнения с рациональными 
коэффициентами. 
Значит, многочлен $1+x+x^2+x^3+\dots+x^{p-1}$ приводим над $\Q$ --- 
противоречие. 
(Видимо, достаточное здесь отсутствие делителей степени 2 у 
многочлена $1+x+x^2+x^3+\dots+x^{p-1}$ можно доказать проще.) 

%\smallskip
%Было бы интересно доказать аналогично непостроимость для простого $n=8k+5$ 
%(и дале для общего случая). 
%Делаем те же группировки на сопряженные, 
%начиная с множества $e^s$, где $1\le s\le288$ и $s$ не делится на 17.  
%Будем использовать обозначения из решения задачи 6b. 
%Обозначим через $g_1,\dots,g_{(p-1)/4}$ суммы чисел в каждой паре сопряженных 
%(отноcительно $Q_{n-1}$) корней, т.е. $g_t=f_s+\overline f_s$. 

%Хорошо бы доказать, что ранги чисел $g_1,\dots,g_{(p-1)/4}$ одинаковы. 
%Тогда аналогично предыдущему эти числа разбиваются на пары сопряженных. 
%Поэтому $p-1$ делится на 8 --- противоречие.  

%Для доказательства одинаковости рангов достаточно показать, что 
%$\rk g_t=\rk f_s-1$. 
%Ясно, что $\rk g_t=f_s+\overline f_s\le \rk f_s-1$. 
%Хочется доказать, что $\rk f_s\le \rk g_t+1$. 

%(Действительно, 
%$$f_s=\alpha+\beta\sqrt a,\quad\overline f_s=\alpha-\beta\sqrt a,\quad
%\text{поэтому}\quad f_s\overline f_s=\alpha^2-a\beta^2\in Q_{n-1},$$ 
%а число $f_s$ является корнем квадратного уравнения 
%$z^2-g_tz+f_s\overline f_s=0$. Ну и что?) 

\smallskip
{\it Решение 10a.} Докажем первую фомулу (остальные доказываются аналогично).
Заметим, что $g^6=-1$. Поэтому 
$$A_0^2=((e^{g^0}+e^{-g^0})+(e^{g^3}+e^{-g^3}))^2 =$$
$$\underset {(*)}\to=2+e^{g^1}+e^{-g^1}+2+e^{g^4}+e^{-g^4}+2(e^{g^0}+e^{g^6})(e^{g^3}+e^{g^9})=4+A_1+2A_2.$$
Последнее равенство верно, поскольку 
$$(e^{g^0}+e^{g^6})(e^{g^3}+e^{g^9})=e^{g^0+g^3}+e^{g^3+g^6}+e^{g^6+g^9}+e^{g^9+g^0}=
e^{g^0+g^3}A_0\underset {(*)}\to=e^{g^8}A_0=A_2.$$
(Равенства $(*)$ выполнены, поскольку $g=2$.)

\smallskip
{\it Указание к 10b.} Докажите, что $A_0+A_1+A_2$,\quad $A_0^2+A_1^2+A_2^2$, 
\quad $A_0^3+A_1^3+A_2^3$ рациональны.

\smallskip
{\it Указание к 10с.} Пользуясь пунктом 10a и тем, что $A_0+A_1+A_2=-1$, 
докажите, что любое $A_i$ рационально выражается через любое $A_j$.

\smallskip
{\it Указание к 10d.} Решение получается из пунктов 10b и 10c аналогично 
решению задачи 9e.

Вот идея другого решения, не использующего пункт 10c. 
Пусть число $A_0$ имеет ранг $r$.
Сопряжём его относительно $Q_{r-1}$. Полученное число будет одним 
из чисел $A_i$ (поясните).  Теперь легко понять, что числа $A_i$ разбиваются 
на пары сопряжённых, т.е. их чётное число, что неверно.  


\smallskip
{\it Указание к 11а.} Аналогично задаче 10.

\smallskip
{\it Указание к 11b.} Предположите, что для $p=2^kr+1$ число 
$\cos\dfrac{2\pi}{p}$ построимо (где $r>1$ --- нечетное число). 
Выведите из этого, что числа
$$A_i=e^{g^i}+e^{g^{r+i}}+\dots+e^{g^{(2^k-1)r+i}},\quad 0\le i \le r-1$$
имеют одинаковый ранг и являются корнями мнгочлена степени $r$ с рациональными
коэффициентами.

\smallskip
{\it Указание к 11c.} Рассмотрите числа
$$A_0=e^{g^0}+e^{g^{17}}+\dots+e^{g^{272}},
\quad A_1=e^{g^1}+e^{g^{18}}+\dots+e^{g^{273}},
\quad A_{16}=e^{g^{16}}+e^{g^{33}}+\dots+e^{g^{288}}.$$ 

%\smallskip
{\it Указание к 12.} Решение аналогично решению задачи 5.

\smallskip
{\it Указание к 14c.} Докажите, что  
$$Q_k=\{\alpha_1+\alpha_2b\ |\ \alpha_1,\alpha_2\in Q_{k-1}\}
\quad\text{для любого}\quad b\in Q_k-Q_{k-1}.$$  

%\smallskip
{\it Указание к 14d.} Следует из 14a и 14c.
  
\smallskip
{\it Указание к 14e.} 
{\it Размерностью} $\dim(F:G)$ поля $F$ над полем $G$ называется наименьшее 
$k$, для которого существуют такие 
$$b_1,b_2,\dots,b_k\in F,\quad\text{что}
\quad F=\{\alpha_1b_1+\alpha_2b_2+\alpha_3b_3+\dots+\alpha_kb_k\ |
\ \alpha_i\in G\},$$  
если такое $k$ существует. 
Докажите, что $\dim F=\dim G\dim(F:G)$. 

\smallskip
{\it Указание к 15b.} 
%Обозначим за $k$ $\dim\Q[\cos\dfrac{2\pi}{13}+i\sin\dfrac{2\pi}{13}]$.
Докажем, что существуют такие рациональные $a_0,a_1,\dots,a_{12}$, 
не все равные 0, что 
$$a_0+a_1e+\dots+a_{11}e^{11}=0.\quad \quad (*)$$
По определению размерности существуют такие 
$b_1,\dots,b_{11}\in\Q[\cos\dfrac{2\pi}{13}+i\sin\dfrac{2\pi}{13}]$ 
и $\alpha_{kl}\in\Q$, что 
$$e^{j-1}=\alpha_{j,1}b_1+\alpha_{j,2}b_2+\dots+\alpha_{j,11}b_{11}
\quad \text{для} \quad j=1,2,\dots,12.$$
Подставьте эти значения $e^i$ в $(*)$. Теперь приравняйте к 0 коэффициенты при 
$b_1,\dots,b_{11}$. Наконец, докажите, 
что полученная система уравнений имеет нетривиальное рациональное решение.

%$\alpha_{11}x_1+\alpha_{21}x_2+\dots+\alpha_{12,1}x_{12}=0,\quad
%\alpha_{12}x_1+\alpha_{22}x_2+\dots+\alpha_{12,2}x_{12}=0,\quad \dots,\quad
%\alpha_{1,k}x_1+\alpha_{2,k}x_2+\dots+\alpha_{12,k}x_{12}=0$
%имеет нетривиальное решение $(a_1,\dots,a_{12})$.
%Тогда $a_1+a_2e+\dots+a_{12}e^{11}=0$.

\smallskip
{\it Указание к 16a.} Решение аналогично решению задач 15ab. Воспользуйтесь 
неприводимостью многочлена $\Phi(x)=1+x^{17}+x^{34}+x^{51}+\dots+x^{272}$.

\smallskip
{\it Указание к 17a.} Пусть $a$=$a_1$ и $b$=$b_1$ --- построимые числа, а $P$ и $Q$ --- 
многочлены с рациональными коэффициентами минимальной степени, корнями которых 
являются соответственно $a$ и $b$. Пусть $a_2,\dots,a_m$ --- все остальные 
комплексные корни многочлена $P$, а $b_2,\dots,b_n$ --- все остальные комплексные корни многочлена $Q$.
Заметим, что 

$a+b$ --- корень многочлена $P(x-b_1) \dots P(x-b_n)$,

$a-b$ --- корень многочлена $P(x+b_1) \dots P(x+b_n)$,
 
$ab$ --- корень многочлена $P(\frac{x}{b_1}) \dots P(\frac{x}{b_n})$,

$\frac{a}{b}$ --- корень многочлена $P(xb_1) \dots P(xb_n)$,

$\sqrt{a}$ --- корень многочлена $P(x^2)$.

Осталось доказать следующее вспомогательное утверждение.

{\it Лемма.} Пусть $R(x,y)$ --- многочлен
от двух переменных с рациональными коэффициентами, а $b_1,b_2,\dots,b_n$ --- 
все комплексные корни многочлена $Q$ с рациональными коэффициентами. 
Тогда многочлен от одной переменной $R(x,b_1) R(x,b_2) \dots R(x,b_n)$ 
также имеет рациональные коэффициенты.

\smallskip
{\it Решение задачи 17b} аналогично решению задач 5bc. 

%\smallskip
%{\it Идея прямого решения задачи 17b.} 
%Для каждого корня рассмотрим минимальную цепочку квадратичных расширений, 
%аналогичную 3d. 
%Возьмем корень $z_1$ с {\it наибольшей} длиной минимальной цепочки. 
%Если уравнение не имеет рациональных корней, то $n\ge1$. 
%Значит, $z_1=\alpha+\beta\sqrt a$, где $\alpha,\beta\in Q_n$ и $\beta\ne0$.

%Тогда число $\overline z_1=\alpha-\beta\sqrt a$ также является
%корнем рассматриваемого уравнения (по лемме о сопряжении). 
%Поскольку $\beta\ne0$, то $\alpha-\beta\sqrt a\ne\alpha+\beta\sqrt a$, т. е. 
%$\overline z_1\ne z_1$. 
%Обозначим $z_2:=\overline z_1$. 

%Каждый из остальных корней либо лежит в $Q_{n-1}$, либо имеет сопряженную пару. 
%Как бы получить противоречие с неприводимостью???




\bigskip 
\centerline{\bf Литература}

[Al] В. Б.Алексеев, Теорема Абеля. (М: Наука, 1976)

[Ch] Н. Н. Чеботарев, Основы теории Галуа, 1934. 

[Ga] К. Ф. Гаусс, Арифметические исследования. 

[Gi] С. Гиндикин, Дебют Гаусса, Квант, 1972 N1. 

[Ka] А. Я. Канель, готовится. 

[Ki] А. А. Кириллов, О правильных многоугольниках, функции Эйлера и числах 
Ферма, Квант, 1977 N7 или 1994 N6. 

[Ko] В. А. Колосов, Теоремы и задачи алгебры, теории чисел и комбинаторики  
(М: Гелиос, 2001). 

[Li] Дж. Литлвуд, Математическая смесь. 

[Po] М. М. Постников, Теория Галуа. 

[Pr] В. В. Прасолов, Многочлены (М: МЦНМО, 1999, 2001, 2003)

[PS] В. В. Прасолов и Ю. П. Соловьев, 
Эллиптические функции и алгебраические уравнения (М.: Факториал, 1997).  

[Va] Б. Л. Ван дер Варден, Алгебра. 

[Vi] Э. Б. Винберг, Алгебра многочленов, Просвещение, 1980.






\end



Подсказками к решению некоторых из предыдущих задач являются
следующие понятия и задачи.

{\bf 11.} 
(a) В $\Q[\sqrt2]$ число $3+2\sqrt2$ квадратичное, а числа
$\sqrt2$, $1+\sqrt2$, $1-\sqrt2$ и $5+4\sqrt2$ неквадратичные.

(b) $F[\sqrt a]$ действительно является полем.
%Найдите $a$, такое что $\R[\sqrt a]=\C$.


(b) Найдите ранги квадратичных иррациональностей, приведенных в
качестве примера выше (не забудьте доказать минимальность цепочки
расширений!).

%(b) Существуют сколь угодно длинные цепочки последовательных квадратичных
%расширений поля $\Q$. (Например,
%$Q_0=\Q\subset Q_1=\Q[\sqrt2]\subset Q_2=Q_1[\sqrt{\sqrt2}]\subset\ldots.$)
%Конечно, существуют и более сложные цепочки расширений, однако при их
%построении каждый раз нужно устанавливать неквадратичность соответствующих
%элементов, а это не совсем просто.

(c) Существуют квадратичные иррациональности сколь угодно большого
ранга (например, $rk^{2^n}\sqrt2=n$).

(d)* Если $p_1,\dots,p_n$ --- различные простые числа, то
$\rk(\sqrt{p_1}+\sqrt{p_2}+\sqrt{p_3}+\ldots+\sqrt{p_n})=n$.


%{\bf 0.} Пусть $\varphi(n)$ --- количество натуральных чисел, меньших $n$
%и взаимно простых с $n$.
%(a) Если $p$ простое, то $\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$.
%(b) Если $m$ и $n$ взаимно просты, то $\varphi(mn)=\varphi(m)\varphi(n)$.
%(c) Найдите $\varphi(p_1^{k_1}p_2^{k_2}\dots p_m^{k_m})$.
%(d) Составьте таблицу значений $\varphi(n)$ для $n\le17$ и сравните с Задачей 2.
%(e) Найдите все $n$, такие что $\varphi(n)$ есть степень двойки.
%(указание: достаточно найти такие $n$ вида $n=p^k$).
%(f) Если число $2^l+1$ простое, то $l$ --- степень двойки.
%(g) Какие из чисел $2^{2^n}+1$ простые для $n\le5$?




%\newpage
\bigskip  \bigskip
\centerline{\it Курс А. Н. Землякова в ФМШ при МГУ (под редакцией
А. Б. Скопенкова).}
\bigskip
\centerline{\bf Алгебраическая теория геометрических построений.}

\smallskip
\hfill{\it --- Чему же вас учили?~--- спросила Алиса.}

\hfill{\it --- Сначала чихать и плясать, конечно,~--- ответил
Мок-Тартль,~--- затем}

\hfill{\it четырем действиям арифметики: Служению, Почитанию,
Угождению и Давлению.}

\hfill{\it Льюис Кэррол, Алиса в стране чудес}

\smallskip
Рассмотрим классические задачи на построение.

\smallskip
{\bf Построение правильного пятиугольника, т. е. построение
$x=\cos36^\circ$.} Рассмотрим треугольник $ABC$ с углами
$C=36^\circ$ и $A=B=72^\circ$. Проведем биссектрису $AD$, получим
треугольник $ABD$, подобный $ABC$. С одной стороны, если $AC=1$,
то $AB=2x$. С другой стороны, $CD=AD=AB=2x$, значит $BD=1-2x$. Из
подобия находим $\frac{1-2x}2=\frac{2x}1$, откуда $4x^2+2x-1=0$ и
$x=\frac{-1+\sqrt5}4$. Строим $x$ при помощи операций (1)-(5).

{\bf Построение правильного $n$-угольника, т.е. деление окружности
на $n$ равных дуг.} Центр окружности можно считать находящемся в
начале координат $O$, а радиус~--- равным 1. Требуется построить
точки с полярными координатами $(1,k\frac{2\pi}n)$, где
$k=1,2,\ldots,n-1$. Очевидно, достаточно построить только точку
$(1,\frac{2\pi}n)$, а она определяется своей координатой
$x=\cos\frac{2\pi}n$.

{\bf Удвоение куба.} Зная ребро куба, построить ребро другого
куба, имеющего вдвое больший объем: по $a=1$ построить $x$, т. ч.
$x^3=2a^3=2$, т. е. $x=^3\sqrt2$.

{\bf Квадратура круга.} Требуется построить квадрат, площадь
которого равна площади данного круга. Т. е. по $R=1$ построить $x$
т. ч. $x^2=\pi R^2=\pi$, т. е. $x=\sqrt\pi$.

{\bf Трисекция угла.} Данный угол $\alpha$ требуется разделить на
три равные части. В этой задаче данными можно считать 1 и
$\cos\alpha$, искомым~--- $x=\cos\frac\alpha3$. В частном случае
$\alpha=\frac\pi3$ можно ограничиться в качестве данного только
одним отрезком, 1, ибо отрезок $\cos\frac\pi3=\frac12$ можно сразу
построить.

\smallskip
Оказывается, {\it любая задача на построение сводится к задаче
построения отрезков данной длины.} Действительно, она сводится к
получению каких-то отрезков (сторон, радиусов и т. д.) или точек
(вершин, центров, точек касания и т. п.). Раз и навсегда нарисовав
на плоскости перпендикулярные оси $Ox$ и $Oy$, можно сказать, что
отыскание точки $(x,y)$ эквивалентно отысканию ее координат~---
отрезков $x$ и $y$. Таким образом, все искомые элементы в задачах
на построение можно считать отрезками~--- $x_1, x_2,\ldots, x_n$.
Условившись, ради определенности, откладывать их по оси $Ox$ от
точки $O$, мы можем сказать, что задача на построение заключается
в построении чисел $x_1, \ldots, x_n$ (или точек $(x_1,0), \ldots,
(x_n,0)$).

Аналогично, данные задачи на построение можно считать отрезками на
оси $Ox$. Выбрав один из них за единичный отрезок, мы можем
сказать, что данные~--- это числа $1, a_1, \ldots, a_m$.

Итак, задача на построение состоит в переходе с помощью конечного
числа применений циркуля и односторонней линейки от данных
элементов $1, a_1, \ldots, a_m$ к искомым $x_1, x_2, \ldots, x_n$.

Часто в задаче на построение задан только один отрезок, 1, и
требуется построить (точнее, достаточно построить) тоже только
один отрезок, $x$.

Например, задачи о построении правильного $n$-угольника, удвоении
куба и квадратура круга являются задачами типа $1\to x$. А вот
задача о трисекции угла является задачей типа $(1,a)\to x$.

\smallskip
{\bf Примеры осуществимых} с помощью циркуля и линейки {\bf
операций} с данными (или известными) отрезками (числами).

(1) $a,b\to a+b, a-b$.

(2) $a\to ma$, $m\in\Z$.

(3)  $a\to\frac an$, $n\in\Z$.
%$\Rightarrow a\to\frac mna=\alpha a$, $\alpha\in \Q$.

(4) $a,b,c\to x=\frac{ab}c$ (в частности, $x=ab$ при $c=1$ и
$x=\frac ac$ при $b=1$).

(5) $a,b\to\sqrt{ab}$ (в частности, $x=\sqrt a$ при $b=1$).

\smallskip
Этих операций уже достаточно для решения многих (как мы докажем
далее, всех разрешимых!) задач на построение. Например, теорема
Пифагора дает построение $a,b\to\sqrt{a^2+b^2}$, но такая операция
есть композиция операций (4), (1) и (5).

Итак, напрашивается следующий {\bf способ построений отрезка $x$
из отрезков $1,a_1,\ldots,a_m$.}

1. С помощью геометрического анализа составляем алгебраическое
уравнение $P(x)=0$, связывающее данные $1, a_1, \ldots, a_m$ с
искомым $x$.

2. Решаем уравнение $P(x)=0$~--- выписываем $x$ в явном виде (если
сможем).

3. Если формула для $x$ содержит только перечисленные операции
(1)-(5), то строим $x$ стандартными приемами.

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


\bigskip
\centerline{\bf Критерий разрешимости задач на построение.}

\smallskip
\hfill{\it Музыку я разъял как труп. Поверил я алгеброю гармонию.}

\hfill{\it (А. С. Пушкин, "Моцарт и Сальери").}

\smallskip
Примеры осуществимых операций показывают, что если число $x$ можно
получить из 1 при помощи умножения, деления и извлечения
квадратного корня, то $x$ построимо. Такие числа называются {\it
квадратичными иррациональностями}. Таким образом, чтобы доказать,
что построение $1\to x$ осуществимо, {\it достаточно} показать,
что $x$ является квадратичной иррациональностью. Заметим, что
существует много чисел, не являющихся квадратичными
иррациональностями. Это можно доказать из соображений мощности
(конкретные примеры $^3\sqrt2$ или $\pi$ будут рассмотрены далее).
К сожалению, пока мы не знаем, что числа, не являющиеся
квадратичными иррациональностями, не являются построимыми (или
являются таковыми). Поэтому возникают следующие вопросы.

А. Нельзя ли расширить список осуществимых операций (например,
как-нибудь добавить построение $a\to ^3\sqrt a$)? Иными словами,
можно ли, исходя из числа 1, циркулем и линейкой построить числа,
не являющиеся квадратичными иррациональностями?

Б. Любое или не любое число $x\in\R$ можно построить, исходя из
числа (отрезка) 1? Каково множество построимых чисел?

\smallskip
{\bf Основная теорема теории геометрических построений (ОТГП).}
{\it Отрезок $x$ можно построить с помощью циркуля и линейки,
исходя из отрезка 1, тогда и только тогда, когда число $x$ можно
получить из 1 при помощи умножения, деления и извлечения
квадратного корня (т.е. $x$ является квадратичной
иррациональностью).}

\smallskip
Таким образом, чтобы выяснить, разрешима или нет задача на
построение "$1\to x$", достаточно установить, является или нет
число $x$ квадратичной иррациональностью! Итак, построения на
плоскости с помощью циркуля и линейки тесно связаны с вопросом о
разрешимости уравнений в квадратных радикалах.

Перед тем, как доказывать необходимость в ОТГП, уточним понятие
построимого числа. Дело в том, что при геометрических построениях
иногда (и довольно часто) приходится брать или строить
произвольный вспомогательный элемент~--- отрезок или точку. В силу
произвольности мы всегда можем (и будем) выбирать в качестве таких
вспомогательных элементов рациональные отрезки и точки с
рациональными координатами. Ход и результат построения при этом
измениться не может, но зато мы освободимся от неконтролируемых
добавок в множество построенных чисел~--- от игры случая и воли.

Заметим, что если приходится выбирать точки вне уже начерченных
линий или отрезки, отличные от уже построенных, то, в силу всюду
плотности множества $\Q$ в $\R$, подобный произвол также можно
считать "рациональным".

Еще один вид "произвола" в построениях~--- когда выбирается
произвольная вспомогательная точка на одной из уже построенных
линий. Условимся  выбирать произвольную вспомогательную точку
$M=(x_0,y_0)$ на проведенной линии так, чтобы $x_0\in \Q$.

%147.
Идея доказательства необходимости в ОТГП такова: поскольку любое
геометрическое построение есть последовательность конечного числа
элементарных, простейших, шагов, мы перечислим все такие шаги и
затем выясним, какие числа присоединяются к уже построенным на
каждом из элементарных шагов.

Напомним, что все построения выполняются на плоскости с
зафиксированной прямоугольной системой координат $Oxy$.

\smallskip
{\bf Список всех элементарных шагов} (из которых, в той или иной
последовательности, состоит любое геометрическое построение).

А. Взятие произвольного отрезка $x_0$ или точки $(x_0,y_0)$.

Б. Проведение прямой $ax+by=c$ через две имеющиеся точки $A$ и
$B$.

В. Проведение окружности $(x-x_0)^2+(y-y_0)^2=R^2$ через имеющуюся
точку $(x_0,y_0)$ известным (заданным или построенным) радиусом
$R$.

Г. Взятие точки пересечения двух построенных прямых.

Д. Взятие точки пересечения проведенных прямой и окружности.

Е. Взятие точки пересечения двух проведенных окружностей.

Ж. Взятие произвольной точки на уже проведенной линии.

\smallskip
Точка $(x,y)$ называется квадратичной иррациональностью, если $x$
и $y$ являются квадратичными иррациональностями. Прямая или
окружность называется квадратичной иррациональностью, если все
коэффициенты уравнения этой линии (см. выше) являются
квадратичными иррациональностями.

Необходимость в ОТГП вытекает из следующей леммы.

%150.
\smallskip
{\bf Лемма.} {\it Если на некотором шаге построения все имеющиеся
на чертеже элементы (отрезки, точки, прямые и окружности) являются
квадратичными иррациональностями, то после следующего
элементарного шага все новые (взятые или построенные) элементы
снова являются квадратичными иррациональностями.}
%либо принадлежат какому-нибудь квадратичному расширению $F[\sqrt a]$ поля $F$.

\smallskip
{\it Доказательство.} В силу замечаний после формулировки ОТГП
утверждение леммы выполнено для элементарного шага А.

Если точку $M=(x_0,y_0)$ при "произвольном взятии" Ж мы берем на
прямой, то из $x_0\in\Q$ и уравнения прямой получаем, что $y_0$
является квадратичной иррациональностью (поясните). Если же $M$
берется на окружности, то координата $y_0$ отыскивается из
квадратного уравнения (получающегося из уравнения окружности),
коэффициенты которого являются квадратичными иррациональностями.
Следовательно, $y_0$ является квадратичной иррациональностью
(поясните).

Для элементарного шага В утверждение леммы тривиально~---
коэффициенты уравнения проведенной окружности, конечно, являются
квадратичными иррациональностями.

Уравнение прямой, проходящей через точки $A=(x_A,y_A)$ и
$B=(x_B,y_B)$ выглядит так:
$\frac{x-x_A}{y-y_A}=\frac{x-x_B}{y-y_B}$. Переписывая его в виде
$aX+bY=c$, видим, что $a,b,c$ являются квадратичными
иррациональностями, и тем самым для шага Б лемма проверена.

Координаты точек пересечения в элементарных шагах Г, Д, Е
отыскиваются из систем уравнений соответствующих линий.

В случае Г система линейная и ее коэффициенты являются
квадратичными иррациональностями. Решая ее (например,
подстановкой), получим, что ее решение~--- точка $(x,y)$~---
является квадратичной иррациональностью.

Чтобы решить систему Д, сделаем подстановку $y=\alpha x+\beta$
(или $x=\alpha y+\beta$) уравнения прямой в уравнение
окружности~--- получим квадратное уравнение относительно $x$ (или
$y$) с коффициентами --- квадратичными иррациональностями.
Следовательно, $x$ и $y$ являются квадратичными
иррациональностями.

Наконец, вычитая из одного уравнения системы Е другое, получим
линейное уравнение. Далее рассуждаем, как в случае Д. \qed

\smallskip
{\bf Обобщение.} Если в задаче задан не один отрезок, а несколько,
т.е. в задачах типа "$(1,a_1,a_2,\ldots,a_m)\to x$", то можно
провести аналогичное исследование. При этом вместо единицы нужно
начинать с чисел $1,a_1,\ldots,a_m$, т.е. определить квадратичные
иррациональности над множеством $\{1,a_1,\ldots,a_m\}$ (вместо
$\{1\}$). Критерий построимости формулируется и доказывается
совершенно аналогично.



\bigskip
\centerline{\bf Неразрешимость задач на построение и уравнений в
квадратных радикалах.}

\smallskip
\hfill{\it To him a thinking man's job was not to deny one reality
at the expence}

\hfill{\it of the other, but to include and to connect. This was
not an easy job.}

\hfill{\it Ursula K. Le Guin, The Disposessed.}

%\hfill{\it Но плотник проронил слезу} \hfill{\it И отвечал "Едва ли!"}
%\hfill{\it Льюис Кэррол}

\smallskip
Далее мы применим доказанную теорему ОТГП к классическим задачам
на построение. Схема дальнейших исследований такова: выписываем
уравнение $P(x)=0$ на искомый отрезок $x$, а затем выясняем,
является ли корень $x$ квадратичной иррациональностью или нет~---
в зависимости от этого задача на построение "$1\to x$" будет
разрешимой с помощью циркуля и линейки или нет. В этом и состоит
связь между вопросами о разрешимости уравнений в квадратных
радикалах и о разрешимости задач на построение!

 Итак, {\it трансцендентные}
(т.е. не алгебраические) числа "заведомо" {\it не являются}
построимыми или квадратичными иррациональностями. Пока неясно,
любое ли алгебраическое число является квадратичной
иррациональностью?

Приведем представление квадратичных иррациональностей, необходимое
для дальнейшего. Обозначим множество всех квадратичных
иррациональностей через $\Q_{\infty}$.

Начнем с наводящих соображений. Ясно, что $\Q\subset\Q_\infty$.
Если $a_1\in\Q$, то положим $\Q[\sqrt a_1]:=\{\alpha+\beta\sqrt
a_1\ |\ \alpha,\beta\in\Q\}$. Ясно, что $Q_1:=\Q[\sqrt
a_1]\subset\Q_\infty$. Если $a_2=\alpha+\beta\sqrt a_1\in Q_1$, то
положим $\Q_1[\sqrt a_2]:=\{\alpha+\beta\sqrt a_2\ |\
\alpha,\beta\in Q_1\}$. Ясно, что $Q_2:=\Q_1[\sqrt
a_2]\subset\Q_\infty$. Если $\sqrt{a_1}\not\in\Q$, то $Q_2\ne
Q_1$, т.е. $Q_2$ есть {\it существенное} расширение множества
$Q_1$. Так можно продолжить далее, и получить весьма большой набор
примеров квадратичных иррациональностей. Мы докажем, что так можно
получить {\it все} квадратичные иррациональности.

Перейдем к строгим формулировкам.

\smallskip
{\bf Определение.} {\it Полем} (числовым) называется подмножество
множества $\R$ вещественных чисел, замкнутое относительно
сложения, вычитания, умножения и деления.

Примеры полей: $\Q$, $\Q_{\infty}$, множество всех построимых
чисел (поскольку операции (1)-(4) не выводят нас за пределы этого
множества), а также $\Q[\sqrt2]$.

%{\bf Теорема.} {\it Квадратичные иррациональности образуют поле:
%если $x,y\in \Q_{\infty}$, то $x\pm y,xy,\frac1x\in \Q_{\infty}$.}
%Определим в множестве $F[\sqrt a]$ операции сложения и умножения формулами
%$(+)\qquad(\alpha_1+\beta_1\sqrt a)+(\alpha_2+\beta_2\sqrt a)=\ldots(?),$
%$(\cdot)\qquad(\alpha_1+\beta_1\sqrt a)\cdot(\alpha_2+\beta_2\sqrt a)=\dots(?).$

\smallskip
{\bf Определение.} Пусть $F$ --- поле и число $a\in F$ {\it
неквадратичное}, т.е. уравнение $x^2=a$ не имеет решений в $F$
(т.е. либо $a<0$, либо $\sqrt a\not\in F$). {\it Квадратичным
расширением поля $F$ по числу $a$} называется поле $F[\sqrt
a]:=\{\alpha+\beta\sqrt a\ |\ \alpha,\beta\in F\}.$

\smallskip
Поскольку $F=\{\alpha+0\cdot\sqrt a\}\subset F[\sqrt a]$, то
$F[\sqrt a]$ действительно является 'увеличением' поля $F$. Легко
проверить, что $F[\sqrt a]$ действительно является полем,
используя следующий удобный способ {\it деления} в $F[\sqrt
a]$~--- "домножение" на сопряженный элемент:
$$\frac1{\alpha+\beta\sqrt a}=\frac{\alpha-\beta\sqrt a}{\alpha^2-\beta^2a}=
\frac{\alpha}{\alpha^2-\beta^2a}+\frac{-\beta}{\alpha^2-\beta^2a}\sqrt
a= \alpha'+\beta'\sqrt a\quad(\text{почему}\quad
\alpha^2-\beta^2a\ne0?).$$

Например, в $\Q[\sqrt2]$ числа 4, $3+2\sqrt2$, $3-2\sqrt2$
квадратичные, а числа $\sqrt2$, $1+\sqrt2$, 3, 5, $5+2\sqrt2$,
$1-\sqrt2$ неквадратичные. Ясно, что любой элемент поля
$\Q_\infty$ квадратичен. Если $a\in F$~--- {\it квадратичное}
число, т.е. $a=c^2$, то {\it фиктивное} расширение $F[\sqrt
a]=\{\alpha+\beta\sqrt a=\alpha+\beta c\ |\ \alpha,\beta\in F\}$
совпадает с расширяемым полем $F$. Из этого и того, что
квадратичное расширение является полем, вытекает следующее.

\smallskip
{\bf Теорема о представлении квадратичных иррациональностей.} {\it
Число $\alpha$ является квадратичной иррациональностью тогда и
только тогда, когда существует цепочка последовательных
квадратичных расширений, начинающаяся с $\Q$ и захватывающая
$\alpha$, т.е. когда существуют такие положительные $n\in\Z$ и
$a_1,\ldots a_n\in\R$, что
$$\Q=Q_0\subset Q_0[\sqrt{a_1}]=Q_1\subset Q_1[\sqrt{a_2}]=Q_2\subset
\ldots\subset Q_{n-1}[\sqrt{a_n}]=Q_n\supset\alpha,$$ причем
$a_k\in Q_{k-1}$ и $\sqrt{a_k}\not\in Q_{k-1}$ для любого $k\le
n$.}

%Отступление (Г.Х.Харди). "Редукция к абсурду", которую так любил Евклид,
%является едва ли не самым изящным орудием математика. Это намного
%более красивый прием, чем любой шахматный гамбит~--- шахматист, чтобы
%добиться успеха, может пожертвовать пешку или даже фигуру; математик же идет
%на риск проигрыша всей партии.


\smallskip
{\bf Трисекция угла.} Мы рассмотрим задачу о трисекции угла
$\alpha=60^{\circ}$, т.е. построение "$1\to x=\cos20^{\circ}$".
Используя известную формулу $\cos3\phi\cdot4\cos^3\phi-3\cos\phi$,
получим, что число $x$ удовлетворяет уравнению
$$\cos60^{\circ}=4\cos^320^{\circ}-3\cos20^{\circ},\quad\text{т.е.}\quad
1/2=4x^3-3x, \quad\text{или}\quad 8x^3-6x-1=0.$$ Легко проверить,
это уравнение не имеет рациональных корней (кандидатов на корни
всего 8~--- проверьте их). Можно найти $x=\cos20^{\circ}$ по
формулам дель Ферро-Эйлера: $\cos20^{\circ}=\frac12\left(
^3\sqrt{\frac{1+i\sqrt3}2} + ^3\sqrt{\frac{1-i\sqrt3}2}\right),$
однако особого энтузиазма это изящное соотношение не вызывает.

Мы попытаемся воспользоваться косвенной информацией: тем, что $x$
является корнем неприводимого над $\Q$ кубического уравнения.
Оказывается, доказательство непостроимости числа $\cos20^{\circ}$
возможно только одновременно с числами $\cos140^{\circ}$ и
$\cos260^{\circ}$, т.е. с другими корнями уравнения $8x^3-6x-1=0$
(иногда более сильные --- т.е. более {\it 'сложные'} ---
результаты доказывать {\it проще}, см. статью 'Парадокс
исследователя' в 'Кванте'). Это одна из причин того, что
классические задачи древности удалось решить только в Новое время
--- в древности не были разработаны идеи доказательства
непостроимости числа без явной формулы для него и рассмотрения
вместе с каждым корнем многочлена других его корней.

Непостроимость числа $\cos20^\circ$ вытекает из следующей теоремы.
(Можно показать неразрешимость трисекции угла $\alpha$ для всех
$\alpha$, кроме счетного множества исключительных углов~---
например, $\alpha=90^\circ$.)


\smallskip
Несмотря на то, что в {\it формулировке} теоремы о кубических
уравнениях речь идет о {\it вещественных} числах, для ее
доказательства в случае наличия ровно одного вещественного корня
необходимы {\it комплексные} числа. Т. е. нужна более сильная
версию этой теоремы --- в которой квадратичные иррациональности
считаются {\it комплексными} (опять парадокс исследователя!).
Число $x\in\C$ называется {\it комплексной квадратичной
иррациональностью (над $\Q$)}, если $x$ можно получить из 1 при
помощи сложения, вычитания, умножения, деления и извлечения
квадратного корня (в $\C$!). Обозначим через $\Q_\infty^\C$
множество всех комплексных квадратичных иррациональностей.

Для комплексных квадратичных иррациональностей справедлив аналог
теоремы о представлении --- он формулируется точно так же, только
неквадратичные числа $a_k$, по которым строится цепочка
квадратичных расширений, уже могут быть комплексными (в частности,
действительными отрицательными). Итак, если $a_m$~--- первое
отрицательное из $a_k$, то поле $Q_m$ будет уже подполем поля
$\C$, как и все следующие поля $Q_k$. Следующие же $a_k$ могут уже
быть комплексными. Теорема о кубических уравнениях доказывается
аналогично вещественному случаю.

(Плоскость $Oxy$, на которой мы делаем построения, можно считать
комплексной плоскостью $\C$, ее точки можно отождествить с
комплексными числами; тогда можно говорить о построимых
комплексных числах. С помощью геометрической интерпретации
операций в $\C$ нетрудно проверить построимость с помощью циркуля
и линейки комплексных чисел $z_1\pm z_2$, $z_1\cdot z_2$,
$z_1/z_2$, $\sqrt z$ по данным $z_1,z_2,z\in\C$. ОТГП справедлива
и для комплексных построимых чисел и квадратичных
иррациональностей.)

При доказательстве теоремы о кубическом уравнении фактически
появилось следующее понятие. Наименьшая длина $n$ цепочки
последовательных квадратичных расширений, начинающаяся с $\Q$ и
захватывающая $\alpha$, называется {\it рангом} квадратичной
иррациональности $\alpha$ и обозначается $rk\alpha$. Например,

(0) $\alpha\in \Q\Leftrightarrow \rk\alpha=0$.

(1) квадратичные иррациональности $\sqrt3$, $1+\sqrt2$,
$\sqrt{3+2\sqrt2}$ и $1+\sqrt{3-2\sqrt2}$ имеют ранг 1.

(2) квадратичные иррациональности $^4\sqrt2=\sqrt{\sqrt2}$,
$\sqrt{2\sqrt3}$, $\sqrt{1+\sqrt2}$, $\sqrt2+\sqrt3$,
$\sqrt{5+2\sqrt2}$, $3+4\sqrt{1+\sqrt2}$, $\sqrt2+\sqrt{1+\sqrt2}$
имеют ранг 2.

Таким образом, составив уравнение задачи на построение "$1\to x$",
в случае степеней 3 и 4 мы можем установить как неразрешимость,
так и разрешимость этой задачи.



\smallskip
{\bf Небольшой список неразрешимых задач на построение.}

А. Построение треугольника по трем биссектрисам.

Б. Построение треугольника по данным "$a$", "$c$" и $B-C$.

В. Построение отрезка данной длины внутри данного угла,
проходящего через данную точку.

Г. Построение квадрата, пары соседних вершин которого лежат на
двух данных окружностях (эта задача приводит к уравнению степени
4).

\smallskip
Абель и Галуа при доказательстве неразрешимости в радикалах
уравнений степени 5 и выше рассматривали расширения полей, более
общие по сравнению с квадратичными. Для таких расширений они
исследовали т. н. {\it группы автоморфизмов Галуа}~--- группы
отображений расширенного поля $F_1\supset F$ в себя, обладающих
выписанными свойствами (a), а также $\overline z=z\Leftrightarrow
z=\alpha+0\cdot\sqrt a\in F$. С помощью теории групп Галуа и
устанавливается упомянутая неразрешимость!
%Отметим, что группы Галуа~--- это частный случай {\it сохраняющих} групп
%преобразований.
%А именно, автоморфизмы Галуа сохраняют операции сложения и умножения~---
%свойства $(+)$ и $(\cdot)$~--- а также оставляют инвариантным подполе
%$F\subset F_1$ (св-во$(И)$).




\bigskip
%\newpage
\centerline{\bf Построение правильных многоугольников.}
\smallskip
\hfill{\it Нормальные герои всегда идут в обход!}

\hfill{\it Р. Быков, Айболит-66.}

\smallskip
{\bf Проблема.} {\it При каких $n$ правильный $n$-угольник можно
построеить циркулем и линейкой, а при каких~--- нет?}

\smallskip
Для краткости мы будем опускать слово "правильный". Мы уже
научились с помощью элементарной алгебры строить 5-угольник; ниже
мы установим неразрешимость задачи о построении 7-угольника.
Проставим в таблице плюсики под разрешимыми задачами и минусы~---
под неразрешимыми~--- там, где сможем.
$$\minCDarrowwidth{0pt}\CD
n= @=2 @=3 @=4 @=5 @=6 @=7 @=8 @=9 @=10 @=11 @=12 @=13 @=14 @=15
@=16 @=17 @=18
   @=19 @=20 @=21 \\
X= @=+ @=+ @=+ @=+ @=+ @=- @=+ @=? @=+  @=?  @=+  @=?  @=-  @=+
@=+  @=?  @=+
   @=?  @=+  @=- \endCD$$
Мы хотим уловить закономерности этой таблицы~--- выяснить, как ее
заполнять.

Формулируемые ниже утверждения (кроме теоремы Гаусса и леммы
Гаусса) предлагаем читателю доказать самостоятельно.

\smallskip
{\bf Теорема о мультипликативности.} {\it Пусть $m$- и $n$-
угольники построимы, причем $m$ и $n$ взаимно просты. Тогда и
$mn$-угольник построим.}

\smallskip
Из теоремы о мультипликативности вытекает, что проблему
построимости $n$-угольника достаточно решить для $n$ вида $n=p^k$,
где $p$ простое.

Конечно, наша задача сводится к построению $1\to\cos\frac{2\pi}n$.
Можно написать уравнение на $x=\cos\frac{2\pi}n$ (как это
сделать?), но что потом?! Вернемся к геометрии. Пусть требуется
построить $n$-угольник $A_0A_1A_2\ldots A_{n-1}A_0$~--- вписать
его в данную окружность. Вершину $A_0$ можно взять произвольным
образом, и мы будем считать ее положение зафиксированным. Для
построения всего $n$-угольника достаточно построить вершину
$A_1$~--- остальные вершины получаются последовательным
откладыванием дуги $A_0A_1$ от точки $A_1$. Вместо $A_1$ можно
взять и вершину $A_{n-1}$.

При $n=5$ весь 5-угольник можно восстановить и по вершине $A_1$, и
по вершине $A_2$~--- опять-таки, откладывая дугу $A_0A_2$ (при
этом мы совершим двойной {\it обход} окружности),~--- и по вершине
$A_3$~--- точно так же. При $n=6$ весь 6-угольник можно
восстановить только по вершинам $A_1$ или $A_5$ (вершина $A_2$ не
годится!). {\it Вопрос:} как, зная $n$ и $k$, выяснить, можно ли
весь $n$-угольник восстановить по $A_0$ и $A_k$ откладыванием дуги
$A_0A_k$ или нельзя?

Итак, чтобы построить $n$-угольник, зная вершину $A_0$, достаточно
построить такую его вершину $A_k$, чтобы все остальные вершины
получались последовательным откладыванием по окружности дуги
$A_0A_k$. Каждую такую вершину $A_k$ будем называть {\it решением}
задачи о $n$-угольнике. Чтобы построить $n$-угольник, нужно
циркулем и линейкой найти хотя бы одно решение.

Мы не будем отыскивать решения, а пойдем {\it в обход}: посмотрим,
каково {\it число решений} задачи об $n$-угольнике. Найдите это
число при $n=4,7,8,10,12,100$.

\smallskip
{\bf Лемма.} {\it Число решений задачи об $n$-угольнике равно
количеству $\varphi(n)$ натуральных чисел, меньших $n$ и взаимно
простых с $n$ (т.е. функции Эйлера от $n$).}

\smallskip
{\bf Свойства функции Эйлера.} {\it (a) Если $p$ простое, то
$\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$.

(b) Если $m$ и $n$ взаимно простые, то
$\varphi(mn)=\varphi(m)\varphi(n)$.}

\smallskip
Теперь сопоставьте числа последней строчки таблицы со значениями
функции Эйлера. Не можете ли Вы теперь догадаться, как поставить
знаки $\pm$ вместо знаков вопроса? Проверьте Вашу догадку для
$n=24$! Впервые это сделал Гаусс, но он шел {\it совсем в обход}!

\smallskip
{\bf Лемма Гаусса.} {\it $n$-угольник построим тогда и только
тогда, когда $\phi(n)$ является степенью двух: $\phi(n)=2^k$.}

\smallskip
{\it Идея геометрического доказательства необходимости в лемме
Гаусса.} Наводящий вопрос. Сколько решений имеют такие задачи:

(а) вписать в треугольник окружность,

(б) построить общую касательную к двум данным окружностям,

(в) построить окружность, касающуюся трех данных окружностей
(задача Аполлония)?

Мы исходим из окружности $\Gamma$ и точки $A_0$ на ней, и хотим
построить одно из решений $A_k$ задачи о $n$-угольнике. Любая
прямая или окружность пересекает $\Gamma$ ровно в двух точках,
если мы на предыдущем шаге постороения построили $m$ точек, то на
следующем шаге можем построить на $\Gamma$ ровно $2m$ точек (все
точки предыдущего шага из соображений симметрии можно считать
равноправными). Поскольку мы исходим из одной точки~--- $A_0$,~---
то на $s$-ом шаге мы получаем на $\Gamma$ ровно $2^s$ точек.
Поскольку решения $A_k$ одно не хуже другого, на каком-то шаге мы
сразу получим все эти $\varphi(n)$ решений. Следовательно,
$\varphi(n)=2^s$.
\smallskip

Мы не будем доказывать лемму Гаусса, а посмотрим, что из нее
следует.

{\it Если $n=p^k$ и $p$ простое, то $n$-угольник построим тогда и
только тогда, когда либо $p=2$ (т.е. $n=2^k$), либо $n=p=2^l+1$
простое (т.е. $k=1$).}

{\it Если число $l$ имеет хотя бы один нечетный делитель, то число
$2^l+1$ составное.}

{\it Простые числа вида $p=2^l+1$ обязаны иметь вид
$F_m=2^{2^m}+1$.}

{\it Если $n$ простое, то $n$-угольник построим тогда и только
тогда, когда $n=2$ или $n$ есть простое число Ферма
$F_m=2^{2^m}+1$.}

Например, можно построить 17-угольник, но нельзя построить
13-угольник, 11-угольник, 19-угольник, 23-угольник.

Первые числа Ферма суть 3, 5, 17, 257~--- все они, очевидно,
простые. Следующее число Ферма $F_4$ равно 65537 и тоже, как
нетрудно проверить, является простым. При $m=5$ мы впервые получим
составное число Ферма: $F_5=4294967297$ делится на 641 (это
заметил Эйлер; проверьте!). В настоящее время известно еще 36
составных чисел Ферма~--- это $F_m$ при
$m=6,7,8,9,10,11,12,13,14,15,16,18,23,36,38,39,\dots,452,1945$
($F_{1945}$ делится на $5\cdot2^{1947}+1$!). Про остальные числа
Ферма пока неизвестно, простые они или составные (первое из этих
таинственных чисел~--- $F_{17}$).

Итак, из наших рассмотрений (основанных на недоказанной нами лемме
Гаусса) вытекает

\smallskip
{\bf Теорема Гаусса.} {\it Правильный $n$-угольник можно построить
циркулем и линейкой тогда и только тогда, когда $n=2^k\cdot
p_1\cdot p_2\cdot\ldots\cdot p_m,$ где $k\ge0$, а
$p_i=2^{2^n}+1$~--- различные простые числа Ферма.}

\smallskip
Таким образом, в настоящее время известно всего $32=2^5$
построимых правильных многоугольника с нечетным числом сторон;
конечно, непостроимых многоугольников с нечетным числом сторон
бесконечно много~--- скажем, при $n=3^{1+l}$. Пока что неизвестно,
конечно или бесконечно число простых чисел Ферма.
%(Кстати, отметим, что то же относится и к числам $C_n=n^{n^n}+1$~---
%известно только, что среди этих чисел от одного до $10^{40^{17}}$ имеется
%ровно два простых $C_n$: это 2 и 17.)

\end
