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

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

Определение

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

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

Свойства

• Мультипликативность: <math>\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)</math>. Очевидными свойствами мультипликативности являются также следующие:
  • если <math>a</math> не делится на <math>p</math>, то <math>\left(\frac{a^2}{p}\right) = 1;</math>
  • если <math>a = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}</math> — каноническое разложение <math>a</math> на простые множители, то

    <math>\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}</math>.

• Если <math>a\equiv b\pmod p</math>, то

  <math>\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)</math>.

• <math>\left(\frac{1}{p}\right)=1</math>.
• Лемма Гаусса о квадратичных вычетах.
• Критерий Эйлера:

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

• Если <math>p\ne2</math>, то:

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

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

{{Hider|

 title = Доказательство|
 hidden = 1 |
 title-style = text-align: left; |
 content-style = text-align: left; |
 content =

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

<math>1 \cdot 2 \cdot 3 \cdot 4 \cdot \ldots \cdot \frac{p-1}{2} = </math>

<math>= (-(-1)) \cdot 2 \cdot (-(-3)) \cdot 4 \cdot \ldots \cdot \left({ \pm \left({ \pm \frac{p-1}{2} }\right) }\right) \equiv</math>

<math>\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\ ,</math>

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

<math>s! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot \ldots \cdot \frac{p-1}{2} \equiv</math>

<math>\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</math>

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

• Квадратичный закон взаимности: Пусть p и q — неравные нечетные простые числа, тогда

  <math>\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\cdot\left(\frac{p}{q}\right).</math>

• Если <math>p\equiv q\pmod{4\cdot a}</math>, то

<math>\left(\frac{a}{p}\right)=\left(\frac{a}{q}\right)</math>.

• При <math>p\ne2</math> среди чисел <math>1\leqslant a\leqslant p-1</math> ровно половина имеет символ Лежандра, равный 1, а другая половина — равный −1.

Литература

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

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