Символ Лежандра и его свойства
Пусть целое а не кратно р.
Символом Лежандра называется а по р определяется равенствами
а _ (+1, если а — квадратичный вычет по модулю р р ~ ( — 1, если квадратичный невычет по модулю р
Если а кратно р, то символ Лежандра равен нулю.
Символ Лежандра дает ответ на вопрос: при каких а простейшее двучленное сравнение второй степени имеет решение.
Теорема 2.59 (критерий Эйлера).
Пусть целое а не кратно натуральному р.
Тогда
|
а 2 = (mod р) |
(2.241) |
|
Доказательство. Используем теорему Ферма, |
|
|
ар-1 = {(mod р) |
(2.242) |
|
Преобразуем (2.242): |
|
|
ар-1 — 1 = 0(mod р) |
(2.243) |
|
(а~ — 1) (а~ + 1) = Ofmod р) |
(2.244) |
В левой части сравнения (2.244) одно из сомножителей кратен р. Это действительно так поскольку если оба сомножителя были бы кратны р, то
|
тогда и их разность должна была бы быть кратно р, но Р-2 p-і (а і - 1) - (а 2 + 1) = 2 Но 2 кратно р, следовательно, либо p-і а 2 = l(mod р), либо p-і а 2 = —l(modp). |
|
Но всякий квадратный вычет, а удовлетворяет некоторому сравнению
|
а = x2(mod р) /а ?zl = а 2 (m°d Р) “ Ф°РмУла Эйлера |
(2.248) |
Из всего сказанного выделим свойства символа Лежандра.
Свойства символа Лежандра 1.
Если а = b(mod р), то
- 2.
- 3.
- 1;
р± = (—1) 2
- 4.
- 5.
,2
- 1;
- 6.
Pz~l
— 1 8
Теорема 2.60 Гаусса {квадратичный закон взаимности)
Если р и q — не четные простые, то справедливо:
р-1 q-l = (-1) 2 2
- -У р)
- (2.249)
Например, используя квадратичный закон вычислим символ Лежандра /198
U00/
/198 / 94
Решение. Так как 195 = 94(mod 101), то имеем ---I = I — .
юо7 юо7
Далее, 94 = 2-47, следовательно, используем свойство 4; и далее свойства 6 и 1:
/94 / 2 /47 /101
—- = 7777 ? 7777 = (-1) • 777 = I101 = ~7^ГПО(1 47)| 1007 1017 1017 v 47 7
/101 /47 / 2
= 71) ? Нт = V = I47 = ~2(mod 7)| = --
4 / / / / / /
Символ Якоби
Символ Якоби является обобщающим символа Лежандра для т -любого составного нечетного числа.
Рассмотрим любое нечетное положительное число т. Разложим это число на простые множители:
т = Pi>P2> ->Ps (2.250)
Поскольку в записи не использованы степени, то это означает, что среди pi, і = і — s могут оказаться одинаковые числа.
Символ Якоби определяется как произведение символов Лежандра:
(-) = (Л) . (.1) . ... . (2.251)
mj pj p2J psJ
Перечисленные свойства символа Лежандра 1 - 6, а также квадратичный закон взаимности справедливы также и для символа Якоби.
