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

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

Зміст

1 Визначення
2 Властивості
3 Приклад обчислення
4 Див. також
5 Джерела

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

Нехай 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{align} 1&= (-1)(-1) \\ 2&=2(-1)^2 \\ 3&= (-3)(-1)^3 \\ 4&= 4 (-1)^4 \\ & \quad\quad \ldots\\ s&= (\pm s)(-1)^s \end{align}

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

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