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

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

Визначення[ред. • ред. код]

Нехай 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}}$