Закрыть

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

Автор: Васин Алексей
Опубликовано 11.04.2012 в 19:38
Раздел: Теория чисел
Теги:

Определение. Для любого нечетного $p$ и целого $a$ символ Лежандра определяется следующим образом:

$\left( \frac{a}{p} \right) = \left\{ \begin{array}{l} 0, если  a \equiv 0  mod  p \\ 1,  если  a  -  вычет  mod  p \\ -1, если  a  -  невычет  mod  p \end{array}$

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

Утверждение 1. $a_{1}  \equiv  a  mod  p  \Rightarrow \left( \frac{a}{p} \right) = \left( \frac{a_1}{p} \right).$

Утверждение 2. (Критерий Эйлера)  $\left( \frac{a}{p} \right) =a^{\frac{p-1}{2}}$

Доказательство.

Для $a \equiv 0 mod  p$ утверждение очевидно.

Далее малая теорема Ферма гласит: $a \neq  0  mod  p  \Rightarrow  a^{p-1}  \equiv  1  mod  p.$

Рассмотрим 2 случая:

1. $a$ - квадратичный вычет, то есть $\exists x: x^2 \equiv a  mod  p$. Тогда $a^{\frac{p-1}{2}}=x^{p-1} \equiv 1  mod  p$. Последнее сравнение вытекает из малой теоремы Ферма. Но из того, что $a$ - квадратичный вычет, вытекает, что $\left( \frac{a}{p} \right) = 1$, следовательно $\left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}}  mod  p$.

2. $a$ - квадратичный невычет, тогда из Утверждения 2 следует, что $\exists j:  a=\theta^{2j+1}$, где $\theta$ - порождающий элемент. Тогда

$a^{\frac{p-1}{2}} =\theta^{\frac{(2j+1)(p-1)}{2}}=\theta^{\frac{(2jp-2j+p-1)}{2}}=\theta^{j(p-1)+\frac{p-1}{2}}=\theta^{\frac{p-1}{2}}={\theta^{\left(p-1\right)}}^{\frac{1}{2}}=1^{\frac{1}{2}}.

Сравнение $x^2\equiv  1  mod  p$ может иметь только 2 решения: $x=\pm1$, но, так как $\theta$ - порождающий элемент, то только одна ее степень от $0$ до $p-1$ может давать $1$, и это - степень $p-1$. Следовательно $\theta^{\frac{p-1}{2}}\equiv-1  mod  p$, а значит

$a^{\frac{p-1}{2}}\equiv-1  mod  p .$

Вспомним, что $a$ - квадратичный невычет, и получим требуемое:

$ \left(\frac{a}{p}\right)=a^{\frac{p-1}{2}}$

Утверждение 3. $\left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right)\left( \frac{b}{p} \right)$

Доказательсьво. Доказательство следует из критерия Эйлера: $\left( \frac{ab}{p} \right) = (ab)^{\frac{p-1}{2}} = a^{\frac{p-1}{2}} b^{\frac{p-1}{2}} = \left( \frac{a}{p} \right)\left( \frac{b}{p} \right)$

Утверждение 4. Если $GCD(a, p)=1$, то справедливо равенство: $\left( \frac{a^2 b}{p} \right) =\left( \frac{b}{p} \right)$

Доказательсьво. Доказательство следует из критерия Эйлера: $\left( \frac{a^2b}{p} \right) = (a^2 b)^{\frac{p-1}{2}} = (a^2)^{\frac{p-1}{2}} b^{\frac{p-1}{2}} = \left( \frac{b}{p} \right)$.

Так как $GCD(a, p)=1$, то $a^2$ - квадратичный вычет, и утверждение очевидно.

Утверждение 5. $\left( \frac{1}{p} \right) = 1$; $\left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}}$;

Доказательство:

Первое равенство следует из того, что $1^2\equiv 1 mod p$, a второе из критерия Эйлера при $a=-1$

Утверждение 6. $\left( \frac{2}{p} \right) = (-1)^{\frac{p^2-1}{8}}$

(Доказательство Виноградов И.М. Теория чисел)

Алгоритм вычисления символа Лежандра является рекурсивным. На практике он неприменим для больших чисел, так как требует разложения числа на простые сомножители.

Теорема  1 (Квадратичный закон взаимности) Для любых простых нечетных $p$ и $q$ справедливо:

$\left( \frac{p}{q} \right)= {\left( -1 \right)}^{\frac{p-1}{2}\frac{q-1}{2}}\left( \frac{q}{p} \right).$

Впервые теорема была сформулирована Эйлером в 1783 году, а впоследствии доказана Гауссом в 1796, правда имела формулировку отличную от современной.

Алгоритм:

1. Если $a<0$, то, применяя Утверждения 3 и 5, получаем $\left( \frac{a}{p} \right)=\left( \frac{-a}{p} \right)\times \left(-1\right)^\frac{p-1}{2}$. Переобозначаем $a:=-a$.

2. $a:=a mod p$ (операцией $\mod$ без скобок мы будем обозначать взятие остатка).

3. Раскладываем $a$ на простые сомножители:

$a=p^{k^1}_{1}\times...\times p^{k^s}_{s},  где $p_j$ - простые числа для $j=1,...,s$}.

Тогда согласно Утверждению 3

$\left( \frac{a}{p} \right) = \left( \frac{p_1}{p} \right)^{k_1}\times...\times \left( \frac{p_s}{p} \right)^{k_s}$

Множители в четной степени $k_j$ можно удалить, так как они все равны 1.

4. Для всех $p_j=2$ и нечетных $k_j$ вычисляем $\left( \frac{2}{p} \right)$ по Утверждению 6.

5. Для всех $p_j\neq2$ и нечетных $k_j$ применяем квадратичный закон взаимности:

$\left( \frac{p_j}{p} \right)= {\left( -1 \right)}^{\frac{p_j-1}{2}\frac{p-1}{2}}\left( \frac{p}{p_j} \right).$

6. Применяем алгоритм для каждого $\left( \frac{p}{p_j} \right).$

Пример. Вычислить $\left( \frac{126}{53} \right).$

$\left( \frac{126}{53} \right) = \left( \frac{20}{53} \right) = \left( \frac{2}{53} \right)^2 \left( \frac{5}{53} \right) =\left( \frac{5}{53} \right) = \left(-1\right)^{\frac{53-1}{2}\frac{5-1}{2}} \left( \frac{53}{5} \right) = \left( \frac{3}{5} \right) = \left(-1\right)^{\frac{3-1}{2}\frac{5-1}{2}} \left( \frac{5}{3} \right) = \left( \frac{2}{3} \right) = \left(-1\right)^{\frac{9-1}{8}}=-1$

Комментарии (0)

Комментировать могут только зарегистрированные пользователи

Подразделы
Новые статьи
  • 2017-07-09 14:11:58 Robertfoere » трейдинг

    Я получил бесплатно $100 для обу...

  • 2017-07-09 13:54:28 Robertfoere » forex

    Я получил бесплатно $100 для ...

  • 2017-07-09 07:21:33 Robertfoere » trader

    Я получил бесплатно $100 для обу...

  • 2017-07-09 07:03:20 Robertfoere » broker

    Я получил бесплатно $100 для обу...

  • 2017-07-06 14:45:03 Robertfoere » stock exchange

    Я получил бесплатно $100 для обу...

Aрхив статей