Золотая теорема

2

Золотая теорема

С. Г. Гиндикин

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

Л. Эйлер

Мы совершим экскурс к истокам современной теории чисел — отрасли математики, изучающей натуральные числа. В то время математики подмечали удивительное простые и красивые закономерности в мире натуральных чисел. Но часто интугиюя простота формулировок обращалась неприступностью решения. Лобовые atаки не давали успеха, приходилось придумывать обходные пути, создавать совершенное новый аппарат.

Мы рассекjem здесь об одной такой задаче*), формулировка которой понятна школьнику, знающему, что такое простое число. Но решить эту задачу далеко не просто, и первый шаг на пути ее решения совсем не сразу удалось сделать велиkomу Эйлеру. Гипотезу, формулированную Эйлером (но не доказанную им), пытаемся доказать Ланггранж и Лежандр; удалось это сделать девятнадцатилетнему Гауссу. Это была его вторая работа **).

Гауссс называл доказанную им теорему «золотой теоремой». В ней идет речь о том, какими могут быть остатки от деления квадратов целых чисел на простые числа. Мы не будем сейчас приводить полной формулировки утверждения, доказанного Гауссом, отложив это до стр. 5. Сейчас же мы появим постановку задачи, введем некоторые термины и подробно рассмотрим частный случай «золотой теоремы», доказанный Эйлером.

Хорошо известны различные условия, необходимые для того, чтобы число было квадратом. Например, такое число может оказаться только на 0, 1, 4, 5, 6 или 9. Другое часто использующее свойство состоит в том, что квадрат целого числа или делится на 3 или при делении на 3 дает остаток 1 (доказhte). Первое свойство можно формулировать в тех же терминах, что и второе, заметив, что последняя цифра — это остаток от деления на 10.

Всюду ниже мы будем предложать, что $p$ — простое число, причем $p \neq 2$. Делить целые числа можно «с недостатком» или «с избытком». Иными словами, остатки можно считать положительными или отрицательными. Условия выбирать остаток наименьшим по абсолотной величине.

Нетрудно доказать, что если $p$ нечетно, то всякое целое число $n$ единственным образом представляется в виде

$$n = pq + r, \quad |r| \leq \frac{p-1}{2},$$

где $q$ и $r$ — целые.

4

ставных $p$ наше утверждение не верно).

Далее, очень надо 0 и 1 являются красьми во всех строихах. Что касается остальных стольцов, то сразу не видна закономерность, согласно которой в них появляются красьные числа. Начнем с $a = -1$. Оно является красьим при $p = 5, 13, 17, \dots$ и черным при $p = 3, 7, 11, \dots$. Вы, может быть, заметили, что простые числа первой группы при делении на 4 дают остаток 1, а второй — остаток — 1 (заметьте, что простые числа $p \neq 2$ других остатков вообще не могут). Итак, можно предложить, что — 1 является квадратным вычетом для простых чисел вида $p = 4l + 1$ и квадратным невычетом для $p = 4l - 1$. Эту закономерность первым заметил Ферма (1601—1665), однако оставил ее без доказательства. Попытайте найти доказательство самостояльно! Вы убедитесь, что главная трудность в том, что не видно, как воспользоваться простой $p$, а без этого предложения утверждение становится неверным.

Первое доказательство после нескольких неудачных попыток нашел в 1847 году Эйлер (1707—1783). В 1855 году Эйлер нашел другое, очень изящное доказательство, использующее малую теорему Ферма: Если $p$ — простое число, мо для всякого целого $a$, $0 < |a| < p$: $a^{p-1} \equiv 1 \pmod p$. (2)

Известно много различных доказательств этой теоремы. Однако из них приведено в МТФ. Здесь мы приводим другой доказательство, близкое по идее к другим рассмотреням этой статьи.

