Тема 3. Теорія порівнянь.

3.11 Порівняння другого степеня, квадратичні лишки і квадратичні нелишки, символ Лежандра.

1. Звести порівняння другого степеня 4x²  11x  3  0(mod13) до двочленного.

Р о з в' я з а н н я. Для простого модуля старший коефіціент взаємно простий з ним. Тоді процес зведення заданого порівняння до двочленного можна скоротити і навіть залишити модуль незмінним. Визначимо множник k так, щоб .

Матимемо k = 10(mod13). Домножаючи обидві частини заданого порівняння на 10 за модулем 13, дістаємо

40x²  110x – 30  0(mod13),

або

x² – 6x – 4  0(mod 13). (1)

Виділимо в лівій частині цієї порівняння повний квадрат

x²  2·3x + 9 – 9 – 4  0(mod13).

або

(x  3)² – 13  0(mod13),

Остаточно

(x  3)²  0(mod13).

Зауваження

1. При розв'язуванні задач такого типу треба намагатися спростити процес виділення повного квадрату, для цього є різні способи. Зокрема, у розглянутому прикладі від заданого порівняння можна було б перейти до такого порівняння:

4x² – 24x – 16 (mod13) (2)

Оскількі (4, 13) = 1, то на 4 можна скоротити обидві частини порівняння (2):

x² – 6x – 4  0(mod13).

Дістали порівняння (1).

2. Часто процес зведення порівняння до двочленного завершується простим розв'язанням його. Так,

x – 3  0(mod13), або x  3(mod13).

2. Скільки розв'язків має порівняння x²  219(mod383)?

Р о з в' я з а н н я. Знайдемо символ Лежандра . Оскільки 219 = 3·73, а 383 – просте число, то, згідно з властивістю 5,

.

Обчислимо окремо символи Лежандра і . Оскільки 3 і 383 – різні прості непарні числа, то внаслідок закону взаємності 9, дістаємо

.

За властивістю 1) маємо , бо 383  2(mod3).

За властивістю 8)

.

Отже, . Щоб спростити запис, а також полегшити процес перевірки, доцільно при кожному переході під знаком рівності ставити номер властивості, на основі якої відбувається цей перехід. Наприклад,

.

1. Остаточно

.

Таким чином, задане порівняння має два розв'язки.

4. Зауваження

1. Слід уважно застосовувати властивість 9), оскільки якщо хоч одне з чисел p чи q є складеним, застосування цієї властивості може призвести до помилок в обчислені символу Лежандра.

2. Розглядаючи символ Лежандра як окремий випадок символу Якобі і користуючись властивостями останнього, можна символ Лежандра обчислити швидше.

Наприклад

3. Зауважимо, що коли p – просте непарне число, то символ Лежандра є для порівняння x²  a(mod p) символом Якобі і навпаки. Тому для порівнянь за простим модулем можна не розрізняти символів Лежанлра і Якобі, що дає змогу при обчисленні символіві Лежандра не розкладати чисельник на прості співмножники. Треба тільки виділяти множники, що дорівнюють 2. Якщо , то це порівняння має два розв’язки; якщо , порівняння розв’язків не має. Для порівняння , де m – непарне складене число, символ Лежандра не існує, а символ Якобі існує. Проте, якщо символ Якобі і m – непарне складене число, то це ще не означає, що порівняння має розв’язки. Так порівняння розв’язків не має, а символ Якобі для неї .

Тема 4. ПервІснІ коренІ, Індекси та характери.