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

Си́мвол Лежа́ндра, арифметическая функция чисел ${\displaystyle p}$ и ${\displaystyle a}$, определённая для простых нечётных ${\displaystyle p}$ и целых ${\displaystyle a}$, не делящихся на ${\displaystyle p}$. Символ Лежандра обозначается ${\displaystyle \left({\frac {a}{p}}\right)}$. Символ Лежандра ${\displaystyle \left({\frac {a}{p}}\right)=1}$, если сравнение ${\displaystyle x^{2}=a({\bmod {p}})}$ разрешимо; в противном же случае ${\displaystyle \left({\frac {a}{p}}\right)=-1}$. Иногда символы Лежандра доопределяют и для чисел ${\displaystyle a}$, делящихся на ${\displaystyle p}$, полагая, что в этом случае ${\displaystyle \left({\frac {a}{p}}\right)=0}$. Символ Лежандра обладает следующими свойствами:

1) если ${\displaystyle a\equiv b({\bmod {p}})}$, то ${\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}$;

2) ${\displaystyle \left({\frac {1}{p}}\right)=1}$;

3) ${\displaystyle \left({\frac {a}{p}}\right)\equiv a^{(p-1)/2}({\bmod {p}})}$;

4) ${\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)}$;

5) ${\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{(p-1)/2}}$;

6) ${\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\left(p^{2}-1\right)/8}}$;

7) если ${\displaystyle p}$ и ${\displaystyle q}$ – простые нечётные, то

${\displaystyle \left({\frac {q}{p}}\right)\left({\frac {p}{q}}\right)=(-1)^{(p-1)/2\cdot (q-1)/2}}$.

Последний факт, впервые доказанный К. Ф. Гауссом (1796), носит название квадратичного закона взаимности. Перечисленные свойства позволяют легко вычислять символы Лежандра, не прибегая к решению сравнений. Например,

${\displaystyle \left({\frac {438}{593}}\right)=\left({\frac {2}{593}}\right)\left({\frac {3}{593}}\right)\left({\frac {73}{593}}\right)=}$
${\displaystyle =+1\left({\frac {593}{3}}\right)\left({\frac {593}{73}}\right)=\left({\frac {2}{3}}\right)\left({\frac {9}{73}}\right)=-1\left({\frac {3}{73}}\right)^{2}=-1.}$

Ещё более облегчает вычисление символов Лежандра использование символа Якоби. При фиксированном ${\displaystyle p}$ символ Лежандра является действительным характером мультипликативной группы классов вычетов по модулю ${\displaystyle p}$.

Введён А.-М. Лежандром (1785).