Доказательство. При $p = 2$ утверждение очевидно, и можно считать $p$ нечетным. Расмотрим $p$ чисел $0, \pm a, \pm 2a, \pm 3a, \dots, \pm ka; k = \frac{p-1}{2}$. Все эти числа при делении на $p$ дают разные остатки, так как в противном случае $r_1 a - r_2 a, r_1 > r_2, |r| \leq k, |r_2| \leq k$, делится на $p$, но $a$ не делится на $p$ и $r_1 - r_2$ не делится на $p$, так как $0 < r_1 - r_2 < p$. Переменным те из рассматриваемых чисел, которые отличны от нуля; получим $(-1)^k (k!)^2 a^{p-1}$. Поскольку средим остатков сомножитель содержится все нульные вычеты и учитывая правильное вычисление остатка произведения, получаем, что произведение имеет тот же вычет, что и $(-1)^k (k!)^2$, то есть $(k!)^2 (a^{p-1} - 1)$ делится на $p$. Так как $k!$ не делится на $p$ ($0 < k < p$), то на $p$ делится $a^{p-1} - 1$, и доказательство окончено.

Следствие (критерий Эйлера квадратности вычета). Выcem $b \neq 0$ является квадратным моеда и молко моеда, коеда

$$b^k \equiv 1 \pmod p, \quad k = \frac{p-1}{2}. \quad (3)$$

Доказательство условия (3) установливается легко. Если $a^2 \equiv b \pmod p$, $0 < a < p$, то $a^{2k} = a^{p-1}$ и $b^k$ должно иметь одинаковые вычеты, равные, в силу (2), 1. Достаточно покажаться сложнее. Мы выведем ее из следующей леммы, доказанной в МТФ.

Лемма 1. Если $P(x)$ — многочлен стерегии $l$, $p$ — простое число, и имеется более $l$ различных вычетов $r$ по modulo $p$, для которых

$$P(r) \equiv 0 \pmod p, \quad (4)$$

мо (4) имеет место для всех вычетов.

Приименим лемму к многочлену $P(x) = x^k - 1$. Тогда соответствие (4) удовлетворяет $k$ ненулевых квадратных вычетов. Однако имеет вычет $(r = 0)$, не удовлетворяющий (4); значит, по лемме, все квадратные вычеты должны не удовлетворять (4) и, следовательно, условия (3) достаточно.

Заметание. Для квадратного невычета $b$ имеем: $b^{\frac{p-1}{2}} \equiv -1 \pmod p$. Действительно, если $b^{\frac{p-1}{2}} \equiv r \pmod p$, то $r^2 \equiv 1 \pmod p$, откуда $r = -1$. (Сравнение $r^2 \equiv 1 \pmod p$ удовлетворяет только вычета: $r \equiv 1 \pmod p$, $r \equiv -1 \pmod p$).

Критерий Эйлера позволяет мгновенно решить вопрос о том, для каких $p$ вычет — 1 является квадратным. Подставляя в (3) $b = -1$, получаем, что при $p = 4l + 1$ (3) выполняется $(k - \text{четно})$, а при $p = 4l - 1$ (3)

5

не выполняется ($k$ — нечетно). Сформулированная выше гипотеза стала теоремой.

Задача 1. Доказать, что если $p \neq 2$ есть простой делимель числа $n^2 + 1$, то $p = 4l + 1$.

Итак, мы доказали, что $-1$ — квадратный вычет для $p = 4l + 1$ и квадратный невычет для $p = 4l - 1$.

Обсуждим некоторые особенности приведенного доказательства. Это утверждение состоит из двух частей: отрицательное утверждение для $p = 4l - 1$ и положительное для $p = 4l + 1$. В первом случае естественно пытается найти неокоторес свойство, который квадратные вычеты удовлетворяют, а $-1$ не удовлетворяет, что и сделал Эйлер. Найdenное свойство оказывается характеристческим, то есть одновременно удалось доказать и вторую часть гипотезы. Если вы проволали доказать эту часть утверждения самостоятельно, что вы, верятоно, пытались явно построить по $p = 4l + 1$ число $n^2$, дающее при делении на $p$ остаток $-1$. Доказательство Эйлера не эффективно в том смысле, что оно не дает явной конструкции для числа $n$ по $p$, а лишь утверждает его существование. Иными словами гарантируется, что если мы будем перебирать числа $1,2,...,2l$, возводить их в квадраты, брать остатки от деления квадратов на $p$, то рано или поздно мы получим $-1$. Остается открыть вопрос, нельзя ли указать более явную конструцию $n$ по $p$, не использушую процедуры перебора. Положительный ответ дал Лангганж (1736—1813) в 1773 году, использую следующую теорему.

