6037

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

Лабораторная работа

Математика и математический анализ

Символи Лежандра та Якобі Означення. Нехай p - просте, a - ціле число. Символ Лежандра визначається так: Критерій Ейлера. Число a, яке не ділиться на непарне просте p, є квадратичним лишком за модулем p тоді і тільки тоді, коли...

Украинкский

2012-12-27

101.5 KB

2 чел.

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

Означення. Нехай 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}.


 

А также другие работы, которые могут Вас заинтересовать

5977. Жилищное право. Конспект лекций 990.5 KB
  Краткий конспект лекций содержит основные положения Жилищного права. В нем раскрываются определения понятий Жилищного права, его предмета и метода, проводится анализ основных принципов в сфере жилищных правоотношений, рассматриваются вопросы жилищно...
5978. Проблемы корпоративного права. Корпоративные правоотношения 85.58 KB
  Проблемы корпоративного права. Корпоративные правоотношения Основные понятия Корпорация – от лат. corpus habere - в Римском праве им обозначался статус юр. лица. Римск. право не знало учения о юр. лицах. Корпорация в РФ - ст. 71 ФЗ «О...
5979. Влияние легирующих элементов на механические и химические свойства стали 455 KB
  Следуя в ногу с техническим прогрессом, требующим удовлетворения растущих потребностей вновь создаваемых и развивающихся отраслей промышленности, ОАО ТАГМЕТ наращивал объем производства за счет расширения старых и строительства новых цехо...
5980. МЕХАНИЗМ МЫШЕЧНОГО СОКРАЩЕНИЯ 104.69 KB
  Мышечные ткани (обзор). Физиологические свойства поперечно-полосатых скелетных мышц. Структурно-функциональная характеристика мускулатуры (поперечно-полосатых мышц), их иннервация. Механизм мышечного сокращения. Явления, сопровождающие мышечное сокращение.
5981. Экономика как сфера жизнедеятельности общества 272.7 KB
  Чтобы существовать, жить и развиваться, сохранять и продолжать на земле свой род, человек обязан удовлетворять свои потребности. Хозяйственная деятельность человека предполагает: А) единство цели и средств ее достижения Б) затраты энергии и ресурсо...
5982. Основные понятия по передаче информации 937 KB
  Основные понятия по передаче информации Информация это совокупность сведений об окружающем нас мире. Эти сведения человек получает в процессе взаимодействия с окружающим миром, изучения различных явлений посредством книг, радио, телевидения и других...
5984. Практика проектирования. Руководство к лабораторно-практическим занятиям 3.56 MB
  Представлен перечень практических заданий к лабораторно-практическим занятиям, типовому расчету, курсовой работе и курсовому проекту для студентов энергомашиностроительного факультета при изучении основ инженерного проектирования на завершающем этап...
5985. Аграрне право України О.О. Погріб 5.43 MB
  У підручнику докладно розглянуті умови та порядок створення та функціонування субєктів аграрних правовідносин, питання права власності їх на землю, розкриті умови та порядок набуття і користування земельними ділянками, реалізації земельних прав і обмеження прав на землю.