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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Приклад обчислення[ред.ред. код]

Подані вище властивості використовуються у наступному типовому прикладі:

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

Див. також[ред.ред. код]

Джерела[ред.ред. код]