Теорема Вильсона*). Если $p = 2k + 1$ есть простое число, то $(-1)^k (k!)^2 \equiv -1 (\bmod p)$.

Для доказательства этой теоремы мы воспользуемся lemma 1. Положим $P(x) = (x^2 - 1)(x^2 - 4) \ldots (x^2 - k^2), Q(x) = x^{2k} - 1$. Тогда $R(x) = P(x) - Q(x)$ — многочлен степени не выше $2k - 1$, который при $x = \pm 1, \pm 2, \ldots, \pm k$ делится на $p$ (этом свойством обладает $P$ и $Q$). По лемме $R(x) \equiv 0 (\bmod p)$ для всех $x$. Собственно, новый фактор является лишь то, что $R(0) \equiv 0 (\bmod p)$. Поскольку $R(0) = (-1)^k (k!)^2 + 1$, получаем (5).

Следствие Лагранжа. При $p = 4l + 1$ имеем: $[(2l)!]^2 \equiv -1 (\bmod p)$.

Задача 2. Доказать, что если (5) верно, мо $p$ — простое число.

Эта задача дает повод отметить, что в конструкции Лагранжа простота $p$ существует.

*) Вильсон (1741—1793) — юрист, изучавший математику в Кембридже.

Выяснить, когда $a = -1$ является квадратным вычетом, Эйлер, используя огромный числовой материал (его таблица намного превышает вторую из приведенных выше таблиц), пытается найти аналогичные условия для других $a$. Он подмечает, что при $a = 2$ все зависит от остатка при делении $p$ на 8; 2 оказывается квадратным вычетом для простых $p = 8l \pm 1$ и невычетом при $p = 8l \pm 3$ (простое число при делении на 8 может давать остатки $\pm 1, \pm 3$). Далее, 3 является квадратным вычетом при $p = 12l \pm 1$ и квадратным невычетом при $p = 12l \pm 5$. Эйлер высказывает гипотезу, что и в общем случае все определяется остатком от деления $p$ на 4a.

Гиотеза Эйлер*). Число а одновременно является или квадратным вычетом или квадратным невычетом для всех простых чисел, входящих в арифметическое проресецию $4aq + r$, $q = 0, 1, 2, \ldots, 0 < r < 4a$.

Ясно, что если $4a$ и $r$ имеют общий делитель $s > 1$, то в арифметической проресеции не будет ни одного простого числа. Если же первый член и разность проресеции взаимно просты, то, как утверждает теорема Дирихле (1805—1859), в этой проресеции имеется бесконечное простых чисел (обобщение теоремы о бесконечности числа простых чисел в натуральном ряду).

Возвратимся к гипотезе Эйлер. Окаазось, что критерий Эйлер, который сослужил нам добрую службу при $a = -1$, отказывал уже при $a = 2$. Эйлер не удалось разобраться в этом случае. Ему удалось доказать свою гипотезу, не считая $a = -1$, лишь при $a = 3$. Затем Лагранж, который мы уже упоминали, доказал гипотезу при $a = 2, 5, 7$; Лежандр (1752—1833) в 1785 году предложил доказательство гипотезы для общого служа, которое, однako, содержало существенные проблемы.

*) Гаусс, доказавший эту гипотезу, назвал ее «золотой теоремой».

6

Приложение

Перейдем теперь ко второй части нашего рассказа, из которой наиболее чистые читатели узнали доказательство гипотезы Эйлера.

30 марта 1796 года девятнадцатилетний Гаусс доказал возможность построения правильного семнадцатугольника циркулем и линейкой. С этого дня начнется дневник Гаусса — летопись его удивительных открытий. Вторая запись в дневнике появилась уже 8 апреля. В ней сообщалось, что найдено строгое доказательство «золотой» теоремы — так называл Гаусс гипотезу Эйлера. Он переоткрыл ее, еще учась в брауншвейгской гипназии, когда ему не были доступны произведения Эйлера, Лагранжа, Лежандра, с которых он познакомился лишь после переезда в Геттинген в 1795 году. Вначале он, как и его предшественники, замечает утверждение для $a=-1$, затем, уже гладав результат для общего случая, последовательно разбиает случай за случай, продвинувшись дальше других: им рассмотрен $a=\pm 2$, $\pm 3$, $\pm 5$, $\pm 7$. Наконец, 8 апреля 1796 года он находит общее доказательство, которое Кронекер (1823—1891) очень метко назвал «пробой сил Гауссова гения». Доказательство проводится двойной индикцией по $a$ и $p$; Гауссу приходит при думывать существенно различные сообщения для рассмотрения восемми (!) различных случаев. Нужно было иметь не только порядательную изобретательность, но и удивительное мужство, чтобы не оставиться на этом пути. Позднее Гаусс нашел еще шесть доказательств «золотой» теоремы (ныне их известно около пятдесятей). Как это часто былоет, после того как теорема доказана, удается найти доказательства много более простые, чем первоначальное. Мы приведем здесь доказательство, мало отличующесся от третього доказательства Гаусса. В его основе лежит ключевая лемма, доказанная Гауссом не ранее 1808 года.

