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

Символом Лежандра називається мультиплікативна функція, що використовується в теорії чисел. Названа на честь французького математика Адрієна-Марі Лежандра.

Визначення

Нехай a деяке ціле число і p просте число. Символ Лежандра $\left(\frac{a}{p}\right)$ визначається таким чином:

• $\left(\frac{a}{p}\right)=0$, якщо $a$ ділиться на $p$.
• $\left(\frac{a}{p}\right)=1$, якщо $a$ є квадратичним лишком за модулем $p$, тобто існує таке ціле $x$, що $x^2\equiv a(\mathrm{mod}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\equiv b(\mathrm{mod}p)$, то $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$
• $\left(\frac{1}{p}\right)=1$
• $\left(\frac{-1}{p}\right)=(-1{)}^{(p-1)/2},$ перший додатковий закон (Шаблон:Lang-en)
• $\left(\frac{2}{p}\right)=(-1{)}^{(p^2-1)/8},$ другий додатковий закон (Шаблон:Lang-en)

Доведення

Нехай $s=\frac{p-1}{2}$, і розглянемо $s$ рівнянь

$\begin{array}{cc}1& =(-1)(-1)\\ 2& =2(-1{)}^2\\ 3& =(-3)(-1{)}^3\\ 4& =4(-1{)}^4\\ & \dots \\ s& =(\pm s)(-1{)}^s\end{array}$

Тут ми обираємо знак так, щоб мати правильний знак результату.

Зараз множимо $s$ рівнянь разом. Ліворуч отримуємо $s!$. Праворуч, маємо $2,4,6,\dots$ і якісь від'ємні непарні числа. Але зауважимо, що $2(s)\equiv -1modp$, $2(s-1)\equiv -3modp$, і т.д., отже, ці від'ємні числа є іншими парними числами за модулем $p$, але прихованими. Отже права частина становить $s!(2^s)$ (кожна двійка парна до одного з членів факторіалу, щоб представити парні числа за модулем $p$).

Залишилось лише зауважити, що $(-1{)}^{1+2+\dots +s}=(-1{)}^{s(s+1)/2}$ і перенести в ліву частину.

Збираючи все до купи, ми отримуємо $2^{s}s!\equiv s!(-1{)}^{s(s+1)/2}modp$, або по скороченні факторіалів $2^s\equiv (-1{)}^{s(s+1)/2}$. І $s(s+1)/2=(p^2-1)/8$, отже ми насправді маємо $2^{(p-1)/2}\equiv (-1{)}^{(p^2-1)/8}$.

• Якщо $q$ — просте число, не рівне $p$, то $\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1{)}^{\frac{p-1}{2}\cdot \frac{q-1}{2}}$ — частковий випадок квадратичного закону взаємності.
• Серед чисел $1\le a\le p-1$ рівно половина має символ Лежандра, рівний +1, а інша половина — –1.
• Символ Лежандра при $p>2$ можна обчислити за допомогою критерію Ейлера: $\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}(\mathrm{mod}p)$

Обчислення

Безпосереднє застосування критерію Ейлера для обчислення символу Лежандра потребує піднесення до степеня, що для великих значень $a$ і $p$ є доволі складним (зокрема, доводиться застосувати довгу арифметику) та вельми трудомістким. Набагато ефективніше обчислювати символи Лежандра через їх узагальнення — символи ЯкобіШаблон:Sfn. Шаблон:Main

Приклад

$\left(\frac{12345}{331}\right)$

$=\left(\frac{3}{331}\right)\left(\frac{5}{331}\right)\left(\frac{823}{331}\right)$

$=\left(\frac{3}{331}\right)\left(\frac{5}{331}\right)\left(\frac{161}{331}\right)$

$=\left(\frac{3}{331}\right)\left(\frac{5}{331}\right)\left(\frac{7}{331}\right)\left(\frac{23}{331}\right)$

$=(-1)\left(\frac{331}{3}\right)\left(\frac{331}{5}\right)(-1)\left(\frac{331}{7}\right)(-1)\left(\frac{331}{23}\right)$

$=-\left(\frac{1}{3}\right)\left(\frac{1}{5}\right)\left(\frac{2}{7}\right)\left(\frac{9}{23}\right)$

$=-\left(\frac{1}{3}\right)\left(\frac{1}{5}\right)\left(\frac{2}{7}\right){\left(\frac{3}{23}\right)}^2$

$=-\left(1\right)\left(1\right)\left(1\right)\left(1\right)=-1.$

Див. також

• Символ Кронекера — Якобі

Література

• Шаблон:Айленд.Розен.Введение в современную теорию чисел
• Шаблон:Публікація