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


 

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

47875. Кольори та їх значення 237.5 KB
  Тема: СИМВОЛІКА КОЛЬОРІВ План Особливе значення читання мови барв Кольорові асоціації Кольорова символіка країн світу Мета: сформувати естетичні уявлення про колір пояснити основну символіку кольору дізнатися про значення кольору в різних країнах Обладнання: навчальні плани програми підручники посібники для дизайну; ТЗН для мультимедіа презентації. Так в астрології промені Сонця що розкладені в спектр і дають 7 кольорів відповідали 7 основним планетам: червоний колір Марса синій колір Венери жовтий колір...
47876. Своєрідність драматичних творів першої половини ХХ століття 51.5 KB
  Антігона надзвичайно любить життя, природу і красу. Вона кохає Гемона, сина Креона, мріє стати його дружиною і народити сина. Але цілком свідомо відмовляється від усього цього. Чому Антігона це зробила, вона намагається пояснити у своєму діалозі-змаганні з Креоном, який займає майже третину тексту. На відміну від античної героїні нею керує не почуття обов’язку
47877. Професійне мовлення вчителя 152.5 KB
  Культура мовлення вчителя компонент педагогічної майстерності. Специфіка педагогічного мовлення. Функції і комунікативні якості мовлення вчителя.
47878. Економічна історія 258.56 KB
  Критерії періодизації курсу Економічна історія історія народного господарства важлива гуманітарна дисципліна складова частина вищої економічної освіти. До історії господарства професіоналекономіст звертається усвідомлюючи це чи ні буквально на кожному кроці. Адже вся технікоорганізаційна динаміка даного господарства має історичний характер; при порівнянні показників різних періодів по суті простежується історикоекономічний процес формування і розвитку виробництва. Вона забезпечує тісний звязок історичних знань з економікою...
47880. Загальна патологія 135.5 KB
  Павлова про розвиток хвороби та його основні положення. Наука яка вивчає закономірності виникнення розвитку і кінця хвороби або іншими словами вивчає життєдіяльність хворого організму називається патологічною фізіологією. Перша частина нозологія або загальне вчення про хвороби. При аналізі хвороби виникає два запитання: чому виникла хвороба і як вона розвивається.
47881. Судова, правоохоронна та правозахисна діяльність 271 KB
  Поняття правоохоронного органу та правоохоронної діяльності Поняття правоохоронного органу. Під правоохоронним органом розуміють державну установу або державну юридичну особу яка діє в системі органів влади й виконує на основі закону державні функції владні організаційнорозпорядчі контрольноперевірочні тощо в різних сферах внутрішньої та зовнішньої діяльності Української держави. За законом до правоохоронного органу належить такий державний орган предмет діяльності якого законодавче зафіксовано як його завдання або функції саме...
47882. ГОСПОДАРСЬКІ РІШЕННЯ У РІЗНИХ СФЕРАХ ПІДПРИЄМНИЦЬКОЇ ДІЯЛЬНОСТІ 814 KB
  Сутнісна характеристика господарських рішень План: Господарські рішення та їх види Способи формалізації та реалізації господарських рішень Якість і ефективність господарських рішень Доповідь: Особливості управління ризиками господарської діяльності Л1Ст. ГОСПОДАРСЬКІ РІШЕННЯ ТА ЇХ ВИДИ Від прийняття господарських рішень їх якості раціональності й обґрунтованості в багатьох випадках залежать реальні можливості досягнення цілей організації її ефективна діяльність....