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


 

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

47154. Право на достоверную информацию о состоянии окружающей среды 69.06 KB
  Как реакция на эту общественную потребность Законом Об охране окружающей природной среды гражданам было предоставлено право требовать от соответствующих органов предоставления своевременной полной и достоверной информации о состоянии окружающей среды и мерах по ее охране. Позже Конституция РФ также закрепила право каждого на достоверную информацию о состоянии окружающей среды. Какую информацию о состоянии окружающейсреды можно считать достоверной полной и своевременной Достоверной является неискаженная заведомо или по небрежности...
47156. Международные книжные ярмарки: названия, особенности, значение для мирового книгоиздания 69.92 KB
  Международные книжные ярмарки: названия особенности значение для мирового книгоиздания. Книжные ярмарки помогали издателям представить свой ассортимент а книготорговцам установить с ними отношения на будущее и купить партии тиражей на коммерческие с их точки зрения издания. На эту ярмарку собираются представители издательств всего региона от Сахалина до Якутии представлены издания учебных центров и университетов издательства ДВО РАН и весь спектр производимой в регионе продукции. Аннотация как элемент аппарата издания.
47159. Формирование принципов редактирования в издательской практике России 40–50-х годов XIX века 70.5 KB
  Журналы расходились по всем концам России становились умственной и духовной пищей передавались из рук в руки зачитывались до дыр. Современники не случайно называли действовавший устав чугунным понимая опасность такой ситуации в России. Белинского в теорию редактирования В работах Белинского поднимаются вопросы о целях и задачах печати в России особенно это касается вопросов создания журнала его популярности отличий журнала от газеты характере журнала и его отделов и т.
47161. Государственный экологический контроль. Права государственных экспертов 71.28 KB
  Государственный контроль в области охраны окружающей среды государственный экологический контроль осуществляется федеральными органами исполнительной власти и органами исполнительной власти субъектов Российской Федерации. Государственный контроль в области охраны окружающей среды государственный экологический контроль осуществляется в порядке установленном Правительством Российской Федерации. В случае если при строительстве реконструкции капитальном ремонте объектов капитального строительства предусмотрено осуществление...
47162. Subordinate clauses of adverbial positions 71.5 KB
  Adverbial clauses are usually classified according to their meaning, that is, according to the relation they bear to the main clause. They differ from nominal and attributive clauses in that they are introduced by conjunctions with a more distinct meaning