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

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

Определение

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

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

Свойства

• Мультипликативность: $\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 \dots \cdot p_k^{{\alpha }_k}$ — каноническое разложение $a$ на простые множители, то

    $\left(\frac{a}{p}\right)={\left(\frac{p_1}{p}\right)}^{{\alpha }_1(\mathrm{mod}2)}\cdot {\left(\frac{p_2}{p}\right)}^{{\alpha }_2(\mathrm{mod}2)}\cdot \dots \cdot {\left(\frac{p_k}{p}\right)}^{{\alpha }_k(\mathrm{mod}2)}$.

• Если $a\equiv b(\mathrm{mod}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}(\mathrm{mod}p).$

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

$\left(\frac{-1}{p}\right)=(-1{)}^{(p-1)/2}$ (частный случай критерия Эйлера);

$\left(\frac{2}{p}\right)=(-1{)}^{(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(\mathrm{mod}4\cdot a)$, то

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

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

Литература

• Шаблон:Книга

Шаблон:Характеры