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


 

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

16470. Основи конституційного ладу України 378 KB
  НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ ІНСТИТУТ ДЕРЖАВИ І ПРАВА ім. В. М. КОРЕЦЬКОГО В. Ф. ПОГОРІЛКО основи конституційного ЛАДУ УКРАЇНИ Київ Ін Юре 1997 ББК 67.94УКР300 1143 Погорілко В. Ф. П43Основи конституційного ладу України. К.: Ін Юре 1997. 40
16471. Права та свободи людини і громадянина в Україні 494 KB
  НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ ІНСТИТУТ ДЕРЖАВИ І ПРАВА ім. В. М. КОРЕЦЬКОГО В. Ф. ПОГОРІЛКО В. В. ГОЛОВЧЕНКО М. І. СІРИЙ ПРАВА ТА СВОБОДИ ЛЮДИНИ І ГРОМАДЯНИНА В УКРАЇНІ Київ Ін Юре 1997 ББК 67.94УКР300 П43 Погорілко В. Ф. Головчен...
16472. Президент України 276.5 KB
  У брошурі розглядаються питання запровадження в Україні інституту президентства, аналізується конституційний статус Президента як глави держави, висвітлюється порядок його обрання і вступу на посаду. Особлива увага приділяється розгляду конституційних повноважень Президента, його відносини з іншими інститутами державної влади, роль у забезпеченні державного суверенітету України, прав та свобод людини і громадянина.
16473. Верховна Рада України 403.5 KB
  НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ ІНСТИТУТ ДЕРЖАВИ І ПРАВА ім. В. М. КОРЕЦЬКОГО Л. Т. КРИВЕНКО ВЕРХОВНА РАДА УКРАЇНИ Київ Ін Юре 1997 ББК 67.94УКР300.6 К82 Кривенко Л. Т. К82Верховна рада України. К.: 1н Юре 1997. 47 с Бчка Нова Конституція Украї
16474. Органи виконавчої влади в Україні 419.5 KB
  У брошурі висвітлюються питання змісту, організації та правового регулювання виконавчої влади в Україні. Розглядаються побудова та функціонування системи органів виконавчої влади, характеризуються правовий статус і структура її окремих ланок, а також ключові напрями здійснення адміністративної реформи
16475. Административная ответственность: Учебник 1.39 MB
  Агапов А.Б. Административная ответственность: Учебник. М.: Статут 2000. 251с. ISBN 5835400373 В учебнике рассмотрены все основные проблемы общеобязательного курса Административная ответственность. В Общей части анализируются базовые институты административной ответ
16476. Антропный принцип: истоки и следствия в Европейской научной рациональности 283.5 KB
  Антропный принцип: истоки и следствия в Европейской научной рациональности А. Н. Павленко Формулировка Б. Картером в 1973 г. антропного космологического принципа АКП первоначально в качестве объяснения совпадения Больших чисел 1040 1080 как и всякое крупное достижение...
16477. Антропный космологический принцип и христианский антропоцентризм 83 KB
  Антропный космологический принцип и христианский антропоцентризм. В.И. Гоманьков И само создание мира его сохранение и управление возвещает величие Божества.Преп. Иоанн Дамаскин ЭВОЛЮЦИЯ ВСЕЛЕННОЙ Замечательным достижением космологии и физики XX века являет
16478. Антропный принцип Вселенной 98.5 KB
  Антропный принцип 1. Сильный и слабый антропный принцип. Под антропностью Вселенной подразумевается её весьма деликатная конструкция допускающая и может быть предполагающая возможность возникновения в ней жизни и человека. Физические науки достигли весьма выс...