WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Символи Лежандра та Якобі - Реферат

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


Реферат на тему:
Символи Лежандра та Якобі
Означення. Нехай p - просте, a - ціле число. Символ Лежандра визначається так:
=
Критерій Ейлера. Число a, яке не ділиться на непарне просте p, є квадратичним лишком за модулем p тоді і тільки тоді, коли 1 (mod p), і квадратичним нелишком тоді і тільки тоді коли 1 (mod p).
Доведення. За теоремою Ферма ap-1 1 (mod p) при НСД(a, p) = 1 та НСД(2, p) = 1. Або:
0 mod p
Звідси вираз в одній із дужок ділиться на p. Обидві дужки не можуть ділитися на p, оскільки тоді на p ділилася б і їх різниця, яка дорівнює 2, а за умовою теореми p - непарне просте число. Якщо a є квадратичним лишком, то a = x2 (mod p) для деякого такого x, що НСД(x, p) = 1. Маємо: xp-1 1 mod p, тобто 1 mod p або - 1 ділиться на p. Якщо a є квадратичним нелишком, то - 1 не ділиться на p, звідки + 1 повинно ділитися на p, або -1 mod p.
Наслідок. (mod p). Якщо число a є квадратичним лишком за модулем p, то за означенням символа Лежандра = 1, а за критерієм Ейлера (mod p) 1. Відповідно якщо число a є квадратичним нелишком за модулем p, то = -1 і (mod p) -1, звідки і випливає твердження.
Приклад. Чи існує розв'язок рівняння x2 5 (mod 7).
Якщо існує розв'язок рівняння, то число 5 повинно бути квадратичним лишком за модулем 7. Перевіримо це за критерієм Ейлера:
53 (mod 7) 25 * 5 (mod 7) 4 * 5 (mod 7) 20 (mod 7) -1 (mod 7). Звідси випливає, що 5 є квадратичним нелишком за модулем 7 і рівняння розв'язків не має.
Властивості символа Лежандра.
1. (mod p). Вказана властивість є наслідком критерія Ейлера.
Зокрема = 1 та = .
Отже -1 Qp якщо p 1 (mod 4) та -1 якщо p 3 (mod 4).
2. = * . Властивість випливає з послідовності очевидних порівнянь:
* * (mod p).
Зокрема, якщо a Zp* , то = 1 та = .
3. Якщо a b (mod p), то = . Властивість випливає з того, що числа одного класа є одночасно або квадратичними лишками, або нелишками. Випливаючи з цієї властивості, можна записати: = , t Z.
4. = 1. Одиницяє квадратичним лишком для довільного непарного простого p. Ця властивість випливає з того, що порівняння x2 1 (mod p) завжди має розв'язки x = ± 1 (mod p).
5. = .
Якщо p = 8k ± 1, то = = = 8k2 ± 2k - парне число.
Якщо p = 8k ± 3, то = = = 8k2 ± 6k + 1 - непарне число.
Отже =1, якщо p 1 або 7 (mod 8) та = -1, якщо p 3 або 5 (mod 8).
6. Закон взаємності непарних простих чисел. Якщо p - просте непарне число, відмінне від q, то
* = .
Помноживши цю рівність на , отримаємо: = * . Якщо виконується хоча б одна з рівностей p (mod 4) 1 чи q (mod 4) 1, то = , інакше = - .
Символ Якобі є узагальненням символу Лежандра на випадок коли n є непарним, але не обовя'язково простим.
Означення. Нехай n - непарне ціле число, n 3. Відомо, що , де pi - прості числа. Символ Якобі визначається так:
= ...
Зазначимо, що якщо n просте, то символ Якобі стає символом Лежандра.
Властивості символа Якобі
1. може приймати одне з трьох значень: -1, 0 чи 1. При цьому = 0 тоді і тільки тоді коли НСД(a, n) 1.
2. = * . Якщо a Zn* , то = 1.
3. = * .
4. Якщо a b (mod n), то = .
5. = 1.
6. = . Отже = 1, якщо n 1 (mod 4) та = -1, якщо n 3 (mod 4).
7. = .
Отже =1, якщо p 1 або 7 (mod 8) та = -1, якщо p 3 або 5 (mod 8).
8. = .
З властивостей символу Якобі випливає, що якщо n непарне, а число a подати у вигляді a = 2ka1, де a1 - непарне число, то
= =
Ця формула дає можливість обчислити значення символа Якобі не маючи розкладу числа n на прості множники.
На відміну від символу Лежандра, символ Якобі не визначає, чи є число a квадратичним лишком за модулем n. Справді, якщо a Qn , то = 1, але з того що = 1 не випливає a Qn.
Означення. Нехай n - непарне ціле число, n 3. Число a будемо називати псевдопростим за модулем n, якщо = 1. Множину псевдопростих чисел позначатимо через = Jn - Qn, де Jn = {a Zn* | = 1}.
Loading...

 
 

Цікаве