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


 

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

44754. Умножение десятичных дробей 40 KB
  Умножение десятичных дробей. Тип урока: комбинированный изучение нового материала закрепление изученного Вид урока: традиционный Цели урока: Образовательные: Подвести учащихся к пониманию правила умножения десятичных дробей; научить выполнять умножение десятичных дробей. Оборудование урока: доска с меловыми записями рабочие тетради учебник Математика 5 кл.
44755. Умножение и деление десятичных дробей на натуральное число 1.28 MB
  Умножение и деление десятичных дробей на натуральное число. Тип урока: урок контроля. Вид урока: традиционный Цели урока: Образовательные: Проверить знания умения и навыки по теме: Умножение и деление десятичных дробей на натуральное число.
44762. Оценка уровня качества телевизора «SAMSUNG» 260 KB
  Телевизор - электронное устройство для приёма и отображения изображения и звука, передаваемых по беспроводным каналам или по кабелю (в том числе телевизионных программ или сигналов от устройств воспроизведения видеосигнала - например, видеомагнитофонов).