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


 

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

52317. Риторика – наука і мистецтво переконувати 67 KB
  Мета: пояснити що є предметом вивчення риторики як науки; окреслити роль і місце риторики в античному світі внесок зроблений у розвиток риторики східними слов’янами з’ясувати причину необхідності поновлення статусу риторики як науки та навчальної дисципліни в сучасній Україні використовуючи сучасне програмне забезпечення в розкритті питань; розвивати мислення комунікативні вміння зокрема робити висновки наводити аргументи та підтвердження тез; увагу пам'ять збагачувати й уточнювати словниковий запас учнів; сприяти духовному...
52318. Самое главное для человека – дружба 110.5 KB
  Ход урока І Организация урока ІІ Мотивація учебной деятельности Учитель зарубежной литературы Сегодня мы проводим необычный урок – бинарный – по изучению двух произведений из зарубежной и украинской литератур посвящённый теме дружбы т. Что вы знаете о литературном портрете Учитель української літератури Пригадайте що таке літературний портрет. Учитель української літератури Про якого героя йде мова Федькохаламидник із однойменного оповідання Володимира Винниченка. Учитель зарубежной литературы А...
52319. Сім’я як соціальна ланка суспільства 86 KB
  Охарактеризувати сімю як соціальну ланку суспільства логічно пов’язати її з предметом основи правових знань. Розкрити ознаки сім’ї в суспільстві активізувати та узагальнити знання учнів про поняття сімя та правові засади сімейних стосунків€. Розвиваюча: Розвивати вміння аналізувати уявляти та робити висновки навички спілкування правильної поведінки в сім’ї.
52320. Цикли з параметром. Площа криволінійної трапеції 49 KB
  Тема уроку з алгебри: Площа криволінійної трапеціїâ€. Освітня мета уроку математики: закріпити вміння і навички знаходження площі криволінійної трапеції через поняття первісної; ознайомити учнів із наближеними методами обчислення площі криволінійної трапеції; підготувати учнів до свідомого сприймання поняття інтегралу. Учитель математики: Що собою являє криволінійна трапеція Як знайти площу криволінійної трапеції Який метод використовується для цього Відповідь на це питання повинна бути проілюстрована малюнком і подана детальна...
52321. Народна казка (українська література), література і фольклор - скарбниця духовних багатств людства (зарубіжна література), виконання ілюстрацій до казки (образотворче мистецтво) 39 KB
  Мета: Розширити знання учнів про казки як вид усної народної творчості; повязати розвиток духовного багатства людства з розвитком фольклору і літератури; удосконалювати навички виразного читання та розуміння прочитаного; розвивати усне мислення; дати поняття про ілюстрацію та працю художників - ілюстраторів дитячої книжки
52322. Розмноження й розвиток рослин 48 KB
  Біологічний диктант вибрати окремо ознаки вітро та комахозапильних рослин Квітки дрібні безбарвні запаху не мають. Квітки великі яскраві. Дрібні квітки зібрані в суцвіття. Квітки розцвітають рано до розпускання листя.
52323. Розвиткове навчання засобами пропонованої технології 161 KB
  Та чи всяка діяльність учня є проявом його розумових зусиль Альтернатива тут така: якщо після виконання якогось завдання учень не прагне вдосконалення чи пізнання нового то він досяг рівня дії; якщо ж стає на шлях пошуку нових способів діяльності в біології – хоча б до самостійного порівняння аналізу тощо тоді це є ознакою пізнавальної діяльності яка є інструментом розвиткового навчання. Засобами розвиткового навчання на уроці за пропонованою технологією є завданнякарточки друковані на папері чи в комп’ютерному вираженні. Вони є...
52324. Сучасний урок. Яким він повинен бути 163 KB
  Стимулюючу роль в організації навчального процесу відіграють заняття учнів у малих групах парна групова колективна форми. Це найпрогресивніша група тварин. Що їх таких різних об’єднує в один тип Від яких тварин вони походять Вивчення нового матеріалу План: Класифікація типу Членистоногі Тип Членистоногі Клас Ракоподібні Клас Павукоподібні Клас Комахи Особливості зовнішньої будови і покривів членистоногих порівняно з кільчаками робота в...
52325. ПРОЦЕСИ ЖИТТЄДІЯЛЬНОСТІ РОСЛИННОГО ОРГАНІЗМУ. УСТАНОВЧО-МОТИВАЦІЙНИЙ ЕТАП НАВЧАЛЬНОГО МОДУЛЯ З БІОЛОГІЇ 440.5 KB
  ПРОЦЕСИ ЖИТТЄДІЯЛЬНОСТІ РОСЛИННОГО ОРГАНІЗМУ. Гельмонт здійснив такий дослід з рослинами. Рослину поливали дощовою водою упродовж п'яти років. Ломоносов припустив що рослина живиться з повітря.