WikiSort.ru - Не сортированное

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

Определение

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

• ${\displaystyle \textstyle \left({\frac {a}{p}}\right)=0}$ , если a делится на p;
• ${\displaystyle \textstyle \left({\frac {a}{p}}\right)=1}$ , если a является квадратичным вычетом по модулю p (то есть существует такое целое x, что ${\displaystyle x^{2}\equiv a{\pmod {p}}}$ ) и a не делится на p;
• ${\displaystyle \textstyle \left({\frac {a}{p}}\right)=-1}$ , если a является квадратичным невычетом по модулю p.

Свойства

• Мультипликативность: ${\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)}$ . В частности,
  • Eсли ${\displaystyle a}$ не делится на ${\displaystyle p}$ , то ${\displaystyle \left({\frac {a^{2}}{p}}\right)=1.}$
  • Если ${\displaystyle a=p_{1}^{\alpha _{1}}\cdot p_{2}^{\alpha _{2}}\cdot \ldots \cdot p_{k}^{\alpha _{k}}}$ — каноническое разложение ${\displaystyle a}$ на простые сомножители, то

    ${\displaystyle \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}}}\cdots \left({\frac {p_{k}}{p}}\right)^{\alpha _{k}{\pmod {2}}}.}$

• Если ${\displaystyle a\equiv b{\pmod {p}}}$ , то

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

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

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

Если ${\displaystyle p\equiv q{\pmod {4\cdot a}}}$ тогда

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

• Среди чисел ${\displaystyle 1\leqslant a\leqslant p-1}$ ровно половина имеет символ Лежандра, равный +1, а другая половина — равный −1.
• Лемма Гаусса о квадратичных вычетах
• формула Эйлера

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

Литература

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