степень
где
мультипликативный порядок числа
по модулю
Таким образом, число различных неприводимых делителей многочлена
над
равно
По определению символа Лежандра число
делит
тогда и только тогда, когда
. Следовательно,
где
число неприводимых делителей многочлена
Дискриминант многочлена
выражается формулой
Теорема Штикельбергера 6.68 утверждает, что если многочлен
степени
является произведением
неприводимых множителей над
то
тогда и только тогда, когда
где через
обозначен дискриминант
Иными словами,
Если
где
простое нечетное число, то
Это соотношение позволяет выразить квадратичный вычет
через квадратичный вычет
Учитывая, что
получим:
Так как
то
Так как
Следовательно,
Это эквивалентно следующей теореме 6.73:
6.73. Теорема Гаусса о квадратичном законе взаимности. Если пир — различные нечетные простые числа, то
Приведенное выше доказательство принадлежит Суону [1962].
Закон взаимности квадратичных вычетов очень полезен при фактическом вычислении символов Лежандра.
6.74. Пример. Чему равны степени неприводимых делителей
над
Решение. Задача состоит в вычислении мультипликативного порядка числа 19 по модулю 257, что сводится к вычислению 19128 или (19/257). Используя закон взаимности, получаем, что