книги из ГПНТБ / Чандрасекхаран, К. Введение в аналитическую теорию чисел

ГЛАВА IV

КВАДРАТИЧНЫЕ ВЫЧЕТЫ И ПРЕДСТАВЛЕНИЕ ЧИСЕЛ

ВВИДЕ СУММЫ ЧЕТЫРЕХ КВАДРАТОВ

§1 . Символ Лежандра. Теория квадратичных выче­

тов является одним из основных разделов теории чисел. С ее помощью, например, можно доказать такие эле­ гантные результаты, как теорему Эйлера о том, что каж­ дое простое число вида 4&+1 представляется в виде сум­ мы двух квадратов, и теорему Лагранжа о том, что каж­ дое положительное целое число представляется в виде суммы четырех квадратов.

Пусть р — нечетное простое число и а — целое число, причем (а, р) = 1. Если существует такое целое число х,

что x2 = a (m o d p ), то а называется квадратичным выче­

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

Мы иногда будем использовать запись aRp для обо­ значения того, что а — квадратичный вычет по модулю р, и aNp для обозначения того, что а — квадратичный невычет по модулю р. Чтобы выяснить, сколько чисел из

Все они попарно не сравнимы по mod р. Действительно, если мы возьмем любые два из этих чисел, скажем г2

что целое число а принимает в сравнении ( 1 ) в точности (р— 1 ) / 2 различных значений, когда х пробегает множе-

Удобно расширить определение символа Лежандра, по­ ложив

— j = 0 , если р |т.

Поскольку имеется столько же квадратичных невыче­ тов, сколько и квадратичных вычетов, мы имеем

р— 1

Далее, если /n1 = m2 (modp), то

§ 2. Теорема Вильсона и критерий Эйлера. Следую­ щий результат, известный под названием теоремы Виль­ сона, но впервые доказанный Лагранжей, выражает характеристическое свойство простых чисел:

и притом единственный, элемент х' из того же самого множества, такой, что

42 Гл. IV. Квадратичные вычеты

= р — 1. Действительно, сравнение x2 = l(m o d p ) эквива­ лентно сравнению (х— 1 ) (х-\-l)= = 0 (modp), так что или

Тем самым теорема Вильсона доказана.

Предположим теперь, что число р составное. Тогда его можно представить в виде p = q r, 1 < р < р . Следова­ тельно, q будет входить в качестве сомножителя в произ­ ведение 1 - 2 -3 ...{р— 1 ), и сравнение

(р— 1 ) !+ 1 = 0 (mod q)

в этом случае не разрешимо. Тем более не будет разре­ шимым и сравнение (р— l)! + l = 0(m odp). Таким обра­ зом, теорема Вильсона устанавливает характеристиче­ ское свойство простых чисел.

Пусть теперь р — нечетное простое число и (а, р) = ■=1. Покажем, что если а — квадратичный вычет по мо­ дулю р, то

а (р_1)/2_ 1 (m od р ).

