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

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

Определение

Пусть a — целое число, и p — нечётное простое число. Символ Лежандра $\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 и существует такое целое x, что $x^2\equiv a\pmod p$;
• $\textstyle\left(\frac{a}{p}\right)=-1$, если a является квадратичным невычетом по модулю p, то есть a не делится на p и не является квадратичным вычетом по модулю p.

Свойства

• Мультипликативность: $\textstyle \left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$.
• Если $a\equiv b\pmod p$, то $\textstyle \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$.
• $\textstyle \left(\frac{1}{p}\right)=1.$
• $\textstyle \left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}.$
• $\textstyle \left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}.$
• Если q — простое число, не равное p, то $\textstyle \left(\frac{q}{p}\right)\cdot\left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$ — частный случай квадратичного закона взаимности.
• Среди чисел $\textstyle 1\leqslant a\leqslant p-1$ ровно половина имеет символ Лежандра, равный +1, а другая половина — равный −1.
• Символ Лежандра можно вычислить по формуле Эйлера: $\textstyle \left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod p$.

Ссылки

• Weisstein, Eric W. Legendre Symbol (англ.) на сайте Wolfram MathWorld.