В. И. АРНОЛЬД
ft Cite
й ле ft а
и АРИФМЕТИКА
ГЕОМЕТРИЧЕСКИХ
ПРОГРЕССИЙ
МОСКВА
иОСКЗДМГО 1ЛХ*л .fnrf
».»ч чм *чс< »«о :v*-<>ao.i
В. И. АРНОЛЬД
ГРУППЫ ЭЙЛЕРА И АРИФМЕТИКА
ГЕОМЕТРИЧЕСКИХ ПРОГРЕССИЙ
Москва
Издательство МЦНМО
2003
УДК 511
ББК 22.13
А84
Арнольд В. И.
А84 Группы Эйлера и арифметика геометрических прогрессий,—
М.: МЦНМО, 2003.-44 с.
ISBN 5-94057-141-7
ББК 22.13
ISBN 5-94057-141-7
© Арнольд В. И., 2003
© МЦНМО, 2003
§4. Основные определения
Для любого натурального числа п в группе вычетов = по
модулю п лежит мультипликативная подгруппа Г(п)с2л, образованная
вычетами, взаимно простыми с п.
Число <р(п) элементов группы Г(п) Гаусс назвал значением в точке п
функции Эйлера у?.
Определение. Группой Эйлера Г(п) называется мультипликативная
группа взаимно простых с п вычетов по модулю п.
Таким образом, группа Эйлера является коммутативной группой по-
рядка <р(п). В то время как функция Эйлера много исследовалась (Фер;ма,
Эйлером, Гауссом, Лежандром, Якоби и другими), группа Эйлера настоль-
ко же интереснее, чем числа <р(п), доставляемые функцией Эйлера, на-
сколько группы гомологий интереснее чисел Бетти.
Приведение по модулю а определяет естественный гомоморфизм
Г(ад)—*Г(а). Настоящая работа посвящена описанию групп Эйлера и
этих естественных гомоморфизмов.
Замечание. Я не стал выискивать, кто первым открыл тот или иной
сообщаемый ниже факт, но в литературе (ср. [4]—[8]) можно найти, в иных
терминах, описания типа: «этот результат был известен Ферма, был сфор-
мулирован Эйлером и был доказан Гауссом (доказательства которого были
позже усовершенствованы NN)». Я предпочитаю считать последующее
изложением достойной войти в элементарные учебники «теории Эйлера»,
не заботясь об отсутствии в его публикациях как формулировок, так и
доказательств.
§ 2. Отступление о функции Эйлера
Значение функции Эйлера легко вычисляется по разложению аргумен-
та на простые множители, л =р“’ • • а именно
Например, <р(р) = р — 1, у?(9) = 6, у?(15) = 8 (причем, по определению,
¥,(!) = !).
Действительно, все вычеты по модулю простого числа р, кроме нуля,
взаимно просты с ним, так что ip(p) ~р~ 1.
Из ра вычетов по модулю п = ра не взаимно просты с п в точности де-
лящиеся на р вычеты, число которых равно ра~', так что <р(ра) =ра ~ ра~1.
Наконец, если простых делителей pi у числа п имеется А, то взаимно
простой с п остаток по модулю п имеет взаимно простой-с pt остаток rt
по модулю р?' и определяется этими остатками г; однозначно (формальное
доказательство см. в § 6, где это следует из теоремы 1).
При больших значениях аргумента п значение растет, в среднем,
как сп. где с = 6/тг2 близко к 2/3 (ср. [3]). «Рост в среднем», введенный
в [3], означает равенство единице предела при п—>оо отношения сумм п
первых значений,
]irn <р(1) + <р(2) + --- + ¥>(я) _ ।
п->оо С-1+С-2+... + СЛ
Он не исключает довольно больших отличий некоторых значений у>(п) от
сп. означая только, что они редки.
Постоянная с — это вероятность несократимости дроби х/у с целыми х
и у, определяемая как предел при R—>oo отношения числа несократимых
пар (х, у) в круге х2 4- у2 < R2 к числу всех таких пар (растущему с R как
тг/?2).
Эта вероятность вычислена Гауссом и опубликована Дирихле [13]. Для
аналогичной задачи о векторах из V1 вероятность несократимости равна
с = l/C(m), где дзета-функция Эйлера определяется как сумма ряда
£(w) = рту 4-Туп 4-jyn 4“... .
Доказательство формулы для с таково. Вероятность сократимости на 2
равна 1/2ш (так как на 2 должна делиться каждая из т компонент век-
тора). Вероятность сократимости на простое число р есть 1/рт. а вероят-
ность несократимости на р есть I - 1/рт.
Поскольку сократимости на разные простые числа р очевидно неза-
висимы, вероятность полной несократимости равна с —П—Ц- (произ-
1___L
ведение по всем простым). Но из единственности разложения числа п на
простые множители вытекает заложившая начало теории градуированных
алгебр формула Эйлера
(суммирование по всем натуральным значениям п). Формула Эйлера вы-
текает из выражения для суммы геометрической прогрессии
вследствие единственности разложения числа п на простые множители.
4
Наконец, формула £(2) =тг2/6 для значения дзета-функции следует из
теории рядов Фурье. А именно, рассмотрим 2тг-периодическое продолже-
ние f функции |/| - тг/2, заданной на отрезке |/| < тг. Коэффициенты Фурье
легко вычисляются (и убывают как l/n2), и выражение /(0) — —тг/2 через
эти коэффициенты доставляет для £2 1/я2 значение тг2/6.
Таким образом, исследование роста функции Эйлера у? включает всю
математику, от рядов Фурье до теории вероятностей и теории градуиро-
ванных алгебр.
Функция Д встретившаяся при вычислении значения £(2), является
одним из членов знаменитой последовательности периодических функций
Колмогорова, начинающейся с функции /?0 = sign cos / и продолжающейся
по правилу F'+| = />.
Колмогоров изобрел эти функции (аппроксимирующие синусы и ко-
синусы кусочно-полиномиальными функциями растущих степеней, от
ступенчатой Fq и пилообразной F\ до параболически аппроксимирующей
непрерывно дифференцируемой F? и п раз непрерывно дифференцируе-
мой F/n-i) ради решения замечательной экстремальной задачи: найти наи-
большее значение промежуточной А-й производной у 2тг-периодической
функции с заданными ограничениями сверху модулей самой функции и
старшей (ги-й) производной.
Его оценка подсказана теорией размерности или принципом автомо-
дельности Леонардо да Винчи, учитывающим отраженную в обозначениях
Лейбница размерность производной,
dim ZjL = -jim У
(dx)r (dimx)r‘
Оценка Колмогорова имеет вид
где рациональные показатели а и b равны b = k/m, а = I - b по принципу
автомодельности. Постоянная С достигается на подходящей функции се-
рии Колмогорова (причем, если период Т отличен от 2тг, то соображения
подобия диктуют и вид зависимости постоянной С от Т).
Например, первая производная оценивается корнем квадратным из
произведения максимумов модулей функции и второй производной. Этот
частный случай теоремы Колмогорова был ранее установлен (независимо
друг от друга) Адамаром и Литтлвудом.
Общее неравенство Колмогорова явилось, по существу, первым ре-
зультатом современной теории управляемых динамических систем (сде-
лавшейся широко известной много позже, когда Понтрягин опубликовал
5
свой «принцип максимума»). Доказательство Колмогорова, опирающееся
на общий геометрический принцип Гюйгенса теории распространения волн
(вариантом которого является и «принцип максимума»), применимо, с не-
большими изменениями, и в общей теории управляемых систем (подобно
тому, как решение задачи о брахистохроне содержит, в сущности, все
вариационное исчисление). Главной идеей является здесь переход от прин-
ципа огибающих волновых фронтов Гюйгенса к его инфинитезимальному
варианту, являющемуся системой канонических уравнений Гамильтона в
фазовом пространстве.
Практический вывод из этих общих соображений состоит в том, что
в задачах управления с ограничениями для оптимизации нужно все время
давать управлению (в задаче Колмогорова— высшей производной) экстре-
мальное значение. Например, вторая производная в ситуации Адамара и
Литтлвуда должна принимать все время то максимальное, то минимальное
значение, что сразу и приводит (при учете периодичности) к пропорцио-
нальной F% экстремали в этой задаче. Так Колмогоров и пришел к своей
последовательности функций Fn-
Что касается ряда Фурье четной функции f = Fi, нужного для вы-
числения £(2) = тг2/6, то из формулы, представляющей f этим рядом,
ДО — cos(Af), мы находим, что Дл = 0 при четных А, тогда как для
нечетного k коэффициент Фурье находится интегрированием по частям:
^Clk= f(t)CQS(kt)dt = 2^tCQS(kt)dt:=
-5Г	О
--Usin^ow =^(coS(A0)i;=-
* о	J *
Итак, мы вычислили коэффициенты Фурье с нечетными номерами: они
суть
Стало быть, значение /(0) = —- равно сумме ряда Фурье
^(0) \S(2m+l)2
и мы вычислили сумму ряда обратных квадратов нечетных чисел
00
.2
т=0 (2m+I)2 ~ *8"'
6
. Введем обозначение В для искомой суммы ряда обратных квадратов
всех натуральных чисел
1
(2m)2’
Тогда, поскольку каждое натуральное число либо нечетно, либо четно, мы
представим искомую сумму в виде В = А + В/4. Следовательно (поскольку
мы уже знаем нечетную часть, А = тг2/8, из ряда Фурье),
4 тг2
<(2) = В = 1Д = ^.
§ 3.	Таблица групп Эйлера
Прямые вычисления дают для первых значений п группы Э.йлера
Г(л), приведенные в следующей таблице. Обозначение вроде 2°.36.4С
в этой таблице означает коммутативную группу, изоморфную группе
(2г)а х (Z3)6 х (Z4)c (порядок которой равен произведению у? = 2а364с).
Разумеется, группа 2а.3° есть та же группа, что и группа 6а, но группа
2а.4а отличается от группы 8а и группа 22а отличается от группы 4а.
Итак, вот таблица первых групп Эйлера.
п	3	4	5	6	7	8	9	10	11	12	13	14	15
Г(л)	2	2	4	2	6	22	6	4	10	22	12	6	4.2
gi	2	3	2 з	5	3 5	(3,5)	2 5	3 7	2.7 6.8	(5.7)	2.6 7,11	3 5	(2,11)
п	16	17	18	19	20	21	22	23	24
Г(л)	4.2	16	6	18	4.2	6.2	10	22	23
gi	(3,7)	3.5.10,11 6.7,12,14	5 II	2.3.14 10.13.15	(З.Н)	(2,5)	7.13 19,17	5.7.11.15.17 14.10,21.20.19	(5,7,13)
п	25	26	27	28	29
Г(л)	20	12	18	6.2 = 22.3	28
gi	2,3.8,12 13.17,22,23	7.Н 15,19	2.5.20 14,11,23	(3,13), (13,27,9)	2,3,4,5.7,8,9,12,14.16,18,19 ДЗ 15,10,22Д25,11.13,17.27,20,21,26.24
п	30	31	32	33	34	35
Г(л)	4.2	30	8.2	10.2 = 22.5	16	12.2
gi	(7.Н)	З.Н. 12,22 21.17.13,24	(3,15)	(2,10), (10,32,4)	3.5.11.27 23.7.31.29	(2,6)
Числа gi, указанные в третьей строке таблицы (для циклических групп
Г(л) С 2Л) — это циклические образующие указанных циклических групп,
7
так что вычеты чисел g* (Q^k<ip(n)) составляют группу Г(п). При этом
под каждой образующей g указана обратная ей образующая Л (так что
gh = 1 (mod п)). Циклические образующие группы Г(п) называются также
первообразными корнями по модулю п.
Для нециклических групп в строке образующих указан в скобках воз-
можный набор циклических образующих групп-сомножителей (другие та-
кие наборы легко получаются заменой этих образующих их степенями и
произведениями).
Доказательство приведенной в таблице теоремы получается прямы-
ми вычислениями геометрических прогрессий ak (mod п). Для опознания
нециклических групп Эйлера удобно составлять ориентированный граф,
вершинами которого являются элементы группы, а стрелки ведут к ква-
драту элемента (в аддитивной записи — от х к 2х).
Пример. Графы групп порядка 8 таковы:
Полезно также составлять таблицу количества элементов различных
порядков в группе. В предыдущем примере эти таблицы такие:
'^^^Г10рЯД0К группа*^^^	12 4 8
Zg Z4 X Z2 Z|	112 4 13 4 0 17 0 0
8
§ 4.	Группы Эйлера произведений
Анализ таблицы § 3 сразу приводит к следующим выводам (доказа-
тельства обсуждаются ниже, см. §6).
Теорема 1. Если числа а и b взаимно просты, то группа Эй-
лера их произведения — прямое произведение их групп Эйлера’.
Г(а6) = Г(а)хГ(6).
Теорема 2. Если число п~р простое, то группа Эйлера Г(р) =
=	— циклическая группа.
Теорема 3. Если число п = ра —степень нечетного простого чи-
сла, то его группа Эйлера — циклическая группа,
Г(ра) =2^) =
Теорема 4. Если число п = 2а, а >2, — степень двойки, то его
группа Эйлера есть произведение циклических групп порядков 2 и
2Q“2:
r(2a) = Z2xZ2fl-2.
Эти четыре теоремы доставляют все группы Эйлера, так как любое
натуральное число можно разложить на простые множители.
Следствие. Группа Эйлера Г(п) является циклической если и
только если число п равно либо 2, либо 4, либо степени нечетного
простого числа, либо удвоенной степени нечетного простого числа.
Теорема 2—-это просто «малая теорема» Ферма, дополненная Эйлером
(первообразность) и Гауссом.
§ 5.	Гомоморфизм приведения по модулю а, Г(а6) —>Г<а)
Будем обозначать приведение по модулю а вычетов по модулю ab через
тг:	(обозначая иногда тем же символом также ограничение этого
приведения до Г(аЬ) —>Г(а) или его действие на Z).
Замечание. тг(Г(д6)) СГ(а) по следующей причине: если бы вычет
х (mod а) не был взаимно прост с а, то вычет х (mod ab) не был бы
взаимно прост с ab.
Как мы сейчас докажем, тг(Г(а6)) =Г(а) (хотя это и не совсем оче-
видно).
Пусть число х взаимно просто с а, т. е. (х,а) = 1. Отыщем вычет по
модулю ab, проектирующийся в вычет х (mod а). Мы должны исследовать
все прообразы вычета х (mod а) в %аь и среди них найти взаимно простой с
ab элемент группы Г(аЬ). Докажем чуть более общий вариант «китайской
теоремы об остатках».
Теорема TDib. В арифметической прогрессии {x+nD} (л = 0,1,...)
с взаимно простыми членом х и разностью D (так что (x,D)~ 1)
9
есть взаимно простой с В член:
VB Зп: (х + лР,В) = 1.
Доказательство. Теорема Тцд очевидна. Теперь мы будем предпо-
лагать верными теоремы Т^ь с d<D н выведем из них теорему Т^в> Итак,
пусть (х, D) = 1.
Обозначим через 6 наибольший общий делитель чисел В и D, так что
В = /36, D = i6, (/3>у) = \.
Первый случай. 7=1, D — 6.
В этом случае В = /3D > 2 или же /3 = 1, В = D. Если В = D, то (х, В) = 1
по условию, так что теорему То,о доказывает выбор п = 0.
В случае же /3 > 1, когда D < В, мы приходим при D > 1 (когда /3<В)
к импликации
Td,0 => То,в»
поскольку из взаимной простоты числа x + nD с /3 вытекает его взаимная
простота с В = /36 (с 6 это число, как и х, взаимно просто по условию
доказываемой теоремы Td,b (где D = 5)),
Итак, теорема Та,в сведена к теоремам с таким же D, но с меньшими В
(причем, как только B<D> условие 7= 1 больше выполняться не будет).
Второй случай. 7 > 1, 6 < D.
В этом случае мы выведем теорему Та в из теоремы где D — ^5,
В = /36Л0^) = ^
Из условия (х, D) = 1 следует взаимная простота числа х с делителем
6 числа D. По теореме существует целое число m такое, что число
г = х + тб взаимно просто с 0.
Из взаимной простоты /3 и 7 следует возможность представления
1 =p/3 + q^ (с целыми р и q). Теперь мы можем представить г в виде
г = х + 6(тр/3 + mq^) = х + трВ + «О,
где п = mq.
Рассмотрим доказывающее теорему число
R = x + nD = r — трВ.
Это число взаимно просто с /?, так как г взаимно просто с 0 (по теореме
и выбору числа т). Кроме того, R взаимно просто с числом так как
(х,5)= 1 по условию доказываемой теоремы Тд.в, а число D = ^6 делится
на 5.
10
Стало быть, число R взаимно просто и с произведением 08 = В, что и
доказывает теорему (причем в качестве п выбирается число mq).
Теоремы 7Ь,в доказаны теперь при любых D и В.
Из них следует соотношение тг(Г(ай)) = Г(а), так как по теореме Tatb
среди вычетов чисел х + па, п = 0,1,2,... (mod b) имеется взаимно про-
стой с b вычет (если (х,а) = 1, т. е. когда хеГ(а)).
Разумеется, число п можно здесь брать из интервала [0,1,..., b — 1 ],
так как при увеличении п на b вычет числа х + па (mod ab)) не меняется.
Следствие. Число прообразов каждой точки хеГ(а) при ото-
бражении 7г: Г(аЬ) —^(а) одинаково.
Доказательство. Это отображение тг — гомоморфизм группы Г(аЬ)
на группу Г(а), как мы только что доказали. Так что указанное число
прообразов равно порядку ядра этого гомоморфизма, | Кег тг| = ip(ab)/ip(a).
§ 6.	Доказательства теорем о группах Эйлера
Доказательство теоремы 1. Сравним оба гомоморфизма приведе-
ния по модулям а и Ь:
тг: Г(ад)—►Г(а), р: Г(аЬ)^Г(Ь).
Пусть х е Г(а), тг”1 (х) = {Х + па}, 0 п < Ь.
Все Ь вычетов чисел Х + па (mod b) различны, иначе число П\а -п^а
делилось бы на b при |ni — П2|<&, вопреки предполагаемой в теореме 1
взаимной простоте чисел а и Ь.
Значит, в %аь найдется элемент с вычетом х (mod а) и с любым
вычетом (mod Ь). Из этого следует также, что отображение
тг х р: I?(aft) —► Г(а) х Г(Ь)
покрывает все произведение (тот элемент z из Za^, который сравним с
хеГ(а) (mod а) и с уеГ(Ь) (mod ft), обязательно лежит в T(aft), так как
из взаимной простоты числа z с сомножителями а и ft следует его взаимная
простота с произведением aft).
С другой стороны, ядро отображения тг х р тривиально, так как
его элементы сравнимы с 1 и по модулю а, и по модулю ft, а значит, их
разность в Zab делится на произведение aft, т. е. равна нулю (поскольку а
и ft взаимно просты в теореме 1).
Теорема 2 — это малая теорема Ферма, пополненная существовани-
ем первообразных корней по модулю простого числа (доказанным ниже
в § 12). Существование первообразного корня нужно для того, чтобы по-
рядок группы не оказался меньшим, чем р- 1.
11
Доказательство теоремы 3. Представим число ра+\ где р — не-
четное простое число, в виде произведения р-ра, и рассмотрим соответ-
ствующий приведению тг (по модулю р) гомоморфизм групп
7г:Г(ро+,)^Г(р).
Образом является вся группа Г(р), которая является циклической
группой порядка р~ 1 (по теореме 2). Изучим ядро гомоморфизма тг.
Лемма. Ядро гомоморфизма тг является циклической группой по-
рядка ра.
Доказательство. Образующей ядра является, например, элемент
1 +р (рассматриваемый как входящий в группу Г(ра+1) вычет по модулю
р°+1)-
Действительно, вычислим степени этого элемента в р-адической си-
стеме счисления. По формуле бинома Ньютона,
(1 + р)*= 1 + рй (mod р2),
поэтому при Л = 0,1 мы получим (mod р2) все р значений
q (mod р) для числа
(1+/?)*-1=р</.
Из той же формулы бинома следует, что
(1 + р)р = 1 + р2 (mod р3).
Возводя этот элемент в степени k = 0,1,2,..., р — 1, мы получаем точно
так же начальные члены р-адического разложения
(1 + р)кр = l+kp2 (mod р3),
(1+р)₽2 = 1+р3 (mod/?4).
Совершенно так же выводятся формулы
(1 +p)kpS = 1 +kps+l (mod ps+2),
доставляющие кратные высшим степеням р слагаемые,
Л = 0,1,2,...,р—1.
Перемножая формулы, соответствующие а членам р-адического раз-
ложения
k = ko + kip + k2p2 + ... + ka-iPa~l (mod ра).
12
мы получаем удобное представление любого элемента циклической группы,
порожденной образующей 1 +р:
(1 +р)* = (1 +рАо)(1 +p2ki)...(\+paka-\) (mod ра+').
Из этой формулы видно, что все полученные (при 0^k<pa) ра эле-
ментов группы Г(ра+1), входящие в ядро гомоморфизма тг, различны1. Зна-
чит, это ядро (имеющее порядок <p(pa+l)/<p(p) = (р ~ l)pa/(p ~ 1) =Ра) ~
циклическая группа (порядка ра).
Итак, абелева группа Г(ра+1) расслоена над Zp_] со слоем Z^. По-
рядки (р - 1 и ра) этих циклических групп взаимно просты, поэтому рас-
слоение тг является прямым произведением (и циклической группой)
Г(ра+1) ~ х Zpa ~ Z^pa),
что и доказывает теорему 3.
Доказательство теоремы 4. Рассмотрим гомоморфизм приведения
по модулю 4, тг: Г(2а) —>Г(4). Образ состоит из вычетов 1 и 3 (mod 4), и
мы можем записать каждый элемент из группы Г(2а) как вычет числа
х=14-2а4-4н, О^а, и<2а~2.
В частности, имеется специальный элемент второго порядка
до = 2а“1 - 1, а(до) = 1 +2 + 4 + ... + 2а-3 = 2а"3- 1, и(до)=0.
Для этого элемента w2 = 1 (mod 2а), т. к. числа 22а-2 и 2-2а_| делятся
на 2а при а^2 (что а ^2, мы предполагали в теореме 4). Мы получаем
подгруппу {1, до}.
Любой элемент х из Г(2а) можно однозначно записать либо в виде
х = 1 +4н (когда 7гх= 1), либо в виде х = до(1 4-4г) (когда тгх = 3, как и
7Г(ДО)).
Это следует из соотношения тг(дох) = тг(до)тг(х) = 9 = 1 (mod 4): иско-
мый множитель 1 +4г есть просто дох.
Итак, мы представили группу Г(2а) в виде прямого произведения непе-
ресекающихся подгрупп Z2 = {1, до} и {1 4- 4z}, где 0 г < 2а“2. Теорема 4
вытекает из следующего факта.
Лемма. Группа {14-4z} (0 г < 2а~2) вычетов по модулю 2а —
циклическая: {1 4-4z} «Z2e-2.
’Произведение (1 + р)\ где 0<К<ра, не может быть равным единице, так как первая
из отличных от нуля компонент Kt разложения К = Kjp1 доставляет отличный от 0 остаток
mod отличия от 1 произведения.
13
Доказательство леммы. Докажем (подобно приведенному выше до-
казательству теоремы 3), что циклической образующей является элемент
1+4 = 5, который мы запишем в виде
go = 1+4До+ 8Dq, До=1» Dq = 0.
Пусть теперь в Г(2а) дан элемент Q= 1 + 22+,Д + 23+'D.
Вычисление квадрата по формуле бинома дает ответ в виде биноми-
альной формулы
Q2= 1 +22+(/+1)Л' + 23+(/+i)D',
где Д' = А (число Df целое потому, что для не выписанных явно трех членов
бинома степеней двоек больше: 2(2 + /) ^3 + (/ + 1), 2(3 + /) >3 + (/+ 1),
1 + (2 + /) + (3 + /) > 3 + (/ + 1)).
Применяя эту фильтрованую биномиальную формулу к случаю (? = <7о
(где / = О, А = До» D = Do), мы получаем для q\ = Q2 = q§ выражение
ql = \^22+xAi-i23+}Di (гдеД^До).
Применяя нашу биномиальную форму к Q = q\, мы находим для
Q2 = 7о = <7? выражение
<?2 = 1 + 22+2Д2 + 23+2D2, Д2 = Дь
Продолжая возведения в квадрат, находим последовательно
=	=	= 1 + 22+eAg + 23+eDg (где Дг = Дг_,)
для g = 0,1,2,...,а-3. При g = a-2 мы получаем <?а_2 = q%~2 = 1 +
+ 2аДа_2 + 2а+|Ля_2 = 1 (mod (2*)), т. е. число 520 2 = I (mod 2е) доста-
вляет единицу группы Г(2а).
Напротив того, все предыдущие степени числа 5 отличны от единицы
по модулю 2а. Действительно, обозначим двоичное разложение числа N,
меньшего, чем 2fl”2, через
М = Л/0 + М1 •2 + A/2-22 + ... + Wa_3-2a"‘3,
где все Nj — нули или единицы.
Тогда для мы получаем выражение
nH-nN*nN'nN* Na-з
— 40 Ч\ 42 ••• Va-3 ’
Обозначим через i первый ненулевой из коэффициентов No,N\,...,Na^
двоичного разложения числа N. Из доказанных выше формул для qg сле-
дует, что
^=1+22+/ (пк^г3*1),
так что 1 в Г(2а) (поскольку / а - 3).
14
Значит, все 2а“2 элементов группы {1 +4z} (mod 2а), которые мы по-
строили в виде 5N (mod 2а), различны, так что эта подгруппа {1 + 4z},
состоящая из всего 2а~2 элементов, исчерпана элементами вида 5N и явля-
ется циклической.
Лемма доказана, и это заканчивает доказательство теоремы 4.
§ 7. Динамическая система Ферма—Эйлера
Зафиксируем взаимно простое с п число а и рассмотрим умножение на
а как преобразование А множества Г(п) взаимно простых с п вычетов по
модулю п в себя: оно переводит вычет числа х в вычет числа ах (которое,
как и х, взаимно просто с п). Мы определили перестановку А : Г(и) —> Г(я),
х^ ах.
Преобразование А множества Г(п) в себя, как и любое взаимноод-
нозначное преобразование, разбивается на циклы этой перестановки ip(n)
элементов.
Теорема (Эйлера—Ферма). Все циклы перестановки Ферма—Эй-
лера А : Г(п) —>Г(п) имеют одинаковый период Т(п,а).
Доказательство. Любой элемент у группы Г(п) получается из лю-
бого другого ее элемента х умножением справа на некоторый элемент z.
Поэтому
АТу — AT(xz) = (ATx)z = xz — у,
т. е. период Т элемента х является периодом и для у.
Следствие. Множество Г(п) взаимно простых с п вычетов по
модулю п разбивается на N(n,a) =у>(п)/Т(п,а) непересекающихся
орбит преобразования Ферма—Эйлера, так что число орбит N,
как и период Т, является делителем значения функции Эйлера,
<р(п) — NT; и выполняется сравнение Ферма—Эйлера
(mod п).
Пример. Если число п=р простое, то имеет место сравнение
ар~[ = 1 (mod р).
Это —исходная «малая теорема» Ферма, которую мы, таким образом,
доказали.
Эйлер перенес эту теорему на составные числа п вместо р, заметив,
что показатель р — 1 = <р(р) нужно для этого заменить на у?(п), откуда и
произошла функция Эйлера <р.
Если преобразование Ферма—Эйлера имеет лишь одну орбиту (N = 1),
то период есть Т = <р(п), так что сравнение Ферма—Эйлера сводится к его
15
простейшей форме
а*{п) = 1 (mod п),
в которой оно верно и когда орбит больше.
Вопрос о поведении периода и числа орбит в зависимости от числа
п весьма непрост. Ниже рассказано об (экспериментальных, в основном)
данных, полученных путем вычисления значений функций N(n) и Т(п) для
простейшего случая а = 2 (в предположении нечетности числа п, т. е. вза-
имной его простоты с основанием а).
Значения числа орбит /V(n) и периода Т(п) операции А умножения на
а = 2 для первых пяти десятков нечетных модулей п указаны в следующей
таблице.
п	3	5	7	9	И	13	15	17	19	21	23	25	27	29	31	33	35	37	39
N	1	1	2	1	1	1	2	2	1	2	2	1	1	1	6	2	2	1	2
Т	2	4	3	6	10	12	4	8	18	6	11	20	18	28	5	10	12	36	12
п	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77
N	2	3	2	2	2	4	1	2	2	1	1	6	4	1	2	2	8	2	2
Т	20	14	12	23	21	8	52	20	18	58	60	6	12	66	22	35	9	20	30
п	79	81	83	85	87	89	91	93	95	97	99
N	2	1	1	8	2	8	6	6	2	2	2
Т	39	54	82	8	28	11	12	10	36	48	30
Простые числа п выделены здесь полужирным шрифтом. Для каждого
из них NT = п - 1, в других случаях произведение NT = <р(п) меньше.
Теорема Эйлера—Ферма означает, что диаграмма Юнга, описывающая
разбиение множества Г(п) на орбиты преобразования Ферма—Эйлера Л,
всегда представляет собой прямоугольник площади <р(п) с основанием
длины Т(п) и N(n) строками такой длины Т(п).
Каждая строка представляет собой орбиту действия преобразования
Л, и мы выписываем ее элементы в порядке (х, Лх, Л2х, ...). Для п= 15
эта диаграмма Юнга такова:
7	14	13	И
1	2	4	8
(11-2 = 7)
(8-2=1)
16
§ 8. Статистика геометрических прогрессий
Рост функции Т(п) с ростом модуля п представляется довольно нере-
гулярным, так как среди диаграмм Юнга встречаются и высокие (с отно-
сительно большим отношением N/Т, как для я = 511, где W = 48, Т = 9) и
низкие (с малым отношением N/Т, как 1/82 для я = 83).
Суммы десятков значений 1 п 19, 21 п 39, 41 п 59, 61 О
^79, 81 я ^99 и десятков соответствующих значений периодов Т обна-
руживают более регулярную зависимость:
	100	300	500	700	900
L^	68	158	246	299	329
Эти данные подсказывают линейный рост Т с п (грубо говоря, в сред-
3
нем порядка Т = Сп, где С« у при п~70 медленно убывает с ростом п).
Никаких теорем на этот счет я не знаю. Вот, однако, некоторые со-
ображения нематематического характера.
Возрастание погрешностей в значении х при умножении х на большое
при больших временах t число az, осуществляемое за время t динамической
системой Ферма—Эйлера А : Г(я) —► Г(л), наводит на мысль, что орбита
{а‘х,	7} должна быть разбросана внутри Г(л) (и даже внутри
Z„ = Z/nZ) хаотическим образом.
Длина или период Т этой орбиты определяется тем условием, что
все Т «случайных точек» а*х должны занимать разные положения среди
т — <р(п) точек множества Г(я) (или среди всех т = п точек множе-
ства Z„). Поэтому возникает идея сравнить Т(п) с длиной типичной
случайной последовательности независимых выборов одной из пг точек
какого-либо множества, в которой все элементы этой случайной последо-
вательности оказались различными.
Эта задача теории вероятностей обычно называется задачей о днях
рождения (Г —число студентов в группе, гп = 365 —число вариантов дня
рождения). Спрашивается, какова вероятность того, что дни рождения всех
Т студентов в группе различны?
Ясно, что эта вероятность тем меньше, чем больше число студентов
Г, и совсем мала, начиная с некоторого их числа (и даже равна нулю
при Т>т). Напротив, если число студентов Т мало, то мала вероятность
наличия совпадений.
Критический размер группы Г*, где вероятность совпадений мала при
Г<Л и велика при Т> Г*, растет с m как квадратный корень из т.
В этом проще всего убедиться, разделив число наборов непересекаю-
щихся последовательных выборов Т элементов из m (равное произведению
17
Т множителей m(m - 1)... (tn — Т+ 1)) на число всевозможных наборов
(равное тт):
Предполагая число Т небольшим по сравнению с пг (например, устремляя
m к бесконечности при фиксированном Г), мы получаем (не останавлива-
ть i
ясь на деталях оцеики ошибки) in р « - j/m.
Таким образом, приближенная формула для вероятности несовпадения
есть
р	.
Это число мало, когда Т:»л/2гп, и близко к 1, когда	так что
длина отрезка m-значной случайной последовательности без совпадений
растет с числом значений как квадратный корень из этого числа.
Замечание. Я думаю, что переход от малых значений р к большим при
переходе Т через критическое значение порядка у/rn описывается универ-
сальной функцией erf (интегралом от гауссовой плотности) при соответ-
ствующих (зависящих от т) единицах измерения отклонения значения Т
от критического. Но, к сожалению, я не вндел в литературе доказательства
соответствующей теоремы, несмотря на ее явный интерес для многих при-
ложений: этот вопрос, видимо, слишком прост, чтобы его рассматривать
вероятностникам.
Сравнивая указанный факт теории вероятностей с нашей таблицей
чисел r(n), мы приходим к выводу, что наблюденные периоды Т(п) гео-
метрических прогрессий 2* растут с числом выборов п быстрее, чем при
полной независимости Т значений (будем ли мы считать их принадлежа-
щими множеству Zn из m-п элементов или же его подмножеству Г(п) из
m = tp(n) элементов, поскольку т растет «в среднем» как сп).
А именно, можно сформулировать это наблюдение как указание на
присутствие какого-то (не изученного еще) отталкивания членами гео-
метрической прогрессии {2* (mod л)} друг от друга. Из-за этого растал-
кивания орбита далеко не случайна и совпадений (или даже близких при-
ближений) точек 2Z (mod п) друг к другу оказывается меньше, чем если
бы последовательные точки (t = 1,2,..., Т) выбирались независимо друг
от друга в m-элементиом множестве (Zrt или Г(л)).
§ 9. Измерение степени случайности подмножества
Для того, чтобы исследовать, насколько случайно расположены точки
орбиты {а*} преобразования Ферма—Эйлера среди всех вычетов, входя-
щих в Zn (или среди т = ip(n) взаимно простых с п вычетов, составляющих
18
группу Эйлера Г(п)), я решил измерять «расталкивание» элементов Т-
элементного множества точек отрезка друг другом при помощи следующей
величины.
Обозначим через {хь...,Х7-} последовательность расстояний между
соседними точками.
Имея в виду приложения к вычетам, я склеил концы отрезка в окруж-
ность, так что сумма положительных чисел х, равна длине L этого отрезка
или окружности.
Для измерения присутствия или отсутствия близких сближений точек
множества я использовал «параметр стохастичности» (randomness)
/? = х? + ... + х£.
Чтобы сделать параметр безразмерным (не зависящим от единиц изме-
рения, т. е. от длины L), я нормировал его, подобно преобразовав отрезок, к
случаю L= 1: нормализованный параметр стохастичности Т точек
есть
r = R/L2.
Эту нормализацию нужно делать, применяя теорию к вычетам из
(где L = п) или к элементам группы Эйлера Г(п) (где L — т и «расстояния»
Xi — это число свободных от элементов группы Г(п) дуг между двумя
элементами этой группы, расстояние между которыми измеряет целое чи-
сло Xi).
Всевозможные конфигурации Т точек окружности длины 1 описыва-
ются (Т — 1)-мерным симплексом
{х=(Х1....Хт), 0 0,^1. ^2х(=1}
(с точностью до поворота окружности).
Параметр стохастичности г является моментом инерции точки х от-
носительно начала координат (квадратом расстояния от х до 0). Поэто-
му его наименьшее значение соответствует центру симплекса: xt = \/T,
''min = Т(\/Т)2 = 1/Г, а наибольшее значение —вершине (xi = 1, остальные
нули): Гтах = 1.
Для сравнения множеств с разным числами элементов Т естественно
ввести бинормализованный параметр стохастичности
s = r/rmin = T^2(Xi/L)2.
Интервал изменения этого параметра при различных выборах подмно-
жеств окружности из Т элементов есть
($min = 1) С $ (Smax = Т)*
19
Минимальное значение, s = 1, достигается на правильном, казармен-
ном расположении (арифметической прогрессии) вершин правильного Т-
угольника %, = \/Т (считая £= 1). В этом случае можно говорить о «силь-
ном расталкивании», не допускающем сближения точек.
Максимальное значение, s = Г, достигается на скученном кластере из
Т слившихся точек, для которого все расстояния х, равны нулю, кроме
одного, равного единице.
В этом случае можно говорить о «сильном притяжении», собравшем
все точки в одно место.
Обсудим теперь истинно случайные расположения Т независимо рас-
положенных на окружности точек. Оказывается, бинормализованный па-
раметр стохастичности таких расположений имеет вполне определенное
значение близкое (при большом числе точек Т) к значению $5=2. Сей-
час мы вычислим это «указывающее на хаотичность множества» значение
$i. Его можно назвать «свободолюбивым значением», указывающим на
отсутствие как отталкивания, так и притяжения точки исследуемого мно-
жества ее соседями. Меньшие значения параметра, вплоть до значения
$min = L соответствующего казарменному регулярному строю равноотсто-
ящих точек, указывают на расталкивание.
Большие, чем свободолюбивое значение s«2, значения бинормализо-
ванного параметра стохастичности указывают на взаимное притяжение то-
чек множества, крайним проявлением которого является соответствующее
полному скучиванию максимальное (при фиксированном числе элементов
множества) значение Г.
§ 10. Среднее значение параметра стохастичности
Рассмотрим случайное распределение точки х в симплексе размерно-
сти Т - 1
т
{О^х.^1, ^2х( = 1},
/=1
с постоянной относительно лебеговой меры плотностью (что соответствует
и расстояниям между Т точками, независимо случайно набросанными на
окружность длины 1).
Теорема. Среднее значение параметра стохастичности s =
= Г xf равно «свободолюбивому значению»
б=!
27
51 ~ 7+Г
Доказательство. Вычислим среднее значение для каждого слагае-
мого х? и сложим эти средние (пользуясь их независимостью).
20
Объем слоя нашего симплекса между Xi = u и x/^u + е равен в
первом приближении по е произведению Се(1-и)т~2 (так как этот
(Г- 1)-мерный слой толщины в опирается на (Г —2)-мерный симплекс
{0^х7^ 1 - и, 52х7 = 1 - и, где ///} объема С(1 -и)г“2).
Стало быть интеграл от xf по всему (Г- 1)-мерному симплексу есть
/ = ^xfdxr”1 = § Cu2(l-u)T~2du — ^CvT~2(\-и)2 du.
u«0	О
Последний интеграл вычисляется уже легко (переход к автомодельной
переменной v обязателен) и равен / — С “ 7 + 7+т)’ В Т° вРемя
как объем всего нашего Т — 1-мерного симплекса равен аналогичному ин-
тегралу без множителя и2, т. е. без (I - и)2,
Итак, среднее значение суммы Т слагаемых Гх2 есть s\ = T4/М =
_r2fl 2(7’—1)	Г-1\	Г3 * * * *(Г+1)-2Г2(Г2-1) + Г3(Г-1) 2Т
\ Т + Г+1/	Г(Г+1)	Г+1’ ЧТ°
и доказывает теорему.
Сравнивая наблюденные для геометрических прогрессий значения па-
раметра стохастнчности s со свободолюбивым значением я обнару-
жил, в большинстве прогрессий {2Z mod п}, меньшие свободолюбивого
значения, l,4^s^$i, близкие обычно к 1,6, что указывает на заметное
расталкивание вычетов членов геометрических прогрессий.
Но никаких теорем об асимптотике величины s(n) при больших л я не
доказал.
Замечание. Было бы интересно рассмотреть не только среднее значе-
ние si, но и другие характеристики истинно случайных множеств — напри-
мер, функцию распределения величины х/, или ее моменты, или распре-
деление вероятностей различных разбиений суммы L на Г целочисленных
слагаемых х, (в случае целочисленных значений переменных х,)2.
2Упомяну лишь, что в [1] доказано, что вероятности ръ встретить дуги длины k среди
Т дуг, на которые делят конечную окружность Т разных случайно выбранных точек,
пропорциональны биномиальным коэффициентам, стоящим на параллельной стороне прямой
на расстоянии Г —2 от стороны треугольника Паскаля:
р* = С*“2. JCT~\
Например, для Г = 4 случайных точек вероятности длин дуг соотносятся как
1:3:6:10:15...
(наименьшую вероятность имеет наибольшая длина дуги, равная т — Т — 1).
21
Все эти интегралы явно вычислимы и задают кусочно-полиномиальные
распределения (например, для величины $, зависящей от пробегающего
симплекс случайного параметра х).
Вероятно, эти распределения (и особенно их универсальные асим-
птотики вблизи свободолюбивого среднего значения при больших Г)
заслуживают специального изучения в теории вероятностей или в стоха-
стической геометрии.
Что же касается статистики геометрических прогрессий вычетов, то
здесь распределения окажутся другими, и их изучение, даже эксперимен-
тальное, может привести к новым открытиям в этой эргодической теории
чисел.
Я попытался исследовать, кроме геометрических прогрессий, также
арифметические прогрессии вычетов {dt (mod л), t = 1,2,3,..., Т} и мно-
жества взаимно простых с п вычетов, Г(и) cZn.
В обоих случаях наблюдаются заключенные между I и 2 значения
параметра стохастичности $, т. е. расталкивание соседей друг другом. Ве-
роятно, для случая арифметических прогрессий эти результаты можно до-
казать при помощи цепных дробей (и надлежащих обобщений теоремы
Кузьмина).
§ 11. Дополнительные замечания о динамике Ферма—Эйлера
Экспериментальное исследование функций Т и N переменной п при-
вело меня к сотням наблюдений, некоторые из которых стали сегодня
теоремами. Вот простейший пример.
Определение. Нечетное число п принадлежит классу N, если удовле-
творяется сравнение Ферма—Эйлера
2^ = 1 (mod п).
Теорема. Класс N представляет собой идеал в коммутативной
мультипликативной группе нечетных чисел: если п принадлежит
классу N, то и произведение п на любое нечетное натуральное число
тоже ему принадлежит.
Пример. Классу (3+) принадлежат числа 31, 43, 63, 91, 93, 117, 129,
133, 155, 157, 171, 189, 215, 217, 223, 229, 247, 259, 273, 279, 283, 301
(полужирным выделены простые числа).
Образующими полугруппы являются те из них, которые не кратны
другим: это все простые элементы и еще 63, 91, 117, 133, 171, 247, 259.
Странное наблюдение, для которого не видно пока никаких оснований,
состоит в том, что вычеты всех этих образующих по модулю 9 являются
квадратичными (принадлежат четверке {0,1,4,7}).
22
Аналогичный результат (так же как и этот, являющийся только на-
блюдением в пределах имеющихся таблиц, простирающихся, впрочем, до-
вольно далеко) верен для класса (5+) и вычетов по модулю 25.
Для некоторых других N квадратичными оказываются вычеты по мо-
дулю N2 не всех, а простых образующих идеала N,
Класс (Л/—) определяется сравнением
2*>(л)/Л/ = —1 (mod и)
для его элементов п.
Если число <р(п) делится на 4 и нечетное число п принадлежит классу
(2+), то п лежит либо в (4+), либо в (4—): по модулю п
4-1) = (2^(л)/2 — 1) = 0
по теореме Эйлера.
Но указать явно, какие из элементов класса (2+) лежат в (4+), а какие
в (4—) не удается (как и не удается пока различить подклассы (8+) и (8—)
внутри класса (4+)).
Условия принадлежности к разного рода классам иногда бывают до-
вольно явными. Например, в статье [1] доказана
Теорема. Если нечетное число п имеет k или больше разных
простых делителей, то оно принадлежит классу (2*+).
Значительную информацию о классе числа-произведения дает иногда
описание классов сомножителей. Например, в статьях [1] и [2] имеется
(восходящая, вероятно, к Эйлеру, если не к Ферма)
Теорема. Нечетное число ра лежит в классе (2+), если простое
число р дает при делении на 8 остаток 1 или — 1, и в классе (2—),
если оно дает остаток 3 или —3.
Так что распознать принадлежность любого нечетного числа классам
(2+) или (2—) легко. Но уже для классов (4+) и (4—) (и даже для простых
чисел этих классов) положение сложнее и критерий неясен.
Например, числа
17, 41, 57, 97,
принадлежат классу (4—), а числа
65, 73, 89, 113
*— классу (4+), но причины этого неясны.
Таблицы подсказывают десятки разнообразных гипотез, часть из ко-
торых уже стала теоремами.
Например, в [1] доказано, что если простое число~р = 8с+ 1 (вроде
р = 73) принадлежит классу (4+), то все произведения parf>, где q —
другое нечетное и простое число, принадлежат классу (8+)-
23
§ 12. Первообразные корни простого модуля
Здесь мы докажем теорему 2 из §4, из которой выше доказана только
половина: то, что ар~[ = 1 (mod р) для простого модуля р.
Остается доказать цикличность группы Г(п), т.е. существование
такой геометрической прогрессии {az} mod р, все р- 1 членов которой
(с 1 t ^р - 1) различны (так что а1 1 (mod р) при 0< t <р- 1).
Такое основание а€Г(р) называется первообразным корнем. Ока-
зывается, число таких корней равно <р(р~ 1).
Доказательство существования первообразного корня основано на за-
мечательном тождестве Эйлера: сумма значений функции Эйлера во
всех делителях d числа п равна самому этому числу п\
<р( 1) 4-... 4- y>(d) 4-... 4- ¥>(п) = п.
Например, делителями числа 6 являются d = 1,2,3,6, и тождество сво-
дится к соотношению
¥>( 1) 4- ¥>(2) 4-у(3) 4-^(6) =14-14-24-2 = 6.
Доказательство тождества Эйлера получается из разбиения всех вы-
четов по модулю п в зависимости от их наибольших общих делителей.
Наибольший общий делитель d с числом п имеет вычет вида kd, причем
число k должно быть взаимно простым с n/d (иначе общий делитель d
вычетов с числом п не был бы наибольшим).
Итак, число вычетов, наибольший общий делитель каждого из которых
с п есть d, равно y>(n/d).
Все п вычетов mod п разбиваются по делителям d числа п на классы
(вычетов, наибольший общий делитель членов каждого из которых с п есть
d) из v>(n/d) элементов.
Поэтому общее число вычетов представлено в виде суммы по всем
делителям d числа п,
n = ^4><n/d}.
d
К так как число k = n/d также является делителем числа п, и допол-
нительные делители d и k взаимно определяют друг друга, то последняя
сумма может быть переписана и в виде
k
где суммирование опять распространено на все делители числа п. Тожде-
ство Эйлера доказано.
Пример. Для п = 6 наибольшее общие делители d= (1,2,3,6) с
числом п = 6 имеют вычеты (1,5), (2,4), (3), (6) соответственно. Числа
24
вычетов, имеющих такие наибольшие общие делители с п = 6, равны
k = у?(б/1) = 2, у?(б/2) = 2, у?(6/3) = 1, 99(6/6) = 1, соответственно, так что
общее число вычетов (п — 6) представлено указанным их разбиением на
классы с разными наибольшими общими делителями d с числом п в виде
6 = р(б/1) + р(б/2) + у»(б/3) + ¥>(6/6) = р(6) + р(3) + р(2) + 1).
Рассмотрим теперь геометрические прогрессии вида {a' mod р}, где
р — нечетное простое число и где а взаимно просто с р. По теореме Фер-
ма ар~[ = I (mod р), но для некоторых оснований а минимальный период
прогрессии может оказаться равным не р — 1, а одному из делителей Т
числа р- 1:
аг=1 (mod р).
В этой прогрессии имеется тогда ровно <р(Т) членов b = af (где
О < / <Т взаимно просто с Т), имеющих mom же минимальный период
Т прогрессии {b*} (mod р).
Действительно, bT = atT = (атУ = 1(р), а меньшим, чем Г, период быть
не может, так как br = atr — au, где и —меньший Т остаток отделения tr
на Г; так что, если бы Ьг было единицей по модулю р, то период Т не был
бы минимальным и для основания а.
Других решений сравнения ат= 1(р), кроме Т членов прогрессии {а*},
по модулю р нет, так как сравнение степени Т по простому модулю р
со старшим коэффициентом I не может иметь больше Т решений (по
теореме Виета). Значит, <р(Т) — это полное число всех решений указанного
сравнения.
Таким образом, распределение всех р—1 чисел 0<а<р (которые
все взаимно просты с р) по их минимальным периодам Т прогрессий
{a* (mod р)} (являющимися притом делителями числа р—1) имеет вид
р-1 =^2<р(7),	(*)
где суммирование идет по тем делителям Т числа р—1, для которых одна
из прогрессий {az} имеет наименьший период Т.
По тождеству Эйлера число и = р— 1 равно сумме значений ip(d) по
всем делителям d числа р—1. Значит, и в сумме (*) ни один делитель d
не может отсутствовать. Доказана
Теорема. Число остатков 0<а<р с наименьшим периодом d
у прогрессии {д' (mod р)} равно <p(d) для любого делителя d числа
р- L
В частности, делителем является и число d = р — 1.
Следствие. Число первообразных корней по модулю р равно
ip(p- 1) (и, в частности, такие корни всегда есть).
25
Пример. Для модуля р = 7 число первообразных корней есть <р{&) = 2.
Прогрессии {a' (mod 7)} (/= 1,2,...) (где а= 1,2,...,6) и их наименьшие
периоды Т(а) суть:
{1,1,...}, 7=1;
{2,4,(8 = 1);2,...}, 7 = 3;
{3,(9 = 2),6,(18 = 4),(12 = 5),(15 = 1);3,...}, 7=6;
{4, (16 = 2), (8= 1);4,...}, 7=3;
{5,(25 = 4),(20 = 6),(30 = 2),(10 = 3),(15= 1);5,...}, 7=6;
{6,(36= 1);6,...}, 7=2;
Первообразные корни —это а = 3 и а = 5. Число корней периода 7 = 3
также равно р(3) =2.
§ 13. Узор координат квадратичных вычетов
Используем доказанные выше факты о геометрических прогрессиях
для описания геометрии квадратичных вычетов по нечетным простым мо-
дулям р.
Обозначим через А какой-нибудь первообразный вычет mod р, 0<
< А < р. Геометрическая прогрессия {Д'}, 0 < t < р - 1, содержит (по разу)
все ненулевые вычеты по модулю р. Квадратичные ненулевые вычеты со-
ответствуют четным значениям t.
Обозначим через 7 наименьший период геометрической прогрессии
{2'}, 2r= 1 (mod р), и обозначим через N число строк диаграммы Юн-
га перестановки «умножение вычета на 2» множества всех tp(p)=p — 1
ненулевых вычетов по модулю р (так что TN = p- 1).
Основное предложение. Все TN вычетов (mod р) чисел
Ar2s (0Cs<7, 0^r<N)
различны.
Доказательство. В случае совпадения двух вычетов мы получили
,бы равенство единице одного из таких же вычетов (а именно, равного
отношению двух совпадающих),
Д“2"=1(р) (0О<7, 0cv<M-
Если и и v не оба нули, то, возведя это сравнение в степень 7, мы получили
бы сравнение
ДГ“2П’ = ДГ“ = 1 (mod р), где 0< 7u< 7W = p(p),
т. е. вычет А не был бы первообразным по модулю р.
26
Итак, основное предложение доказано. Мы будем использовать выче-
ты s (mod Т) и г (mod N) в качестве координат точек диаграммы Юнга
или вычетов A1 = Ar2s (mod р).
Опишем места, занимаемые в этих координатах квадратичны-
ми вычетами. Они образуют замечательные узоры на плоскости (г, s).
По самому определению, все вычеты с четными г и s квадратичны. Но
их число составляет всего около четверти общего числа р — 1 ненулевых
вычетов, в то время как число квадратичных вычетов равно их половине,
т.е. (р- 1)/23 *.
Значит, существуют и другие квадратичные вычеты, происходящие из
квадратов вычетов Д'2Л Они равны Л2'22/= ДГ2А' (mod р), где г^2Л
Места (г, $) этих квадратов расположены на диаграмме Юнга по-
разному, в зависимости от остатка при делении простого модуля р на
восемь.
Теорема. Если р = 8г±1, то квадратичными являются все вы-
четы четных строк, A2r2s и только они. При этом число строк N
всегда четно.
Если р — 8с±3, то квадратичные вычеты составляют половину
каждой строки, а именно, квадратичны вычеты A2r22s, д2'п-122'"~1
и только они.
При этом число строк N всегда нечетно, а длины Т строк четны
(делятся на 4 при р —8с —8 и не делятся на 4 при р = 8с4-3).
Вот несколько примеров значений чисел строк N и их длин Т:
	с	р	Т	N		с	Р	Т	N
	2	17	8	2		0	3	2	1
р = 8г 4- I:	9	73	9	8	; р — 8с 4- 3:	1	11	10	1
	14	113	28	4		5	43	14	3
	29	233	29	8		31	251	50	5
	С	р	Т	/V		С	р	Т	N
	0	5	4	1		0	7	3	2
р = 8г 4-5:	1	13	12	1	; р = 8г4-7:	3	31	5	6
	4	37	36	1		15	127	7	18
	13	109	36	3		53	431	43	10
Интересный вопрос о росте чисел Т и N с ростом числа р изучен лишь
эмпирически, и эксперимент подсказывает чаще гораздо меньшие, чем Г,
3Операция возведения вычета в квадрат складывает множество ненулевых вычетов попо-
лам потому, что квадрат 1 имеют только вычеты 1 н — 1, поэтому каждый ненулевой квадрат
является квадратом в точности двух вычетов, ±х.
27
значения N (которые в среднем, быть может, даже остаются ограничен-
ными).
Квадратичные вычеты (mod р) набраны полужирным шрифтом в сле-
дующих четырех диаграммах Юнга, строки каждой из которых — вычеты
чисел Ar2s с фиксированным г (координата s — 0,1,..., Т - 1 растет здесь
слева направо, а координата r = 0,	— 1 — сверху вниз, как это и
обычно для матриц).
Мы рассмотрим четыре примера (с остатками 1, 3, 5 и 7 числа р по
модулю 8).
р = \7:N = 2, Т=8,
1	2	4	8	16	15	13	9	(18=1)
3	б	12	7	14	И	5	10	(20 = 3)
р = 43: М = 3, 7=14,
1	2	4	8	16	32	21	42	41	39	35	27	11	22	(44=1)
3	6	12	24	5	10	20	40	37	31	19	38	зз	23	(46 = 3)
9	18	36	29	15	30	17	34	25	7	14	28	13	26	(52 = 9)
р = 13:М=1,7=12,
1 !	> 4 1	J 3 (	> 12	И	9 {	j 10 1	г (14=1)
p = 31:/V = 6, 7 = 5,
1	2	4	8	16	(32=1)
3	6	12	24	17	(34 = 3)
9	18	5	10	20	(40 = 9)
27	23	15	30	29	(58 = 27)
19	7	14	28	25	(50 = 9)
26	21	11	22	13	(26-3= 16)
Легко увидеть из этих таблиц, что число А = 3 — первообразный вычет
для модулей р— 17, 43 и 31. Предыдущая теорема утверждает, что узоры,
образованные квадратичными вычетами на этих диаграммах, не случайны:
приведенное ниже доказательство показывает, что именно такое располо-
жение квадратичных вычетов (разное в зависимости от остатка при делении
модуля р на 8) неизбежно.
28
Доказательство теоремы. Заметим прежде всего, что если число N
четное, то в строках Аг25 с нечетными г квадратов нет, поэтому в строках
с четными г квадраты не только те (очевидные) вычеты, у которых s четно.
Если какой-либо вычет Д2г22п-1 является квадратичным, то квадра-
тичными будут и все остальные вычеты вида такой же четности,
д2«22и—1 _ д2гд2л— 1(Ди“г2и~л)2
Итак, при четном N квадратичные вычеты — это все вычеты
четных строк, {A2“2S}, и только они.
Если же число строк N нечетно, то, как мы сейчас докажем, ква-
дратичные вычеты составляют половину каждой строки: это вы-
четы {Дг25}, где г и s одной четности.
Для доказательства обозначим нечетное число N через 2г— 1 (и заме-
тим, что период Т при нечетном N четен, так как произведение NT = р — I —
четное число).
Квадрат элемента Аг есть Д^1 = ДЛ/Д.
Лемма L Имеет место сравнение элементов N-й и нулевой
строк,
AN~2‘ (mod р),
где I — некоторое целое число, 0 < I < Т.
Доказательство. Произведения вида
Д“2" (где 0 и < /V, 0 v < Г)
исчерпывают все NT = <р(р) вычетов по модулю р по доказанному выше
основному предложению. Поэтому вычет Д^1 совпадает с одним из них.
Он не может совпасть с вычетом элемента Aw2l какой-либо промежу-
точной строки (для которой 0 < w < N) по тому же основному предложе-
нию. Значит, ш-Ои лемма доказаиа.
Представляя теперь вычет квадрата элемента Аг в виде стоящего в
первой строке вычета Д2*, мы заключаем, что квадратичными являются
также все вычеты элементов всех строк Д"2/“, а, следовательно, и всех
элементов вида Д"2/, где / имеет такую же четность, как 1и.
Таким образом мы получили в каждой из N строк по Т/2 квадратичных
вычетов, т. е. всего у?(р)/2 квадратичных ненулевых вычетов, а значит, мы
получили все квадратичные вычеты.
Кроме того, мы заключаем, что число I нечетно, так как иначе сам вычет
А оказался бы квадратическим, так что А = Д25 (mod р), Д25"1 = I (mod р),
и нечетное число 2s — 1 должно было бы делиться на четный период у?(р)
операции умножения вычетов иа первообразный вычет А.
29
Из нечетности числа I вытекает одинаковость четностей обоих показа-
телей и, v квадратичных вычетов Аи2и в случае нечетности числа строк N.
Чтобы закончить теперь доказательство теоремы, исследуем четность
числа строк N (в зависимости от остатка при делении простого модуля р
на 8).
Лемма 2. Если р = 8с±3, то число строк N нечетно.
Доказательство. Если бы число строк N было бы четным, то мы
нашли бы, для указанных простых чисел р, соответственно,
<р = 8с + 2 = 2(4с+1);
N = 2m\
4с + I = mk;
T = k
<р = 8с-4 = 4(2с-1);
W = 2m или W = 4m;
2c- I = mk\
T = 2k или T — k\
(где число k везде нечетно как делитель нечетного числа <р/2 или <р/4
соответственно, равного mk).
Из указанных формул мы получаем сравнение
2*’/2 = 2'"* = (2г)'" = + 1 при р = 3 (mod 8).
Если же р = 8с — 3, то имеет место либо сравнение
2^/2 — 2^тк = (2Г)Ш = 4-1
в первом указанном выше случае (когда ;V = 2m), либо же сравнение
2^/2 __ 2mk = (2^)^ =
во втором, когда N = 4m. Это во всех трех случаях противоречит свойству
ре (2-) простых чисел р = 8с±3, т.е. выполняющемуся для них сравне-
нию Ферма—Эйлера (имеющемуся в статье [2])
2У>(р)/2-_| (mo(j ру
Лемма 2 доказана.
Лемма 3. Если р = 8с± 1, то число N четно.
Доказательство. Пусть р = 8с-1. Тогда <р = 8с-2 = 2(4с—1), и,
если бы число N было нечетным, то мы нашли бы четный период Т = 2т,
4с- I = mk, N = k.
Мы получили бы тогда для последовательности вычетов {2f (mod р)}
период Т = 2т (по теореме Эйлера или Ферма, что ре (2+)) и у?(р)/2 =
= mk. Из нечетности последнего числа следует, что период Т не минимален,
30
врпреки своему определению. Значит, предположение о нечетности числа
строк N неверно, и лемма доказана в случае р = 8г- 1.
Доказательство в случае р = 8с+ 1 сложнее, и мы рассмотрим сперва
некоторые вспомогательные конструкции.
По теореме Ферма—Эйлера, имеет место сравнение (доказанное, на-
пример, в [2])
2^-1=0 (mod р).
Представим число <р(р) = 8с в виде произведения у?(р) = 2ал, где чи-
сло п нечетно (03). Разлагая разности квадратов на множители, мы
перепишем сравнение Ферма—Эйлера в виде
(2'1 + 1)... (2Л +1)...(2я + 1)(2Я - 1) =0 (mod р),
где ti = 2a~ln, 1 ^i^a.
Одна из этих скобок — нулевой вычет, и мы разберем по очереди два
случая.
Случай I. Имеет место сравнение
2я = 1 (mod р).
Утверждение. В этом случае период Т~ нечетный делитель чи-
сла п = Тт, а число строк четно, N — 2ат.
Действительно, нечетное число п является (по условию I) одним из
периодов умножения вычетов на 2, а значит, кратно наименьшему периоду,
который, следовательно, нечетен. Значит, число строк N четно, так как
77V = у?(р) — четное число.
Случай II. Имеет место сравнение
2// = -1 (mod р).
Утверждение. В этом случае число N четно.
Действительно, возведя сравнение 11 в квадрат, мы убедимся, что число
2//=2а-'+,л является одним из периодов операции умножения вычетов
на 2, и, следовательно, кратно наименьшему периоду Т.
С другой стороны, знак минус в сравнении II показывает, что само
число tj = 2a~ln этому периоду Т не кратно. Значит, число Т делится на
2fl-'+I и ИМеет поэтому вид
где m — нечетный делитель нечетного числа п = mk.
Стало быть, число N — (p(p)/T = 2^mk/(2a~i^lm) — 2i~lk четно, если
i> 1.
31
Если бы число I равнялось 1, то мы имели бы
2чХр^ = -\ (mod р)
вопреки теореме Эйлера—Ферма (8с + 1 6 (24-)), согласно которой (см.,
например, статью [2])
2,р(р)/2 = + 1 (modp).
Итак, мы проверили, что N нечетно, и закончили доказательство леммы 3.
Соединяя полученную информацию о четности чисел Т и N с про-
веденным в начале доказательства теоремы анализом координат и и v
квадратичных вычетов AU2V в зависимости от четности чисел Т и Л/, мы
заканчиваем доказательство теоремы.
§ 14. Приложения к квадратичным сравнениям
Из доказанного в предыдущем параграфе описания узора координат
квадратичных вычетов сразу следуют удивительные результаты о предста-
влении чисел квадратичными формами (описание этой теории и ее связей
с релятивистским миром де Ситтера имеется в статье [9]).
Теорема 1. Если число х2 4- у2 делится на простое число р = 4с 4- 3,
то и х и у делятся на него.
Иными словами:
Теорема 1'. Сравнение х2 4- у2 = 0 (mod р) не имеет ненулевых ре-
шений х (mod р), у (mod р), если р дает при делении на 4 остаток 3.
Следствие. Если уравнение х2 + у2 = п имеет целочисленное ре-
шение, и « = Пр?/П?// — разложение правой части п на простые
множители, где pi =3 (mod 4) для всякого i, то имеет целочисленное
решение уже и уравнение без множителей p-t в правой части, т. е.
х2 +у2~т,
где =
Замечание 1. В частности, ни одно из чисел п = 3,27,21,63 не пред-
ставимо в виде х2 + у2 с целыми х и у.
Замечание 2. В действительности все простые числа q=\ (mod 4)
(и следовательно, согласно статье [9], все произведения их степеней) пред-
ставимы в виде х2 + у2.
Разрешимость этих уравнений для ненулевых вычетов следует из
результатов предыдущего параграфа, но саму представимость q — x2 + y2
(например, 5 = 4+1, 13 = 9 + 4, 17=16+1) мы доказывать не будем,
ограничиваясь исследованием сравнений.
Теорема 2. Если число х2 + 2у2 делится на простое число р —
= 8с + 5 или 8с + 7, то и целые числа х и у делятся на него.
32
Подобно теореме 1' и ее следствию, теорема 2 сводит решение уравне-
ния х2 + 2у2 = л к случаю, когда каждый простой множитель р числа п дает
при делении на 8 в остатке 1 или 3. В этом случае уравнение х2 + 2у2 = р
имеет на самом деле целочисленное решение (откуда следует, согласно
статье [9], и разрешимость уравнения с любой правой частью п, делящейся
лишь на такие простые числа). Но мы не будем этого доказывать, огра-
ничившись лишь легко вытекающим из предыдущего параграфа анализом
сравнений (теоремой 2).
Пример. Для р = 5 всевозможные значения вычетов х, у и формы
х2 + 2у2 (mod 5) составляют матрицу.
\ х	0 12 3 4
0 1 2 3 4	0 14 4 1 2 3 113 3 4 2 2 4 3 4 2 2 4 2 3 113
Нулевая по модулю 5 сумма х2 + 2у2 встречается только в одном
случае, x = 0 = y (mod 5).
Теорема 2 обобщает это наблюдение на случай произвольного простого
числа р вместо 5, но при условии, что оно дает при делении на 8 остаток
5 или 7: в матрице будет тогда только один нуль.
Для р = 1 или 3 (mod 8) положение совершенно иное, решения есть
(для сравнений вместо уравнений, можно было бы получить полное реше-
ние из результатов предыдущего параграфа). Это уравнение было изучено
Якоби, Эйлером и Ферма.
Пример. Формой х2 + 2у2 представимы простые числа
17 = 32 + 2-22= 1 (mod 8),
19= 12 + 2-32 = 3 (mod 8)
и вообще все простые числа, сравнимые с 1 или с 3 по модулю 8, а
также все их произведения (утверждение о произведениях следует из
статьи [9]).
Для вопроса о представлении целого числа целочисленной квадратич-
ной формой доказана его принципиальная сводимость к сравнениям: если
как сравнение по достаточно многим модулям уравнение степени
два разрешимо, то оно имеет и настоящее целочисленное решение
(«принцип Хассе»).
33
Напротив, для диофантовых уравнений более высоких степеней встре-
чается случай разрешимости по любому модулю при отсутствии настоя-
щего целочисленного решения (не знаю, насколько часто это бывает).
Вопрос здесь сходен с проблемой сходимости формальных степенных
рядов для решения задач анализа. Из существования такого формального
ряда следует разрешимость уравнения по модулю сколь угодно высоких
степеней переменных, но не следует, вообще говоря, существование ана-
литического решения: ряд может расходиться.
Доказательство теоремы 1. Пусть сначала р = 8с4-3. Воспользу-
емся описанием узора координат остатков от деления на р квадратов не-
нулевых вычетов
х2 = Л2г225 или Д2г~1225"'1 прир = 8с4-3.
По теореме Эйлера—Ферма, р Е (2-), т. е. имеет место сравнение
(2»’/2 = 24c+i) = -1 (mod р).
Из этого сравнения мы заключаем, что противоположные квадратам
вычеты образуют дополнительный узор,
-y2 = A2r~'22s или Л2^25-1.
Поэтому сравнение х2 + у2 = 0, т. е. х2 = -у2 (mod р), не имеет ненулевых
решений, и теорема 1 доказана в случае р = 3 (mod 8).
При р = 8с + 7 ненулевые квадраты вычетов имеют вид x2 = A2r2s (по
теореме о координатах квадратичных вычетов).
Из сравнения х2 + у2 = 0 (mod р) при y2 = A2a2v мы получили бы
Л2“2Р( 1 + A2(r~u'2s~v) = 0 (mod р),
что, как мы сейчас увидим, невозможно.
Действительно, вычет — 1 по модулю р может иметь только одна сте-
пень первообразного вычета А, а именно Л*’/'2 = Л4с+3 (ведь квадрат этой
величины должен быть вычетом 1, так что удвоенный показатель степени
должен делиться на период <р(р) прогрессии {Л'}).
Итак, при x2 + p2 = 0 (mod р) мы получили бы сравнение
Л2^-«)25-р = Л4с+3 (mod р).
Используя сравнение 2Г=1 (mod р) и определение числа строк N, мы
приводим его к сравнению вида
Ad2e=l (0<d</V, 0<е<Т)
34
с нечетным показателем d. Это последнее сравнение противоречит дока-
занному в предыдущем параграфе основному предложению о различии всех
NT вычетов такого вида.
Стало быть, сравнение х2 + у2 = 0 (mod р) не имеет ненулевых ре-
шений вида р = 8с + Т.
Теорема 1 доказана (открыл ли ее первым Ферма или только Эйлер, я
не сумел понять).
Доказательство теоремы 2. Пусть опять р = 8с + 7, так что узор
квадратов имеет вид
x2 = 42r2s, г/2 = Л2"2у (mod р).
В этом случае имеет место сравнение
х2 + 2у2 = A2r2s + A2u2v+X (mod р).
Неразрешимость этого сравнения относительно не нулевых вместе вы-
четов х, у уже доказана (при разборе случая р = 8с + 7) в доказа-
тельстве теоремы 1. Значит, не нулевых вместе решений сравнение
х2 + 2у2 = 0 (mod р) не имеет.
Пусть теперь р = 8с + 5. В этом случае из теоремы о координатах ква-
дратичных вычетов мы находим сравнения для узора ненулевых квадратов
? = АГ22' (0Cr<N, 0^2i<T),
y2 = A"22v (Q^u<N, Q^2v<T).
Следовательно, из сравнения х2 + 2у2 =0 (mod р) (с не нулевыми вме-
сте вычетами х и у) вытекает сравнение
Дг22' +Л"2(2в+1) = 0 (mod р).
С другой стороны, по теореме Ферма—Эйлера «р Е (2—)» из (2] имеет
место сравнение
(2*’(р)/2 = г4'4-2) = -1 (mod р),
так что мы можем привести предыдущее сравнение к виду
Лг22.+4с+2 = л«22с+1 (mod р).
Это сравнение опять противоречит неразрешимости сравнений вида
4d2‘=l (Q^d<N, 0<e<T)
(где (d, е)^(0,0)), доказанному в основном предложении предыдущего
параграфа (о различии всех NT вычетов такого вида).
Теорема 2 доказана.
35
Все эти примеры применения геометрии узоров, образуемых квадра-
тичными вычетами Ad2e на плоскости с координатами d и е, подсказыва-
ют возможность использования наших результатов и их естественных
обобщений на прогрессии {<?} для исследования мультипликативной
полугруппы целых чисел, образованной всеми значениями бинарной ква-
дратичной формы тх2 + пу2 + kxy. Полугруппу значения формы обра-
зуют, например, если форма представляет единицу (как ее представля-
ет всякая форма вида х2 + пу2). Другой пример полугруппы образуют
значения {Nf}, где N — одно из значений формы f (скажем, значения
формы 4х2 + 2пу2 = 2(2х2 + пу2)). Много других примеров описано в
статье [9].
Все эти мультипликативные полугруппы было бы интересно исследо-
вать в геометрических терминах многогранников Ньютона, образованных
векторными показателями степеней входящих в элементы полугруппы про-
стых множителей:
n = 2a3b5c7d....
Векторы бесконечномерного пространства с компонентами (а, 6, с,
d,...), соответствующие входящим в полугруппу значений числам и,
образуют уже аддитивную полугруппу, и интересно было бы узнать,
допускает ли она столь простое описание, как полугруппа значений формы
Гаусса квадрата нормы комплексных чисел х2 + у\ где это описание
таково: показатели (b,d,...) простых чисел, дающих при делении
на 4 в остатке 3, должны быть четными.
В случае формы х2 + 2//2 описание полугруппы значений тоже про-
сто: четными должны быть показатели простых чисел, дающих при
делении на 8 в остатке 5 или 1.
Но вообще, говоря, аддитивные полугруппы целочисленных векторов
могут иметь куда более сложную структуру (например, для полугрупп век-
торов на плоскости или в трехмерном пространстве).
Было бы интересно узнать, встречаются ли такие сложности в полу-
группах теории чисел, или же, может быть, полугруппа значений квадра-
тичной формы всегда допускает простое описание, подобное приведенным
выше примерам (или конечности базиса полиномиального идеала).
В обоих наших примерах, ограничения накладывались только на
векторную оболочку аддитивной полугруппы (условия четности некото-
рых координат), тогда как в общей аддитивной полугруппе возможны
еще ограничения типа неравенств. Можно взять, например, в качестве
аддитивной полугруппы множество тех целых точек некоторой решетки,
которые лежат внутри какого-либо выпуклого конуса (или многогранника
Ньютона).
36
Ни одного примера полугрупп значений квадратичных форм с такими
нетривиальными многогранниками Ньютона я не знаю.
В самой геометрии аддитивных полугрупп, даже состоящих просто из
натуральных чисел, тоже много открытых вопросов. Например, полугруппа
{тх + пу}> порожденная двумя взаимно простыми натуральными числами
х и у (и состоящая из их линейных комбинаций с неотрицательными це-
лыми коэффициентами), содержит все целые числа, начиная с указанного
Сильвестром предела К = (/п- 1)(п — 1), а от нуля до этого предела по-
лугруппа содержит ровно половину целых чисел (а именно, если число с
входит, то К — 1 — с не входит в полугруппу). Пример: х = 3, у = 5, К = 8,
входят {0,3,5,6}; не входят —{7,4,2,1}.
Обобщения этих результатов Сильвестра на случай большего двух чи-
сла образующих остаются пока гипотезами, даже если ограничиваться (как
это и разумно здесь делать) усредненными асимптотиками величин вроде
K(x,y,z) для большинства больших векторов (x,i/,z), пренебрегая редко
встречающимися большим отклонениями (подробнее об этом написано в
статье [3]).
Интересно также исследовать число представлений большего элемента
полугруппы суммами образующих: здесь тоже имеются, видимо, краси-
вые ответы, если не гнаться за точными формулами, а ограничиваться
средними асимптотиками, описывающими кратности проекций множества
целых точек соответствующего выпуклого многогранника на типичные це-
лочисленные прямые (и пренебрегая редко встречающимися большими
уклонениями от средних).
Переход к подобным усредненным асимптотикам является самым
многообещающим подходом ко многим задачам диофаитовой геометрии,
включая и задачи о целочисленных квадратичных формах и о целочислен-
ных геометрических прогрессиях, рассматривавшиеся Ферма и Эйлером и
описанные выше (см. также [3]).
Эта программа применима, например, к исследованию асимптотики
наименьшего периода Т(а,п) геометрической прогрессии {a'(mod л),
t = 1,2,...} при больших значениях модуля п: верно ли, что период Т(2, п)
растет (в среднем) как степенная функция от п (или, во всяком случае,
быстрее, чем л,-а, или чем zi/inn)? Как растет период Г(3,л)? Что
происходит с периодом при одновременном росте и а, и п (при значениях
а порядка сп)?
Здесь были бы интересны даже просто численные эксперименты: имен-
но так Ферма открыл свою «малую теорему», а Лежандр —закон распре-
деления простых чисел (со средней плотностью 1/ In п). -
Таблица периодов Т(а,п) геометрических прогрессий {t? (mod л),
/= 1,2,...} начинается со следующих значений наименьших периодов:
37
а					
20 19 18 17 16				2 2 2 9 4 2	9	
15 14 13 12 11			2 2 4 2 2 12 3 2	2	8	18 16	18 4	4	3	18	4 16	6 4	16	6	3	2	
10 9 8 7 6		2 2 2 3 4 2	2	6 5	3	3 10	4	4 10 2 12	4 10	12	16	18 2	8	9	2 8	6 2	16 3 3	4 16	9	
5 4 3 2 1	2 2 4 2	4 1111	2 6 2 6 3	3 6 2	4 3	6 11111	5 2	4	6 5	6	2 5	3	6 10	12	4 11111	4	16 6 9 4	9 4	16	18	4 8	18 11111	
	2 3 4 5	6 7 8 9 10	II 12 13 14 15	16 17 18 19 20	п
S	1 4 7 18	21 43 50 71 82	145 152 227 248 271	294 465 486 669 694	
м	1 1,5 1,5 2,75	1,5 3,5 1,75 3,5 2,75	6,3 1,75 6,25 3,5 2,9	2,9 10,7 3,5 10,2 3,1	
В графе S внизу таблицы указана для каждого модуля п сумма всех
периодов, S = 52 Т(а, т), для 1 < а < т (взаимно простых с т) для преды-
дущих модулей, включая п (для т^п). Суммирование облегчает анализ
асимптотик, играя роль усреднения.
В графе М указан средний (по а) период для каждого модуля п. Зна-
чения а берутся только взаимно простые с п.
Ориентировочные выводы о поведении в среднем подсказывают, что S
растет подобно ся2/2 (с коэффициентом с порядка 1/5), а средний период
М — подобно qn (с коэффициентом q порядка 1/3).
Эти наблюдения интересно сравнить с тем обстоятельством, что для
простого п максимальное значение периода, Т(а,п) = <р(п), достигается на
^(^(я)) первообразных вычетах а по модулю п. Если учесть, что функция
Эйлера в среднем растет как (6/тг2)я, и если (незаконно) воспользовать-
ся предыдущим обстоятельством для не простых п тоже, то получился бы
вклад этих наибольших периодов в их сумму порядка (б/тг2)3^, а в сумму
S по предыдущим модулям — порядка (6/тг2)3я2/2«я2/7.
В качестве оправдания незаконного перехода от простых п к произ-
вольным, замечу, что для <р(п) переход от <р(р) =р - 1 к среднему росту
<р(п) как (6/тг2)п лишь меняет в асимптотике коэффициент 1 на 6/тг2 « 2/3.
38
• Для среднего периода такое же (незаконное) рассуждение дает линей-
ный рост с модулем, п: доля максимальных значений периодов составляет в
среднем порядка 2/3 от всех периодов Т(а,п) (при фиксированном модуле
/2), так что можно грубо оценивать средний период как две трети мак-
симального, равного <р(п). Предполагая последний растущим как (2/3)/2,
получаем грубую оценку среднего по а периода порядка (4/9)/2. Но, конеч-
но, простые значения п составляют лишь малую долю всех, (да и <р(п) для
них порядка /2, а не (2/3)/г), так что распространение формул, имеющих
место для простого модуля, на средние по п значения надлежит сопрово-
дить надлежащими изменениями (хотя бы значений коэффициентов), для
осуществления которых предыдущую таблицу периодов нужно было бы
продолжить гораздо дальше.
Для геометрических прогрессий с фиксированным основанием а та-
блица тоже приводит к эмпирическим данным об усредненном по п росте
периода Т(а,п) с ростом модуля п (взаимно простого с а).
В переделах приведенной выше таблицы приближение имеет линей-
ный вид Т(2,л) fcan, и «0,38, а для основания а = 3 —вид 7(3,/2) &vn,
и «0,31. Но это —только усреднение, отклонения от них довольно велики
(7(2,15) = 4, но 7(2,19) = 18). Проведенные мною при больших модулях
/2, вплоть до /2 = 511, вычисления периода 7(2, п) показывают в среднем
линейный по п рост с несколько меньшим при больших п коэффициентом и
и не исключают возможности убывания этого «коэффициента» с ростом п
(скажем, как 1/1п п).
Например, 7(2,511) = 9, но соседние модули дают гораздо большие пе-
риоды: 7(2,499) = 166, 7(2,503) = 251, 7(2,509) = 508, а среднее периодов
7(2, п) по десятку нечетных модулей от п = 493 до п = 511 равно примерно
158, что соответствовало бы коэффициенту 1/3.
Проведенные по моей просьбе Ф. Аикарди вычисления значений пери-
одов Т(п) и чисел орбит N(n) при модулях п 2001 приводят к следую-
щим (удивительным) приближенным эмпирическим формулам, удовлетво-
рительно описывающим рост этих функций в среднем:
Л/~0,67п2/5, Т~1,41л4/5.
Эти «слабые асимптотики» получаются из линейной (неоднородной) ап-
проксимации наблюденной зависимости логарифмов сумм значений
(л	\	/л	\
Ел/W . ig
Л-1	/	\Л-1	/
от логарифма аргумента, lg/2 (где суммирование распространено на не-
четные значения fe, если исследуются период 7 и число орбит систе-
39
мы Ферма—Эйлера, определяющей геометрическую прогрессию вычетов
{2' (mod k)}).
Таблицы Аикарди доставляют, например, следующие значения сумм:
п	9	109	509	1009	1509	2009
п	5	132	1017	2625	4651	6921
п тл	15	1409	23607	82761	176016	302277
(для 2001 < k < 2009 данные экстраполированы).
Если бы число орбит и период имели асимптотики степенного вида,
N(n)~ana, T(n)~bn0,
то для сумм получились бы (интегральные) асимптотики тоже степенного
вида,
^N(k)^ana+l, ^T(k)^bn0+l.
k=\	Л=1
Поэтому эмпирические данные о поведении и (сумм, которые
ведут себя гораздо менее хаотически, чем сами сильно осциллирующие
слагаемые N и Т) доставляют приближенные значения коэффициентов
(а, а; 6,0), которые и указаны выше.
Замечание. Полученные из наблюдений значения а «2/5 и 0«4/5
могут удивлять, так как произведение ip(n) = N(n)T(n) растет в среднем
как сп (где с = б/тг2 « 2/3).
Казалось бы, сумма показателей асимптотик, а и 0, должна бы быть
поэтому равной единице (показателю слабой асимптотики произведе-
ния у?).
Но слабая асимптотика произведения может сильно отличаться от
произведения слабых асимптотик сомножителей, так как среднее значение
произведения может сильно отличаться от произведения средних значений
сомножителей, особенно если большие и малые значения сомножителя
перемежаются.
Пример. Предположим, что значения сомножителя N(n) перемежа-
ются в окрестности значения п своего аргумента так: N принимает два
значения
(jV1=n«)»(jV2=l) (0<ц<1),
причем первое в nw раз чаще, чем второе (о>>0).
Для сохранения значения произведения NT = n предположим, что вто-
рой сомножитель принимает, соответственно, значения
(Tl=n'-u)<z(T2 = n).
40
В этой ситуации вклады указанной окрестности b^N и в 52 определя-
ются, соответственно, в основном первой и в основном второй частью: они
пропорциональны, соответственно, nu+w н п] (если 1 -u + w< 1, чтобы
вклад 52 Л был меньше вклада 52 Тг)-
Таким образом, наблюдаемые эмпирически слабые асимптотики со-
множителей были бы степенными, с показателями
a = u + w, /3=1,
сумма которых больше 1.
Для этого нужно только, как указано выше, чтобы показатель переме-
жаемости, w, превосходил величину показателя и.
Анализ наблюденных значений Т(п) и N(n) показывает их значитель-
ную перемежаемость. Например, значения числа N(n) изменяются при
небольшом изменении аргумента п в десятки раз:
/V( 1969) = 2, N( 1971) = 72, N( 1973) = 1.
Неплохую в среднем аппроксимацию частот ры значений величины
N(n) при изменении аргумента в окрестности данного значения модуля
п дают (для п 2001) следующие эмпирические приближенные слабые
асимптотические формулы (где /V= 1,2,4,8 и /V> 10):
Р1~С1П-7/18, Р2~С2Я“1/9, Р4^С4/?1/3, Р8^С8/?1/9, Р^Ю^СюП1.
Из этих формул видно, что отношения частот встречаемости больших
и малых значений N ведут себя как степенные (в среднем) функции от п
(подобные величине п частоты перемежаемости в разобранном выше при-
мере).
Все эти, не подтвержденные никакими теоремами, эмпирические
данные можно рассматривать как математические гипотезы. В их пользу
говорит удивительно точное расположение графиков соответствующих
функций-сумм f и g, нарисованных на двойной логарифмической бумаге в
окрестностях соответствующих прямых линий.
Речь идет о функциях (определенных значениями N(k) — у и T(k) = z,
встречаемость которых изучается):
gz(n) = (#Л: Т(Л) = 2, 1 k п).
Прямолинейность или почти прямолинейность их графиков на двойной
логарифмической бумаге означает приближенные формулы
+ \ggz(n)&Cz\gn + Dz (Ау=] +ay,Cz=i+0z).
41
Указанные выше показатели ау, 0г степенных асимптотик (ai = -7/18,
...) найдены именно путем рисования этих прямых, априорных оснований
для рациональности этих показателей я не знаю (кроме, разве, теории
турбулентности).
Список литературы
[1]	Arnold V. Ergodic and arithmetical properties of geometric progression
dynamics. To appear in Moscow Mathematical Journal.
[2]	Арнольд В. И. Динамическая система Ферма—Эйлера и статистика
арифметики геометрических прогрессий // Функциональный анализ и
его приложения. 2003. Т. 37, вып. 1. С. 1 — 18.
[3]	Арнольд В. И. Слабая асимптотика чисел решений диофантовых задач
Ц Функциональный анализ и его приложения. 1999. Т. 33, вып. 3.
С. 65-66.
[4]	Арнольд И. В. Теория чисел. М.: Учпедгиз, 1939. 288 с.
[5j Fermat Р. CEuvres de Fermat, Т. I—IV. Paris, 1894—1912.
[6]	Euler L. Commentationes arithmeticae collectae, T. 1. Санкт-Петербург,
1849. 584 с.; T. 2. Санкт-Петербург, 1849. 651 c.
[7]	Jacobi C. G. J. Canon Arithmeticus. Berolini, 1839. 248 pp.
[8]	Венков Б. А. Элементарная теория чисел. М,—Л.: ОНТИ, 1937. 218 с.
[9J	Arnold V. I. Arithmetics of binary quadratic forms, symmetry of their
continued fractions and geometry of their de Sitter world Ц Bull. Brasil
Math. Soc. 2003. Vol. 3, №. 1. P. 1-41.
[10]	Арнольд В. И. Топология и статистика формул арифметики Ц Успехи
матем. наук. 2003. Т. 58, вып. 4. С. 3—28.
[11]	Арнольд В. И. Топология алгебры: комбинаторика операции возведе-
ния в квадрат Ц Функциональный анализ и его приложения. 2003.
Т. 37, вып. 3. С. 20-35.
[12]	Летняя школа «Современная математика» (Москва—Дубна, 2002).
МЦНМО, 2002. 40 с.
[13]	Dirichlet L., Abhandlungen Akad. Wiss. Berlin (Math.). 1849. P. 78—81
(Werke, Vol. 2. P. 60-64.)
42
Оглавление
§	1. Основные определения................................... 3
§	2. Отступление о функции Эйлера........................... 3
§3	. Таблица групп Эйлера................................... 7
§4	. Группы Эйлера произведений............................. 9
§5	. Гомоморфизм приведения по модулю а, Г(аЬ)	—»Г(а)....... 9
§6	. Доказательства теорем о группах Эйлера..................И
§	7. Динамическая система Ферма—Эйлера..................... 15
§	8. Статистика геометрических прогрессий ..................17
§9	. Измерение степени случайности подмножества............ 18
§	10. Среднее значение параметра стохастичности.............20
§11	. Дополнительные замечания о динамике Ферма—Эйлера......22
§	12. Первообразные корни простого модуля ..................24
§13	. Узор координат квадратичных вычетов...................26
§	14. Приложения к квадратичным сравнениям..................32
Владимир Игоревич Арнольд
ГРУППЫ ЭЙЛЕРА И АРИФМЕТИКА ГЕОМЕТРИЧЕСКИХ ПРОГРЕССИЙ
Лицензия ИД №01335 от 24.03.2000 г. Формат 60x90/16. Печать офсетная.
Объем 2,75 печ. л. Тираж 1000 экз. Заказ №16т
Издательство Московского центра непрерывного математического образования.
119002, Москва, Большой Власьевский пер., 11. Тел. 241—72—85.
Отпечатано с готовых диапозитивов в ФГУП «Полиграфические ресурсы».