Но по теореме Ферма (теорема 3 гл. II) мы знаем, что jcp _ 1 = 1 (modр ). Следовательно, а(г>-')/2 = i (modp).

С другой стороны, по теореме Лагранжа (теорема 7 гл. II) сравнение

£(p- i)/2 == 1 (mod р)

может иметь не более чем (р— 1) /2 решений. Но в § 1 мы показали, что имеется в точности (р— 1 ) / 2 квадратич­

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

Теорема 2 (критерий Эйлера). Пусть р — нечетное

простое число и а — любое целое. Сравнение

a(p-i)/2 = 1 (mod р)

справедливо тогда и только тогда, когда а является квад­ ратичным вычетом по модулю р.

и так как по теореме 2 квадратичные невычеты не удов­

летворяют сравнению (5), они должны удовлетворять сравнению (6 ). Вспоминая определение символа Ле­

жандра, мы получаем отсюда следующую теорему:

Теорема 3. Если р — нечетное, простое число, то

Следствие. Имеет место равенство

которое означает, что произведение двух квадратичных

вычетов или невычетов по модулю р является квадра­

тичным вычетом, а произведение квадратичного вычета

и квадратичного невычета по модулю р есть квадратич­ ный невычет по модулю р.

§ 3. Суммы двух квадратов. Пусть р — нечетное про­ стое число, и пусть т = р — 1. Так как р— 1 = — 1 (mod р), то мы получим по теореме 3

( -у -) = ( — 1 )(P_I) / 2 (mod р).

тельно,

( ^ ) = ( - l ) ' ' - ' ’'2,

откуда следует, что — 1 есть квадратичный вычет по mod р для всех простых р = 1 (mod 4) и квадратичный не­ вычет по modр для всех простых p= 3(m od4). Это при­ водит нас к следующей теореме:

Теорема 4 (Эйлер). Каждое простое число вида

4й +1 можно представить в виде суммы двух квадратов.

Доказательство. Если р — простое число вида 4&+1, то — 1 является квадратичным вычетом по модулю р,

т. е. сравнение х2= — 1 (mod р) разрешимо. Следователь­ но, существует целое число Л, такое, что р| (Л2 н-1 ). По

теореме 5 гл. III отсюда следует, что р является суммой двух квадратов.

Результат о том, что для простого числа р вида 4&+1 мы имеем р| (Л2 + 1 ) при некотором Л, может быть уточ­

нен следующим образом:

Следующий результат аналогичен результату теоре­

мы 5.

Теорема 6 . Если р — нечетное простое число, то су­

ществуют целые х и у, такие, что

1 + х2 + у2 = тр, где 0 < .т < .р.

Доказательство. Целые х2, 0 ^ х ^ ( р — 1)/2, попарно не сравнимы по mod р. То же самое справедливо для це­ лых — 1—у2, Os^ys^(p— 1)/2. Но эти два множества вместе содержат р+ 1 целых чисел, и так как имеется

только р классов вычетов по mod р, некоторый член х2 первого множества должен быть сравним с некоторым членом — 1—у2 второго множества. Таким образом,

х 25= — 1— г/2 (mod/?),

или

1 + х 2 + у2= т р .

Но О ^ х, у ^ ( р — 1)/2. Следовательно,

l- fx 2+r/2< l+ 2 ( _ I- p ) 2< /?2,

и тогда

1 -\-х2-\-у2 — тр, 0 < т < /> .

Теорема доказана.

Мы видели, что каждое простое число вида 4&+1 представимо в виде суммы двух квадратов. Но другие числа также обладают этим свойством, например 1 0 = = 12 -г32. Следующая теорема дает необходимое и доста­

точное условие представимости положительного целого числа в виде суммы двух квадратов:

Теорема 7. Положительное целое число п можно

представить в виде суммы двух квадратов тогда и толь­ ко тогда, когда все простые сомножители вида 4&+3

входят в каноническое разложение этого числа с четны­

ми показателями.

Докажем предварительно две леммы. Мы назовем представление п — х2-\-у2 примитивным, если (х, у) = 1 ,

и непримитивным в противном случае.

46 Г л. IV. Квадратичные вычеты

Лемма 1. Если п делится на простое число р, где p s s s 3 (mod4 ), то п не имеет примитивных представлений.

Доказательство. Если п имеет примитивное пред­ ставление, скажем

п — х2-\-у2, (х,у) = 1 ,

то р |(х2 +г/2), но р->(х и p'f у. Так как (р,х) = 1, то урав­

Тогда р\х2(т2+ 1 ), и так как р\х, то р |(т2+ \ ). Таким

образом, т2= — l(m odp). Другими словами, —] есть квадратичный вычет по простому модулю р вида hk-\-3, но, как было выяснено в начале § 3, это невозможно. Тем самым лемма доказана.

Лемма 2 . Если р — простое число, p = 3 (m o d 4 ),

и с — нечетное целое, такое, что рс \п, но pc+I ^ п, то п не может быть представлено в виде суммы двух квадратов.

s=3(m od4). Но это противоречит утверждению леммы 1 и доказывает лемму 2 .

Доказательство теоремы 7. Условия теоремы необхо­ димы. Действительно, из леммы 2 следует, что если п представимо в виде суммы двух квадратов, то каждый простой делитель числа п вида 4&+3 должен иметь чет­ ный показатель степени в каноническом разложении п.

Условия теоремы являются также и достаточными. Действительно, если п — положительное целое, такое,

что каждое простое вида 4&+3 входит в каноническое разложение этого числа с четным показателем, то п мож­

но записать в виде п = п \ п 2, где п2 не имеет простых де­ лителей вида 4&+3. Следовательно, простыми делителя­ ми числа п2 являются только простые числа вида 4&+1

или число 2. Но 2 представимо в виде суммы двух квад­ ратов: 12 + 1 2, и каждое простое вида 4& + 1 также можно

представить в таком виде. Далее, из тождества

( * ? + 0 ? X * 2 + 0 f ) = ( * l* H - « / l« / 2 ) 2 + ( * I # 2 — * 2 i/ l ) 2

следует, что произведение двух чисел, представимых в виде суммы двух квадратов, также имеет такое пред­ ставление. Таким образом, п2 = а 2 + й 2, откуда п —

=(nia)2 + (n ib )2.

§4. Суммы четырех квадратов. В заключении этой главы мы докажем хорошо известный и элегантный ре­ зультат:

Теорема 8 (Лагранж). Каждое положительное целое

число п является суммой четырех квадратов.

где

^1 =Х\У\-\~Х2у2-\-Хъу2-\-Х4у4, z2= Х\у2— х2у\-\-х2у4— х 4г/3, z 3— МУз— хзУ1 -\-х4у2— х2у4,

■ 2ь= Х\У4— Х4у^-\-Х2у2— Х2у2,

следует, что произведение двух целых чисел, представи­ мых суммой четырех квадратов, также можно предста­

что каждое нечетное простое представляется в виде сум­ мы четырех квадратов.

Из теоремы 6 следует, что если р — нечетное простое

число, то существует целое m<ip, такое, что

mp = х* + х\ + х\ + х\,

где не каждое хи х2, х3, х4 делится на р.

Для данного нечетного простого числа р обозначим через т0 наименьшее положительное целое число, такое, что

должно быть нечетным. Действительно, если тй четное, то Х\, х2, Хз, х4 или все четные, или все нечетные, или

мы видим, что (тор)/2 является суммой четырех целых

квадратов, не все из которых делятся на р. Но это про­ тиворечит минимальности т0.

В таком случае т0^ 3 и мы можем записать, что

причем целые bi можно выбрать таким образом, чтобы \yi \< т 0/2. Действительно, если при делении Xi на не­ четное число т0 мы получим Xi— bim0-)-yi, где yt > т 0/2 ,

то мы можем записать, что

Xi=(b'i +l)m o+(y'i—m0) = b im Q-\-yu

где —т 0 /2 < г / ,< 0 .

Далее, не все х\, х2, х3, х4 делятся на т0. Действи­ тельно, если бы все Х\, х2, х3, х4 делились на то, то мы имели бы т0\р, что невозможно, так как 1 < т 0 < р . Сле­

довательно,

У\ + У2 + Уз + У 4> 0,

и мы имеем