6.7. Квадратичный закон взаимности

Для произвольного числа а и простого числа можно определить символ Лежандра следующим образом:

6.71. Определение.

Символ Лежандра возникает в приложениях теоремы Штикельбергера для определения мультипликативного порядка числа а по модулю при определении степеней неприводимых множителей многочлена над при изучении кодов, задаваемых квадратичными вычетами (разд. 15.2) и во многих других вопросах теории чисел. Если уравнение имеет ненулевое решение в то а называется квадратичным вычетом по модулю а если ненулевых решений нет, а — квадратичный невычет.

Если — квадратичый невычет, то многочлен а неприводим над если — квадратичный вычет, то разлагается над . В любом случае Элемент У а лежит в подполе тогда и только тогда, когда Так как и все корни уравнения исчерпываются числами то Следовательно,

Это сравнение носит название критерия Эйлера.

Легко доказываются леммы

6.721. Лемма,

6.722. Лемма.

6.723. Лемма.

6.724. Лемма.

Доказательство леммы 6.724 следует непосредственно из теоремы 6.54.

Рассмотрим теперь разложение многочлена над предполагая, что пир — различные нечетные простые числа. Мы уже знаем, что При этом каждый неприводимый делитель многочлена над имеет

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

Дискриминант многочлена выражается формулой Теорема Штикельбергера 6.68 утверждает, что если многочлен степени является произведением неприводимых множителей над то тогда и только тогда, когда где через обозначен дискриминант Иными словами,

Если где простое нечетное число, то

Это соотношение позволяет выразить квадратичный вычет через квадратичный вычет Учитывая, что получим:

Так как то Так как Следовательно,

Это эквивалентно следующей теореме 6.73:

6.73. Теорема Гаусса о квадратичном законе взаимности. Если пир — различные нечетные простые числа, то

Приведенное выше доказательство принадлежит Суону [1962].

Закон взаимности квадратичных вычетов очень полезен при фактическом вычислении символов Лежандра.

6.74. Пример. Чему равны степени неприводимых делителей над

Решение. Задача состоит в вычислении мультипликативного порядка числа 19 по модулю 257, что сводится к вычислению 19128 или (19/257). Используя закон взаимности, получаем, что

Так как то Так как порядок числа 19 по делит 256 и не делит 128, то он равен 256. Следовательно, многочлен неприводим над

Другие факты о квадратичном законе взаимности можно найти в книгах по теории чисел, в частности в книгах Маккоя [1965] и Нэджела [1951].

Задачи

(см. скан)

(см. скан)