Символи Лежандра та Якобі (реферат)

Реферат на тему:

Символи Лежандра та Якобі.

Означення. Нехай p — просте, a — ціле число. Символ Лежандра $$\left(\frac{a}{p}\right)$$ визначається так:

$$\left(\frac{a}{p}\right)$$ = $$\begin{array}{c}\mathrm{0,}\text{якщо}\text{p}\text{ділиться}\text{на}a\\ \mathrm{1,}\text{якщо}a{Q}_p\\ -\mathrm{1,}\text{якщо}a{\stackrel{}{Q}}_p\\ \\ \begin{array}{c}\{\{\end{array}\hfill \\ \end{array}$$.

Критерій Ейлера. Число a, яке не ділиться на непарне просте p, є квадратичним лишком за модулем p тоді і тільки тоді, коли $$a^{\frac{p-1}{2}}$$ 1 (mod p), і квадратичним нелишком тоді і тільки тоді коли $$a^{\frac{p-1}{2}}$$ mod p).

Доведення. За теоремою Ферма ap-1 $$$$ 1 (mod p) при НСД (a, p) = 1 та НСД (2, p) = 1. Або:

$$\begin{array}{c}\left(a^{\frac{p-1}{2}}+1\right)\left(a^{\frac{p-1}{2}}-1\right)\\ \end{array}$$ 0 mod p.

Звідси вираз в одній із дужок ділиться на p. Обидві дужки не можуть ділитися на p, оскільки тоді на p ділилася б і їх різниця, яка дорівнює 2, а за умовою теореми p — непарне просте число. Якщо a є квадратичним лишком, то a = x2 (mod p) для деякого такого x, що НСД (x, p) = 1. Маємо: $$a^{\frac{p-1}{2}}{\left(x^2\right)}^{\frac{p-1}{2}}$$ -1 1 mod p, тобто $$a^{\frac{p-1}{2}}$$ mod p або $$a^{\frac{p-1}{2}}$$ — 1 ділиться на p. Якщо a є квадратичним нелишком, то $$a^{\frac{p-1}{2}}$$ — 1 не ділиться на p, звідки $$a^{\frac{p-1}{2}}$$ + 1 повинно ділитися на p, або $$a^{\frac{p-1}{2}}$$ mod p.

Наслідок. $$\left(\frac{a}{p}\right)$$ math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >ap-12 (mod p). Якщо число a є квадратичним лишком за модулем p, то за означенням символа Лежандра $$\left(\frac{a}{p}\right)$$ = 1, а за критерієм Ейлера $$a^{\frac{p-1}{2}}$$ (mod p) Відповідно якщо число a є квадратичним нелишком за модулем p, то $$\left(\frac{a}{p}\right)$$ = -1 і $$a^{\frac{p-1}{2}}$$ (mod p), звідки і випливає твердження.

Приклад. Чи існує розв’язок рівняння x2 $$$$ 5 (mod 7).

Якщо існує розв’язок рівняння, то число 5 повинно бути квадратичним лишком за модулем 7. Перевіримо це за критерієм Ейлера:

$$5^{\frac{7-1}{2}}$$ (mod 7) * 5 (mod 7) * 5 (mod 7) (mod 7) (mod 7). Звідси випливає, що 5 є квадратичним нелишком за модулем 7 і рівняння розв’язків не має.

Властивості символа Лежандра.

1. $$\left(\frac{a}{p}\right)$$ math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >ap-12 (mod p). Вказана властивість є наслідком критерія Ейлера.

Зокрема $$\left(\frac{1}{p}\right)$$ = 1 та $$\left(\frac{-1}{p}\right)$$ = $$(\text{-1}{)}^{\frac{p-1}{2}}$$ .

Отже -1 $$$$ Qp якщо p $$$$ 1 (mod 4) та -1 $$$$ $${\stackrel{}{Q}}_p$$ якщо p (mod 4).

2. $$\left(\frac{ab}{p}\right)$$ = $$\left(\frac{a}{p}\right)$$ * $$\left(\frac{b}{p}\right)$$. Властивість випливає з послідовності очевидних порівнянь:

$$\left(\frac{ab}{p}\right)$$ $$$$ $$(\text{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)$$ (mod p).

Зокрема, якщо a $$$$ Zp*, то $$\left(\frac{a^2}{p}\right)$$ = 1 та $$\left(\frac{a^{2}b}{p}\right)$$ = $$\left(\frac{b}{p}\right)$$ .

3. Якщо a (mod p), то $$\left(\frac{a}{p}\right)$$ = $$\left(\frac{b}{p}\right)$$. Властивість випливає з того, що числа одного класа є одночасно або квадратичними лишками, або нелишками. Випливаючи з цієї властивості, можна записати: $$\left(\frac{a}{p}\right)$$ = $$\left(\frac{a+\text{pt}}{p}\right)$$, t $$$$ Z.

4. $$\left(\frac{1}{p}\right)$$ = 1. Одиниця є квадратичним лишком для довільного непарного простого p. Ця властивість випливає з того, що порівняння x2 $$$$ 1 (mod p) завжди має розв’язки x = ± 1 (mod p).

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

Якщо p = 8k ± 1, то $$\frac{p^2-1}{8}$$ = $$\frac{(8k\pm 1{)}^2-1}{8}$$ = $$\frac{\text{64}{k}^2\pm \text{16}k}{8}$$ = 8k2 ± 2k — парне число.

Якщо p = 8k ± 3, то $$\frac{p^2-1}{8}$$ = $$\frac{(8k\pm 3{)}^2-1}{8}$$ = $$\frac{\text{64}{k}^2\pm \text{48}k+8}{8}$$ = 8k2 ± 6k + 1 — непарне число.

Отже $$\left(\frac{2}{p}\right)$$ =1, якщо p $$$$ 1 або 7 (mod 8) та $$\left(\frac{2}{p}\right)$$ = -1, якщо p $$$$ 3 або 5 (mod 8).

6. Закон взаємності непарних простих чисел. Якщо p — просте непарне число, відмінне від q, то.

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

Помноживши цю рівність на $$\left(\frac{p}{q}\right)$$, отримаємо: $$\left(\frac{q}{p}\right)$$ = $${\left(-1\right)}^{\frac{(p-1)(q-1)}{4}}$$ * $$\left(\frac{p}{q}\right)$$. Якщо виконується хоча б одна з рівностей p (mod 4) $$$$ 1 чи q (mod 4) $$$$ 1, то $$\left(\frac{p}{q}\right)$$ = $$\left(\frac{q}{p}\right)$$, інакше $$\left(\frac{p}{q}\right)$$ = - $$\left(\frac{q}{p}\right)$$ .

Символ Якобі є узагальненням символу Лежандра на випадок коли n є непарним, але не обовя’язково простим.

Означення. Нехай n — непарне ціле число, n Відомо, що $$n=p_1^{k_1}{p}_2^{k_2}\text{.}\text{.}\text{.}{p}_t^{k_t}$$, де pi — прості числа. Символ Якобі $$\left(\frac{a}{n}\right)$$ визначається так:

$$\left(\frac{a}{n}\right)$$ = $${\left(\frac{a}{p_1}\right)}^{k_1}$$ $${\left(\frac{a}{p_2}\right)}^{k_2}$$ … $${\left(\frac{a}{p_t}\right)}^{k_t}$$.

Зазначимо, що якщо n просте, то символ Якобі стає символом Лежандра.

Властивості символа Якобі.

1. $$\left(\frac{a}{n}\right)$$ може приймати одне з трьох значень: -1, 0 чи 1. При цьому $$\left(\frac{a}{n}\right)$$ = 0 тоді і тільки тоді коли НСД (a, n) $$$$ 1.

2. $$\left(\frac{ab}{n}\right)$$ = $$\left(\frac{a}{n}\right)$$ * $$\left(\frac{b}{n}\right)$$. Якщо a $$$$ Zn*, то $$\left(\frac{a^2}{n}\right)$$ = 1.

3. $$\left(\frac{a}{mn}\right)$$ = $$\left(\frac{a}{m}\right)$$ * $$\left(\frac{a}{n}\right)$$ .

4. Якщо a $$$$ b (mod n), то $$\left(\frac{a}{n}\right)$$ = $$\left(\frac{b}{n}\right)$$ .

5. $$\left(\frac{1}{n}\right)$$ = 1.

6. $$\left(\frac{-1}{n}\right)$$ = $${\left(-1\right)}^{\frac{n-1}{2}}$$. Отже $$\left(\frac{-1}{n}\right)$$ = 1, якщо n $$$$ 1 (mod 4) та $$\left(\frac{-1}{n}\right)$$ = -1, якщо n $$$$ 3 (mod 4).

7. $$\left(\frac{2}{n}\right)$$ = $${\left(-1\right)}^{\frac{n^2-1}{8}}$$ .

Отже $$\left(\frac{2}{n}\right)$$ =1, якщо p $$$$ 1 або 7 (mod 8) та $$\left(\frac{2}{n}\right)$$ = -1, якщо p $$$$ 3 або 5 (mod 8).

8. $$\left(\frac{m}{n}\right)$$ = $$\left(\frac{n}{m}\right)$$ $${\left(-1\right)}^{\frac{(m-1)(n-1)}{4}}$$ .

З властивостей символу Якобі випливає, що якщо n непарне, а число a подати у вигляді a = 2ka1, де a1 — непарне число, то.

$$\left(\frac{a}{n}\right)$$ = $$\left(\frac{2^k}{n}\right)$$ $$\left(\frac{a_1}{n}\right)$$ = $$\left(\frac{2^k}{n}\right)$$ $$\left(\frac{n\text{mod}{a}_1}{a_1}\right)$$ $${\left(-1\right)}^{\frac{(a_1-1)(n-1)}{4}}$$.

Ця формула дає можливість обчислити значення символа Якобі не маючи розкладу числа n на прості множники.

На відміну від символу Лежандра, символ Якобі $$\left(\frac{a}{n}\right)$$ не визначає, чи є число a квадратичним лишком за модулем n. Справді, якщо a $$$$ Qn, то $$\left(\frac{a}{n}\right)$$ = 1, але з того що $$\left(\frac{a}{n}\right)$$ = 1 не випливає a $$$$ Qn.

Означення. Нехай n — непарне ціле число, n Число a будемо називати псевдопростим за модулем n, якщо $$\left(\frac{a}{n}\right)$$ = 1. Множину псевдопростих чисел позначатимо через $$Q_n$$ = Jn — Qn, де Jn = {a $$$$ Zn* | $$\left(\frac{a}{n}\right)$$ = 1}.