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


 

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

53554. Казка казкою, а в ній наука 46 KB
  Пріоритетні лінії розвитку: соціально-моральний емоційноціннісний пізнавальний 6й рік життя Тема: Казка казкою а в ній наука Автор: Царенко Вікторія Миколаївна вихователь ДНЗ №8 Золотий півник м. Вихователь. Вихователь. Де ви могли чути ці слова Вихователь.
53555. Додатні та від’ємні числа. Протилежні числа. Координатний промінь 923.5 KB
  Протилежні числа. Мета модуля: сформувати уявлення учнів про зміст понять додатні числа від'ємні числа протилежні числа зміст поняття координати точки на координатній прямій; виробити вміння: відрізняти додатні числа від від'ємних й виконувати прості вправи що передбачають таку класифікацію; за готовими рисунками визначити координати вказаних точок звіряток та будувати на координатній прямій точки з вказаними координатами; розвивати логічне мислення та пізнавальну активність учнів при розвязуванні вправ. Розвязування...
53556. Оценка акций 25 KB
  Номинальная цена — это цена, напечатанная на бланке акции или установленная при ее выпуске. Номинальная цена формируется в момент создания акционерного общества и показывает, какая часть величины уставного капитала приходилась на одну акцию на момент ее формирования.
53557. Емма Андієвська „Казка про яян”. Прихований повчальний зміст казки 462.5 KB
  Прихований повчальний зміст казки. Розробка інтегрованого уроку з української літератури й економіки в 6 класі вчителя української мови та літератури...
53558. Розв’язування вправ 7 клас 106.5 KB
  Повторення систематизація і узагальнення знань учнів В одному селі жили собі сестричка Олеся і братик Василько. От якось і каже Олеся: Васильку давай гратися в піжмурки. Тільки як братик заховається то Олеся бігає шукає а знайти не може. Допоможемо Олесі виконати завдання незнайомця на екрані 6 усних завдань Повторення систематизація і узагальнення знань учнів Який з графіків зайвий 2 Яка з функцій зайва у= х 3...
53559. Доходность и риск портфеля 37.5 KB
  Инвестиционным портфелем называют сформированную в соответствии с целями инвестора совокупность объектов инвестирования, которая рассматривается как целостный объект управления.
53560. Завітала казка до малят 40 KB
  Погляньте діти як змінився наш друг Сніговик. Я прекрасна Снігова Королева Я зачаклувала Сніговика бо діти частіше згадують про нього аніж про мене. Зайчата що сталося чому ви плачете Зайчик 1: Як нам не плакати коли надворі холодно й ми вже замерзли Зайчик 2: Ми загубилися в лісі й хочемо до своєї матусі Зайчик 3: Хто малих нас пожаліє хто нам лапоньки зігріє Діти жаліють зайченят. Діти гукають Сніг: Снігу Снігу Сніговію ти нам зайчиків зігрій Сніг: Не можу бо боюся що Снігова Королева прожене мене.
53561. Активізація пізнавальної активності учнів при вивченні основ програмування шляхом використання розвивальної казкотерапії 61.5 KB
  У казці можна знайти повний перелік людських проблем і образні способи їх розв’язання. Слухаючи казки в дитинстві, людина поповнює у підсвідомості банк життєвих ситуацій. Цей банк за необхідності може бути активізований, якщо ні — так і залишиться пасивним. Казка поєднує дорослого й дитину.