Карл Фридрих Гаусс

     Квадратичные  вычеты. Всюду ниже мы будем предполагать, что р = просто число, причем р≠2. Делить целые числа можно «с недостатком» или «с избытком». Иными словами, остатки можно считать положительными или отрицательными. Условимся выбирать остаток наименьшим по абсолютной величине.

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

                      

                        (1)

     где q и r - целые.

     

     Будем называть r остатком от деления n на р  или вычетом числа n по модулю р. Это  обозначается так: n r (mod p)

     Выпишем в таблицу 1 вычеты для нескольких первых простых чисел p>2. Нас интересует, какие вычеты (остатки) могут иметь  квадраты целых чисел. Эти остатки  мы будем называть квадратичными  вычетами, а остальные – квадратичными  невычетами.

     Числа n² и r², где r – остаток числа n по модулю р, имеютодин и тот же остаток при делении на р. Поэтому, если мы хотим найти квадратичные вычеты, то достаточно возводить в квадрат лишь вычеты, т.е. целые числа r,  IrI≤k = (p – 1)/2. При этом, разумеется, достаточно рассматривать r ≥ 0.

     Проведем  вычисления для простых чисел  из предыдущей таблицы. Составим новую  таблицу,в которой «жирые» числа  отвечают квадратными вычетам (табл.2).

     

     Попытаемся  подметить некоторые закономерности и оценить степень их общности. Во-первых, в каждой строке есть в  точности k + 1 жирное число. Покажем, что так обстоит дело для всех простых p>2. Из сказанного выше следует, что для каждого нечетного р (даже не простоого) квадратичных вычетов не больше  k + 1. Мы покажем, что их точно k + 1, если убедимся, что все числа r²(0≤r≤k) дают при делении на р различные остатки. Если r₁>r₂ и r₁² – r₂² дают одинаковые остатки, то r₁² – r₂² делится на р. Поскольку р – просто число, то r₁ + r₂  или r₁ - r₂  должно делиться на р, чего не может быть, так как 0< r₁ ± r₂ <2k<p. Здесь мы впервые воспользовались простотой р.

     Теорема Ферма и критерий Эйлера. Далее, очевидно, что 0 и 1 являются жирными во всех строчках. Что касается остальных столбуов, то сразу не видна закономерность, согласно которой в них появляются жирные числа. Начнем с а = – 1 . Оно является жирным при р = 5, 13, 17, … и не является при р = 3, 7, 11… Простые числа первой группы при делении на 4 дают остататок 1, а второй – остаток -1 (простые числа р≠2 других остатков вообще давать не могут). Итак,можно предположить,  что -1 является квадратичным вычетом для простых чисел вида р = 4l+1 и квадратичным невычетом для р = 4l – 1. Эту закономерность первым заметил Ферма, однако оставил ее без доказательства.

     Первое  доказательство после нескольких неудачных  попыток нашел в 1747 году Эйлер. В 1755 году Эйлер нашел другое, очень  изящное доказательство, использующее малую теорему Ферма: Если р –  просто число, то для всякого целого а, 0<IaI<p,

                                  а^р-1 (mod p).                                      (2)

     Доказательство. При р = 2 утверждение очевидно, и можно считать р нечетным. Рассмотрим р чисел 0, ±а, ±2а, ±3а, … , ±ka; k = (р – 1)/2. Все эти числа при делении на р дают разные остатки, так как в противном случае r₁a – r₂a, r₁> r₂, Ir₁I≤k, Ir₂I≤k, делится на р, так как 0<r₁ – r₂<p. Перемножим те из рассматриваемых чисел, которые отличны от нуля; получим (-1)^k(k!)²а^р-1. Поскольку среди остатков сомножителей содержатся все ненулевые вычеты и учитывая правило вычисления остатка произведения, получаем, что произведение имеет тот же вычет, что и (-1)^k(k!)², т.е. (k!)²(а^р-1 – 1) делится на р. Так как k! не делится на р(0<k<p), то на р делится а^р-1 – 1 и доказательство окончено.

     Следствие (критерий Эйлера квадратичности вычета). Вычет b≠0 является квадратичным тогда и только тогда, когда

                            b^k1 (mod p),                               (3)

     Доказательство . Необходимость условия (3) устанавливается легко. Если а²b(mod p), 0<a<p, то а^2k = a^p-1 и b^k! должны иметь одинаковые вычеты, равные, в силу (2), единице. Достаточность показывается сложнее. Выведем ее из следующей леммы.

     Лемма 1. Если Р(х) – многочлен степени l, р – простое число и имеется более l различных вычетов r  по модулю р, для которых

                                   P(r) 0 (mod p),                                     (4)

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

     Доказательство будем вести индукцией по l. При l = 0 утверждение очевидно. Пусть оно справедливо для многочленов степени не выше l – 1. Пусть далее r₀, r₁, … , r_l, 0≤r_j<p, удовлетворяют сравнению P(r) 0 (mod p). Представим Р(х) в виде Р(х) = (x – r₀)Q(x)+P(r₀), где Q(x) – многочлен степени l – 1, а P(r₀) делится на р. Тогда, поскольку P(r₀) делится на р, (r_j – r₀)Q(r_j) делится на р при 1≤j≤l. Так как r_j – r₀ не может делиться на р, то Q(r_j) делится на р, а тогда по предположению индукции Q(r) будет делится на р при всех r. Следовательно, P(r) делится на р при всех r.

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

     Замечание. Для квадратичного невычета b имеем: b^(p-1)/2 – 1(mod p). Действительно, если бы b^(p-1)/2 r(mod p), то r² 1(mod p), откуда r = – 1 (Сравнению r²1(mod p) удовлетворяют только два вычета: r1(mod p), r² -1(mod p).)

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

     Задача 1. Доказать, что если р≠2 есть простой делитель числа n²+1, то р = 4l+1.

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

     Это утверждение состоит из двух частей: отрицательное утверждение для p = 4l – 1 и положительное для p = 4l+1. В первом случае естественно пытаться найти некоторое свойство, которому квадратичные вычеты удовлетворяют, а -1 не удовлетворяет, что и сделал Эйлер. Найденное свойство оказалось характеристическим, т.е. одновременно удалось доказать и вторую часть гипотезы. Доказательство Эйлера не эффективно в том смысле, что оно не дает явной конструкции для числа n по р, а лишь утверждает его существование. Иными словами, гарантируется, что если перебирать числа 1, 2, … , 2l, возводить их в квадраты, брать остатки от деления квадратов на р, то рано или поздно получится -1. Остается открытым вопрос, нельзя ли указать более явную конструкцию N  и р, не использующую процедуры перебора. Положительный ответ дал Лагранж в 1774 году, используя следующую теорему.

     Теорема Вильсона. Если p = 2k+1 есть простое число, то

                         (-1)^k(k!)² -1 (mod p).                                                    (5)

     Для доказательства этой теоремы воспользуемся  леммой 1. Положим Р(х) = (х² - 1)(х² - 4)…(х² – k²), Q(x) = x^2k-1 – 1. Тогда R(x) = P(x) – Q(x) – многочлен степени не выше 2k – 1, который при x = ±1, ±2, …, ±k делится на р (этим свойством обладают P и Q). По лемме R(x)0 (mod p) для всех х. Собственно, новым фактом является лишь то, что R(0)0 (mod p). Поскольку R(0) = (-1)^k(k!)²+1? Получаем (5).

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

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

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

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

     Гипотеза  Эйлера. Число а одновременно является или квадратичным вычетом или квадратичным невычетом для всех простых чисел, входящих в арифметическую прогрессию 4aq+r, q = 0,1,2,…; 0<r<4a.

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

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

     Доказательство  Гаусса. Вначале Гаусс, как и его предшественники, замечает утверждение для а = -1, затем, уже угадав результат для общего случая, последовательно разбирает случай за случаем, продвинувшись дальше других: им рассмотрены а = ±2,±3,±5,±7. Общий случай (гипотеза Эйлера) не поддался первой атаке: «Эта теорема мучила меня целый год и не поддавалась напряженнейшим усилиям». Заметим, что это было то место, где Гаусс «догнал» современную математику: усилия крупнейших математиков, пытавшихся доказать гипотезу Эйлера, были безрезультатными.

     Наконец, 8 апреля 1796 г. он находит общее доказательство, которое Кронекер (1823 - 1891) очень метко  назвал «пробой сил гауссова гения». Доказательство проводится двойной  индукцией по а и р; Гауссу приходится придумывать существенно различные  соображения для рассмотрения восьми различных случаев. Нужно было иметь  не только поразительную изобретательность, но и удивительное мужество, чтобы  не остановится на этом пути. Позднее  Гаусс нашел еще шесть доказательств  «золотой» теоремы (ныне их известно около пятидесяти). Как это часто  бывает, после того как теорема  доказана, удается найти доказательства много более простые, чем первоначальное. Приведем доказательство, мало отличающееся от третьего доказательства Гаусса. В  его основе лежит ключевая лемма, доказанная Гауссом не ранее 1808 года.

     Лемма2.Пусть р = 2k+1 – простое число, а – целое число, 0<IaI≤2k; r₁, r₂, … , r_k – вычеты чисел а, 2а, … , ka; v – число отрицательных среди них. Тогда

                         a^k(-1)^v(mod p)                                                 (6)

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

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

     Доказательство  леммы 2. Заметим, что все вычеты r₁, … , r_k различны по  абсолютной величине. Это следует из того, что сумма и разность любых двух из них не делится на р: r_i±r_j=(i+j)a, i≠j; I i+j I<p, IaI<p. Таким образом, набор модулей Ir₁I, … , Ir_kI – это числа 1,2,…,k в некотором порядке. В результате а×2а … ka = a^kk! при делении на р дает тот же остаток, что и r₁, … , r_k = (-1)^vk!. Учитывая, что k! не делится на простое число р, получаем (6).

     Доказательство  гипотезы Эйлера. Заметим, что в приводимом рассуждении уже не используется простота р – она в полной мере использована в лемме Гаусса. Отметим на числовой оси точки (рис. 1, а, б) mp/2, если a>0, и –mp/2, если a<0; m=0,1,2,…,IaI. Занумеруем интервалы с концами в этих точках по номерам левых концов. Отметим теперь крестиками точки а, 2а, … , ka; так как а – целое число, неделящееся на р, то крестики не могут совпасть  с ранее отмеченными точками, причем все крестики попадут в какие-то из построенных интервалов (IaIp/2>IaIk). Легко заметить, что фигурирующее в лемме число v – это число крестиков, попавших в интервалы с нечетными номерами.

     

     Подвергнем  теперь нашу картинку преобразованию подобия с коэффициентом 1/а (рис. 1 перейдет в рис. 2).

     

     При этом точки mp/2 перейдут в точки, делящие отрезок [0, р/2] на IаI равных частей, а крестики – в целочисленные точки 1, 2, …, k.

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