Квадратичні лишки

Реферат на тему:

Квадратичні лишки.

.

Теорема. Нехай p — непарне просте число, g — генератор Zp*. Тоді число a є квадратичним лишком за модулем p тоді і тільки тоді, коли a = gi (mod p), де i — парне ціле.

Доведення. Якщо a = g2k (mod p), то a = b2 (mod p), де b = gk (mod p).

Нехай a = gk (mod p) — елемент Zp*. Піднесемо його до квадрату:

a2 = g2k (mod p) xF0BA gi (mod p). Оскільки 2k (mod p — 1) = i — парне число, то звідси і випливає твердження про те що квадрат довільного елемента a xF0CE Zp* представляється у вигляді gi (mod p) лише для парного i.

| = (p — 1) / 2.

Тобто половина елементів Zp* є квадратичними лишками, а половина — ні.

Приклад. Число a = 3 є генератором Z7*. Степені a наведені у наступній таблиці.

I 0 1 2 3 4 5 6.

ai mod 7 1 3 2 6 4 5 1.

= {3, 5, 6}.

Схема множення кважратичних лишків та нелишків аналогічна схемі додавання парних та непарних цілих чисел:

лишок * лишок = лишок лишок * нелишок = нелишок нелишок * нелишок = лишок Приклад. Дослідимо операції множення лишків та нелишків в групі Z7*.

2 xF0CE Q7, 4 xF0CE Q7: 2 * 4 = 8 xF0BA 1 xF0CE Q7.

: 5 * 6 = 30 xF0BA 2 xF0CE Q7.

| = 3 (p — 1)(q — 1) / 4.

Приклад. Нехай n = 21. Тоді |Q21| = (2 * 6) / 4 = 3, Q21 = {1, 4, 16},.

= {2, 5, 8, 10, 11, 13, 17, 19, 20}.

Означення. Нехай a xF0CE Qn. Якщо x xF0CE Zn* задовольняє x2 xF0BA a (mod n), то x називається квадратним коренем числа a за модулем n.

Теорема. Нехай p — просте, p xF0BA 3 (mod 4), a xF0CE Qp. Тоді розв’язком рівняння.

x2 xF0BA a (mod p).

(mod p).

(mod p) xF0BA a (mod p), оскільки за теоремою Ферма ap-1 (mod p) xF0BAxF0201.

Доведення теореми можна провести, використовуючи критерій Ейлера. Оскільки a — квадратичний лишок за модулем p, то.

(mod p) = 1.

xF0BA a (mod p). Візьмемо квадратний корінь лівої та правої частини останньої рівності:

(mod p).

в Z11*.

= 3.

: 53 (mod 11) xF0BA 4. -4 xF0BA 7 (mod 11).

Перевірка: 42 (mod 11) xF0BA 5, 72 (mod 11) xF0BA 5.

: 33 (mod 11) xF0BA 5. -5 xF0BA 6 (mod 11).

Перевірка: 52 (mod 11) xF0BA 3, 62 (mod 11) xF0BA 3.

Теорема. Нехай n = p * q, де p, q — непарні прості числа. Число, а xF0CE Zn* є квадратичним лишком за модулем n тоді і тільки тоді, коли, а є квадратичним лишком за модулем p та q. Тобто, а xF0CE Qn xF0DB xF020а xF0CE Qp та, а xF0CE Qq.

Звідси |Qn| = |Qp| * |Qq| = (p — 1)(q — 1) / 4.

Приклад. Нехай n = 21 = 3 * 7. а xF0CE Q21 xF0DB xF020а xF0CE Q3 та, а xF0CE Q7.

Q3 = {1}, поширимо остачі до 21 за модулем 3: {1, 4, 7, 10, 13, 16, 19}.

Q7 = {1, 2, 4}, поширимо остачі до 21 за модулем 7: {1, 2, 4, 8, 9, 11, 15,16,18}.

|Q21| = |Q3| * |Q7| = 1 * 3 = 3. Числа, спільні в двох множинах поширених остач, і є квадратичними лишками за модулем 21.

Q21 = {1, 4, 16}.