Лемма 2. Пусть $p=2k+1$ — простое число, $a$-целое число, $0<|a| \leq 2k$; $r_1, r_2, \dots, r_k$-вычисленные чисел $a, 2a, \dots, ka$; $v$-число отрицательное

$a^k \equiv (-1)^v (\text{mod } p)$. (6)

Применя критерий Эйлера, получаем такое следствие:

Критерий Гаусса квадратично вычета. Выцем являемся квадратным мода и молко мода, когда фцерурирующее в лемме 2 число $v$ ценно.

Доказательство леммы 2. Заметим, что все вычеты $r_1, \dots, r_k$ различны по абсолотной величины. Это следует из того, что сумма и разность любых двух из них не делится на $p: r_i \pm r_j = (i \pm j) a$, $i \neq j$; $|i \pm j| < p$, $|a| < p$. Таким образом, набор моделей $|r_1|, \dots, |r_k|$ — это числа 1, 2, . . . , $k$ в некотором порядке. В результате произведение $a \cdot 2a \dots ka = a^k k!$ при делении на $p$ дает тот же остаток, что $r_1 \dots r_k = (-1)^v k!$. Учитывая, что $k!$ не делится на простое число $p$, получаем (6).

Доказательство гипотезы Эйлера. Заметим, что в приводимом ниже рассужении уже не использовется простота $p$ — она в полной мере использована в лемме Гаусса. Отметим на числовой оси точки (рис. 1, $a, \delta$) $m \frac{p}{2}$, если $a > 0$, и $-m \frac{p}{2}$, если $a < 0$; $m = 0$, $1, 2, \dots, |a|$ — сине точки ($m$ — их номера). Занумерем интервалы с концами в этих точках по номерам левых концов (на рисунках номера интервалов — красные). Отметим теперь $a, 2a, \dots, ka$ — зеленье точки; так как $a$ — целое, не делущее на $p$, то сине точки не могут совпать.

7

Рис. 2.

с зеленьми, причем все зеленье точки попадут в какие-то из построенных интервалов $\left(|a| \frac{p}{2} \geq |a| k\right)$. Легко заметить, что фигурирующее в лемме число $v$ — это число зеленьых точек, попавших в интервалы с нечетными номерами (доказhte!).

Подвергнем теперь нашу картинику преобразования подобия с коэффициентом $\frac{1}{a}$ (рис. 1 перейдет в рис. 2).

При этом сине точки перейдет в точки, делящие отрезок $\left[0, \frac{p}{2}\right]$ на $|a|$ равных частей, а зеленье точки — в целочисленные точки 1, 2, …, $k$.

Нумарация интервалов теперь будет зависеть от знака $a$: при $a > 0$ они нумеруются номерами левых концов, при $a < 0$ — номерами правых концов; $v$ — число целочисленных точек в интервалах с нечетными номерами. Если мы увеличим $p$ на 4ал, то в каждой интервал добавится точное 2л целых точек. Это следует из того, что при сдвиге интервала на целое число количество целых точек в нем не меняется, а на любом отрезке целочисленной длины $n$ или интервале длины $n$ с нечеточисленными концами имеетровно $n$ целых точек (доказhte!). Итак, при изменении $p$ на $p + 4ал$ величины $v$ изменится на четное число, а $(-1)^v$ не изменится. Значит, для всех $p$ в арифметической прогрессии $p = 4aq + r$ значение $(-1)^v$ одно и то же, и гипотеза Эйлера доказана.

