3. Квадратические вычеты.
Обращаясь снова к примерам, иллюстрирующим теорему Ферма, мы можем подметить, что не только всегда справедливо сравнение 
но (предположим, что 
есть простое число, отличное от 2, значит, — нечетное, 
при некоторых значениях а справедливо также сравнение 
Это обстоятельство вызывает ряд заслуживающих внимания соображений. Теорему Ферма можно записать в следующем виде:
Так как произведение делится на 
только в том случае, если один из множителей делится на 
то, значит, одно из чисел 
или 
должно делиться на 
поэтому, каково бы ни было простое число 
и каково бы ни было число а, не делящееся на 
непременно должно иметь место одно из двух сравнений:
Начиная с самого возникновения современной теории чисел, математики были заинтересованы выяснением вопроса: для каких чисел а оправдывается первое сравнение, а для каких — второе? Предположим, что а сравнимо по модулю 
с квадратом некоторого числа х,
Тогда 
и согласно теореме Ферма правая, а следовательно, и левая части сравнения должны быть сравнимы с 1 по модулю 
Такое число а (не являющееся кратным 
которое по модулю 
сравнимо с квадратом некоторого числа, называется квадратическим вычетом 
напротив, число 
не кратное 
которое не сравнимо ни с каким квадратом по модулю 
называется квадратическим невычетом 
Мы только что видели, что всякий квадратический вычет а числа 
удовлетворяет сравнению 
Довольно легко установить,
что всякий невычет 
числа 
удовлетворяет сравнению 
Кроме того, мы покажем (несколько дальше), что среди чисел 
имеется в точности — квадратических вычетов 
и — невычетов.
Хотя с помощью прямых подсчетов можно было собрать немало эмпирических данных, но открыть сразу общие законы, регулирующие распределение квадратических вычетов, было нелегко. Первое глубоко лежащее свойство этих вычетов было подмечено Лежандром (1752-1833); позднее Гаусс назвал его законом взаимности. Этот закон касается взаимоотношения между двумя различными простыми числами 
Он заключается в следующем:
1) Предположим, что произведение 
четное. Тогда 
есть вычет 
в том и только в том случае, если 
есть вычет 
2) Предположим, напротив, что указанное произведение — нечетное. Тогда ситуация резко меняется: 
есть вычет 
если 
есть невычет 
и наоборот.
Первое строгое доказательство закона взаимности, долгое время остававшегося гипотезой, данное Гауссом еще в молодости, явилось одним из крупных его достижений. Доказательство Гаусса никоим образом нельзя назвать простым, и в наше время провести доказательство закона взаимности стоит известного труда, хотя количество различных опубликованных доказательств очень велико. Истинный смысл закона взаимности вскрылся лишь в недавнее время — в связи с новейшим развитием алгебраической теории чисел.
В качестве примера, иллюстрирующего распределение квадратических вычетов, возьмем 
Так как по модулю
и так как дальнейшие квадраты повторяют эту последовательность, то квадратическими вычетами числа 7 являются числа, сравнимые с 1, 2 и 4, а невычетами — числа, сравнимые с 3, 5 и 6. В общем случае квадратические вычеты 
составляются из чисел, сравнимых с числами 
Но эти последние попарно сравнимы, так как
Действительно, 
Значит, половина чисел 
представляет собою квадратические вычеты числа 
а другая половина — невычеты.
Чтобы дать иллюстрацию также и закону взаимности, положим 
Так как 
то 11 есть квадратический вычет по модулю 5, и так как, кроме того, произведение 
четное, то, согласно закону взаимности, 5 должно быть также квадратическим вычетом по модулю 11; и в самом деле, мы видим, что 
. С другой стороны, положим 
Тогда произведение 
и в этом случае 11 есть вычет по модулю 7 (так как 
невычет по модулю 11.
Упражнения.
(см. скан)
