яло в том, что N не должно иметь вид 4А; + 3. Указанное теперь условие сильнее, так как всякое число вида 4А; + 3 содержит хотя бы один простой множитель вида 4А; + 3 в нечетной степени.

Если отбросить числа, которые, согласно этому условию, заведомо не представили суммой двух квадратов, то ряд оставшихся чисел начинается с 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, ...; читатель путем последовательных проб может убедиться, что каждое из этих чисел представляется в виде суммы двух целых квадратов. Это верно и в обгцем случае: необходимое и достаточное условие представимости числа N в виде суммы двух квадратов состоит в том, что любой простой множитель N вида 4А; + 3 должен входить в N в четной степени.

Докажем теперь это утверждение. Важную роль в доказательстве играет тождество, представляюш;ее произведение двух сумм квадратов в виде суммы двух квадратов. Это тождество

(а + 6)(с + d) = {ac + bdf + {ad - bcf (1)

принадлежит Леонардо из города Пиза (Pisa) (его называют также Фибоначчи); он приводит это тождество в своей «Книге Абак» в 1202 году.

Любое число, удовлетворяюш;ее указанным выше условиям, состоит из множителей, равных 2, простых вида 4А; + 1 и квадратов простых вида + 3. Повторное применение тождества (1) показывает, что если каждый из таких сомножителей представляется в виде суммы двух квадратов, то и само число также представимо в виде суммы двух квадратов. Число 2 представимо в виде 1 + 1; если q есть простое вида Ак + 3, то {q представляется в виде д + 0. Остается доказать, что любое простое вида 4А; + 1 представимо в виде + у, этот результат мы установим в следуюш;ем пункте. Из него будет следовать, что вышеуказанное условие необходимо и достаточно для того, чтобы рассматриваемое число представлялось в виде суммы двух квадратов.

В нашем изложении допускаются представления х + у, в которых X и у могут иметь обгцие множители (например, q = = g + 0); но это не очень сугцественно: требование взаимной простоты X и у приводит к результату, мало отличаюгцемуся от предыдуш;его. Подробнее об этом будет говориться в (VI, 5),

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

2. Простые вида 4к + 1. Мы приведем здесь классическое доказательство того, что каждое простое р вида 4А; + 1 представимо как сумма двух квадратов; это доказательство принадлежит, по существу, Эйлеру. Оно состоит из двух шагов. Первый шаг заключается в установлении того, что некоторое кратное р представимо в виде z + 1; на втором шагу мы установим, что р представимо в виде + у.

Первый шаг эквивалентен доказательству разрешимости сравнения

+ 1 = 0 (mod р)

для любого простого р вида 4А; + 1. Мы уже знаем, что это так, из критерия Эйлера для квадратичных вычетов и невычетов (см. Ш, 3).

Второй шаг доказательства начинается с уже установленного факта, из которого следует, что существует такое натуральное т, для которого

тр = z + 1.

Мы можем, конечно, предполагать, что z лежит между - р и р (этого можно добиться, вычитая из Z подходящее кратное р). Предположив это, получаем

т =-<--< р.

Отсюда, в частности, следует, что существуют такие целые х и 2/, для которых выполняется равенство

тр = х + у\ (2)

где т - натуральное число, меньшее р. Покажем теперь, что если m > 1, то найдется такое натуральное т, меньшее т, для которого уравнение тр = х+у все еще разрешимо в целых х и у. Отсюда (если повторить это рассуждение несколько раз) будет следовать, что разрешимо уравнение р - х + у., в котором т - 1.

Рассуждения проводятся следующим образом. Определим два целых числа г/ и г;, лежащих между -\т и т (включи-

тельно, если т четное), которые сравнимы соответственно с х и у ио модулю т:

и = X (mod m); v = у (mod m). (3)

Тогда u + v = x + y = О (mod m), так что

mr = + (4)

для некоторого целого г. Заметим, что г не может быть равно О, так как тогда и и v были бы равны О, а потому х и у были бы кратны т; а это противоречит равенству (2), ибо отсюда и из (2) следует, что простое число р делится на т. Число г удовлетворяет неравенству

+ \rin? + \inn?

г =-<---- < т.

Перемножим равенства (2) и (4), применяя тождество (1). Это дает

тгр = (х + у){и + v) = {хи + yv) + {xv - yuf. (5)

Важно отметить, что каждое из чисел хи + yv и xv - уи делится на т. Действительно, ввиду сравнения (3) хи + yv = = + 2/ = О (mod т) и XV - уи = ху - ух = О (mod m). Следовательно, (5) можно разделить на т, что дает

гр = Х +

с некоторыми целыми X и¥. Тем самым мы доказали, что сугцествует такое натуральное число г, меньгпее т, для которого гр представимо в виде суммы двух квадратов.

Как мы уже говорили, этого достаточно, чтобы доказать представимость гр в виде суммы двух квадратов. Проиллюстрируем это доказательство на численном примере. Возьмем р = 277 - это простое вида 4А; + 1. Мы знаем, что сравнение 1 + z = О (mod 277) разрешимо и его решение легко найти подбором или с помош;ью таблицы индексов. Число 2; = 60 является решением этого сравнения:

60 + 1 = 3601 = 277 • 13.

Исходным пунктом доказательства, как и в обгцем случае, служит равенство 13 • 277 = 60 +1. Следуя плану доказательства, приводим числа 60 и 1 по модулю 13; получим числа -5 и 1.