Одновременно указаан неокоторый способ выяснить, является ли $a$ квадратным вычетом для $p$. Нужно взять остatok $r$ от деления $p$ на 4a (для удобства положительной); разделить $\left(0, \frac{r}{2}\right)$ на $|a|$ частей, зануемеров их номерами левых (правых) концов, если $a$ — положительное (отрицательное); сосчитать число $v$ целых точек, попавших в интервалы с нечетными номерами; $a$ — квадратный вычет в том и только том случae, когда $v$ четно.

Проделаем эти вычисления для $a = 2$, чтобы подтвердить наблюдания Эйлера, о которых говорилось на стр. 5. Пусть $a = 2$; тогда достаточно рассмотреть $r = 1, 3, 5, 7$, поскольку в остальных случаях арифметическая прогрессия не будет содержать простых чисел. Как видно из рис. 3, число 2 является квадратным вычетом для

$$p = 8q + 1, \quad p = 8q + 7,$$

то есть $p = 8q \pm 1$.

У праванении. Покажите, что — 2 есть квадратный вычет для $p = 8q + 1, \quad p = 8q + 3$.

Аналогично рассматривается случай $a = \pm 3$. Приведем итоги вычислений (таблица для $v$):

Рис. 3. $r = 1, a = 2, v = 0; r = 3, a = 2, v = 1; r = 5, a = 2, v = 1; r = 7, a = 2, v = 2$.

9

ность между вопросами о том, когда $p$ — квадратный вычет по модулю $q$ и когда $q$ — квадратный вычет по модулю $p$.

Доказательство. Всегда или $p-q=4a$ или $p+q=4a$.

I случай. Пусть $p-q=4a$, то есть $p$ и $q$ имеют одинаковые остатки при делении на 4. Тогда $\left(\frac{p}{q}\right) = \left(\frac{q+4a}{q}\right) = \left(\frac{4a}{q}\right) = \left(\frac{a}{q}\right)$ (мы воспользуемся (9), (8), и тем, что $\left(\frac{4}{q}\right) = 1$ при всех $q$). Далее, $\left(\frac{q}{p}\right) = \frac{p-4a}{p} = \left(\frac{-4a}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{a}{p}\right)$. В силу уже доказанной гипотезы Эйлера $\left(\frac{a}{p}\right) = \left(\frac{a}{q}\right)$, то есть $\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)$ при $\left(\frac{-1}{p}\right) = 1$, и $\frac{p}{q} = -\left(\frac{q}{p}\right)$ при $\left(\frac{-1}{p}\right) = -1$. Остается вспомнить, что $\left(\frac{-1}{p}\right) = 1$ при $p=4l+1$, $\left(\frac{-1}{p}\right) = -1$ при $p=4l+3$.

II случай. Пусть $p+q=4a$, то есть $p$ и $q$ имеют разные остатки при делении на 4. Имеем $\left(\frac{p}{q}\right) = \left(\frac{4a-q}{q}\right) = \left(\frac{a}{q}\right)$. Аналогично $\left(\frac{q}{p}\right) = \left(\frac{a}{p}\right)$. В силу дополнительки гипотезе Эйлера $\left(\frac{a}{q}\right) = \left(\frac{a}{p}\right)$, то есть $\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)$. Доказательство окончено.

Нетрудно заметить, что проведенные рассуждения можно обратить и вывести из квадратного закона взаимности гипотезу Эйлера и дополнительное к ней (проделяте это!). Отметим еще, что формулы (8)—(10) дают способ вычисления $\left(\frac{p}{q}\right)$ существенного более простой, чем описанный выше комбinatorный способ. Проиллюстрируем это на примере: $\left(\frac{59}{269}\right) = \left(\frac{269}{59}\right) = -1$,

так как
$\left(\frac{3}{59}\right) = -\left(\frac{59}{3}\right) = -\left(\frac{2}{3}\right) = 1$;
$\left(\frac{11}{59}\right) = -\left(\frac{59}{11}\right) = -\left(\frac{4}{11}\right) = -1$.

Легко показать, что вычисление символьла Лежандра всегда можно свести к случаю, когда $p$ или $q$ равно 2.

Упражнение. Сосчитайте $\left(\frac{37}{557}\right)$, $\left(\frac{43}{991}\right)$.

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