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


 

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

54576. Німецькомовні країни. Розвиток монологічного мовлення 48 KB
  Über Deutschland, Österreich und die Schweiz haben wir vieles erfahren. Und noch gibt es zwei kleine Staaten, wo man deutsch spricht. Hört kleine Information über diese Staaten zu!
54577. ПРОГРАМА ДИСТАНЦІЙНОГО НАВЧАННЯ З НІМЕЦЬКОЇ МОВИ 96.5 KB
  Звісно відпочинок це також необхідна сторона нашого життя але головне завдання вчителя це компетентний учень і робота в режимі дистанційного навчання є чудовим інструментом для його виховання. Робота з текстом: Виписати та вивчити нові слова; Прочитати текст; Перекласти усно; Дати письмові відповіді на питання до тексту та переслати їх на електронну адресу вчителя. Робота з текстом: Виписати та вивчити нові слова; Прочитати текст; Перекласти усно; Виконати тестове завдання до тексту та переслати отримані відповіді на...
54578. Значення нітрогену та його сполук в природі та господарській діяльності людини 57.5 KB
  Сьогодні ми проведемо узагальнюючий урок з теми Підгрупа нітрогену. Щоб виконати завдання редакції необхідно заповнити таблицю Позитивна та негативна роль нітрогену та його сполук. Роль нітрогену та його сполук Позитивна Негативна ІІІ.
54579. НАВЧАЛЬНО-МЕТОДИЧНА КАРТКА (ПЛАН) ЗАНЯТТЯ 174 KB
  Мета завдання: Навчальна: зясувати соціальноекономічну сутність заробітної плати; визначити сфери державного регулювання оплати праці в умовах ринкових відносин; проаналізувати особливості організацій оплати праці на підприємстві; зясувати що лежить в основі побудови системи оплати праці на підприємстві в сучасних умовах; виявити переваги та недоліки різних систем...
54580. З Новим роком! 103.5 KB
  Принц Рік новий вже так близенько Кілька днів всього пройде. Принц Рік новий не за горами Крок за кроком і прийде. Але поки разом з нами Рік старий.
54581. Уроки вдохновения 3.3 MB
  Если вспомнить сколько существует всякой путаницы недоумений всевозможных толкований вокруг метода Константина Сергеевича получившего название метода физических действий сколько было опубликовано неясных изложений этого метода его ближайшими учениками и помощниками последних лет жизни то невольно радуешься тому что почти стенографическое изложение репетиций Станиславского по этому методу становится нашим общим достоянием. Эти ленинские слова из беседы с Кларой Цеткин можно поставить эпиграфом к бессмертному учению Константина...
54582. Предложение. Закон предложения. Факторы, влияющие на предложение 25.07 KB
  Величина предложения – это максимальное количество товаров и услуг, которое производители (продавцы) способны и готовы продать по определенной цене, в определенном месте и в определенное время.
54583. Новогоднее «Кривое зеркало» 62 KB
  Будут Снегурочка и Дед Мороз Он вам подарков немало привез. Огого Народуто сколько И что это они собрались Всех Дед Мороз пригласил Может я не сюда попала Во ктото идет. Дед Мороз вбегает кидается к сидящим в зале хватает их ошибается заглядывает под стулья лезет по рядам сам в очках снимает их заглядывает близко в глаза Снегурочка Внученька Где ты Ты нет опять не она. Где же ты Снегурочка Вечно она куда нибудь теряется убегает Снегурочка Ушел Вот достал дедуля Пора появится А я может быть занята...