PROFILPELAJAR.COM

Символ Лежандра — функция, используемая в теории чисел. Введён французским математиком А. М. Лежандром. Символ Лежандра является частным случаем символа Якоби, который, в свою очередь, является частным случаем символа Кронекера — Якоби, который иногда называют символом Лежандра — Якоби — Кронекера.

Определение

Пусть $a$ — целое число, и $p\neq 2$ — простое число. Символ Лежандра $\textstyle \left({\frac {a}{p}}\right)$ определяется следующим образом:

$\textstyle \left({\frac {a}{p}}\right)=0$ , если $a$ делится на $p;$
$\textstyle \left({\frac {a}{p}}\right)=1$ , если $a$ является квадратичным вычетом по модулю $p$ , но при этом $a$ не делится на $p;$
$\textstyle \left({\frac {a}{p}}\right)=-1$ , если $a$ является квадратичным невычетом по модулю $p.$

Свойства

Мультипликативность: $\left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)$ $\left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)$ . Очевидными свойствами мультипликативности являются также следующие:
- если $a$ не делится на $p$ , то $\left({\frac {a^{2}}{p}}\right)=1;$
- если $a=p_{1}^{\alpha _{1}}\cdot p_{2}^{\alpha _{2}}\cdot \ldots \cdot p_{k}^{\alpha _{k}}$ — каноническое разложение $a$ на простые множители, то
  $\left({\frac {a}{p}}\right)=\left({\frac {p_{1}}{p}}\right)^{\alpha _{1}{\pmod {2}}}\cdot \left({\frac {p_{2}}{p}}\right)^{\alpha _{2}{\pmod {2}}}\cdot \ldots \cdot \left({\frac {p_{k}}{p}}\right)^{\alpha _{k}{\pmod {2}}}$ .
Если $a\equiv b{\pmod {p}}$ , то
$\left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)$ .
$\left({\frac {1}{p}}\right)=1$ .
Лемма Гаусса о квадратичных вычетах.
Критерий Эйлера:

\left({\frac {a}{p}}\right)\equiv a^{(p-1)/2}{\pmod {p}}.

Если $p\neq 2$ , то:

\left({\frac {-1}{p}}\right)=(-1)^{(p-1)/2}

(частный случай критерия Эйлера);

\left({\frac {2}{p}}\right)=(-1)^{(p^{2}-1)/8}.

Доказательство

Если $x<{\frac {p}{2}}$ и $x$ нечётно, то $p-x>{\frac {p}{2}}$ , причём $p-x$ чётно, и наоборот. Поэтому

$1\cdot 2\cdot 3\cdot 4\cdot \ldots \cdot {\frac {p-1}{2}}=$

$=(-(-1))\cdot 2\cdot (-(-3))\cdot 4\cdot \ldots \cdot \left({\pm \left({\pm {\frac {p-1}{2}}}\right)}\right)\equiv$

$\equiv (-{\color {blue}{(p-1)}})\cdot {\color {red}{2}}\cdot (-{\color {blue}{(p-3)}})\cdot {\color {red}{4}}\cdot \ldots \cdot \left({\pm \left({\pm {\frac {p-1}{2}}}\right)}\right){\pmod {p}}\ ,$

где в последнем произведении числа под знаками чётны, причём встречаются все чётные числа. Таким образом, обозначая $s={\frac {p-1}{2}}$ , имеем

$s!=1\cdot 2\cdot 3\cdot 4\cdot \ldots \cdot {\frac {p-1}{2}}\equiv$

$\equiv (-1)^{\lfloor {(s+1)/2}\rfloor }\cdot {\color {red}{2}}\cdot {\color {red}{4}}\cdot \ldots \cdot {\color {blue}{(p-3)}}\cdot {\color {blue}{(p-1)}}=(-1)^{\lfloor {(s+1)/2}\rfloor }\cdot 2^{s}(s!){\pmod {p}}$

Поэтому $2^{s}\equiv (-1)^{\lfloor {(s+1)/2}\rfloor }=(-1)^{\frac {s(s+1)}{2}}=(-1)^{\frac {p^{2}-1}{8}}$ , что, по критерию Эйлера, доказывает утверждение.

Квадратичный закон взаимности: Пусть p и q — неравные нечетные простые числа, тогда
$\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}\cdot \left({\frac {p}{q}}\right).$
Если $p\equiv q{\pmod {4\cdot a}}$ , то

\left({\frac {a}{p}}\right)=\left({\frac {a}{q}}\right)

.

При $p\neq 2$ среди чисел $1\leqslant a\leqslant p-1$ ровно половина имеет символ Лежандра, равный 1, а другая половина — равный −1.

Литература

Виноградов И. М. Основы теории чисел. — Москва: ГИТТЛ, 1952. — С. 180. — ISBN 5-93972-252-0.