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

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

Визначення

Нехай 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{\pmod {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{\pmod {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},$ перший додатковий закон (англ. first supplementary law)
• $\left({\frac {2}{p}}\right)=(-1)^{(p^{2}-1)/8},$ другий додатковий закон (англ. second supplementary law)

Доведення

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

${\begin{aligned}1&=(-1)(-1)\\2&=2(-1)^{2}\\3&=(-3)(-1)^{3}\\4&=4(-1)^{4}\\&\quad \quad \ldots \\s&=(\pm s)(-1)^{s}\end{aligned}}$

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

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

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

Збираючи все до купи, ми отримуємо $2^{s}s!\equiv s!(-1)^{s(s 1)/2}\mod p$, або по скороченні факторіалів $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\leq a\leq p-1$ рівно половина має символ Лежандра, рівний 1, а інша половина — –1.
• Символ Лежандра при $p>2$ можна обчислити за допомогою критерію Ейлера: $\left({\frac {a}{p}}\right)\equiv a^{(p-1)/2}{\pmod {p}}$

Обчислення

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

Приклад

$\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.$

Див. також

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

Література

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — Москва : Мир, 1987. — 416 с.(рос.)
• Нестеренко А. Ю. Теоретико-числовые методы в криптографии : [рос.]. — Московский государственный институт электроники и математики. — М., 2012. — 224 с. — ISBN 978-5-94506-320-4.