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

Означення. Число a Zn* називається квадратичним лишком або квадратом за модулем n, якщо існує таке x Zn*, що x2 a (mod n). Якщо такого x не існує, то число a називається квадратичним нелишком. Множина усіх квадратичних лишків за модулем n позначається через Qn, нелишків – через . За означенням 0 Zn*, отже 0 Qn та 0 .

Теорема. Нехай 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)  gi (mod p). Оскільки 2k (mod p – 1) = i – парне число, то звідси і випливає твердження про те що квадрат довільного елемента a Zp* представляється у вигляді gi (mod p) лише для парного i.

Наслідок. | Qp | = (p - 1) / 2, | | = (p - 1) / 2.

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

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

I0123456

ai mod 71326451

Звідси Q7 = {1, 2, 4}, = {3, 5, 6}.

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

лишок * лишок = лишок

лишок * нелишок = нелишок

нелишок * нелишок = лишок

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

2 Q7, 4 Q7 : 2 * 4 = 8 1 Q7

2 Q7, 5 : 2 * 5 = 10 3

5 , 6 : 5 * 6 = 30 2 Q7

Твердження. Нехай n – добуток двох різних простих чисел p та q, n = p * q. Тоді число a  Zn* є квадратичним лишком за модулем n тоді і тільки тоді, коли a Qp та a Qq. Звідси |Qn| = |Qp| * |Qq| = (p - 1)(q - 1) / 4 та | | = 3 (p - 1)(q - 1) / 4.

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

| | =. (3 * 2 * 6) / 4 = 9, = {2, 5, 8, 10, 11, 13, 17, 19, 20}.

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