Символ Лежандра

В п. 3.1.9 мы изучали сравнение ax º b(modm). Рассмотрим сравнение ax²+bх+ с º 0 (mod m). Путем выделения квадрата приведем его к виду (2ах + b)² = b²– 4ас (mod 4am). Полагая у = 2ax + b, d = b²– 4ас, имеем сравне­ние у²ºd(mod4am). Фактически исходное сравнение сведено к сравнению вида х²ºа(mod m). Рассмотрим случай, когда т – простое.

Пусть р – нечетное простое число, (а,р)=1. Символ Лежандра определяется равенством =1, если сравнение х² º a(mod р) разрешимо, и = –1 в противном случае. Говорят также, что в первом случае а является квадратичным вычетом по модулю р и квадратичным невычетом во втором.

Таким образом, = ±1.

Пример. Квадратичные вычеты по mod 7 – это 1, 2, 4: невычеты – 3, 5, 6. Если g – первообразный корень по mod p, то каждое целое g^2k – квадратичный вычет, а каждое g^2k+1 – квадратичный невычет.

Свойство 1. = ,где (а,р)=(b,р) =1.

Теорема 1 (критерии Эйлера). Если (а,р)=1, то

Свойство 2.