Квадратичні лишки
Означення. Число a ? Zn* називається квадратичним лишком або квадратом за модулем n, якщо існує таке x ? Zn*, що x2 ? a (mod n). Якщо такого x не існує, то число a називається квадратичним нелишком. Множина усіх квадратичних лишків за модулем n позначається через Qn, нелишків – через EMBED Equation.3 . За означенням 0 ??Zn*, отже 0 ? Qn та 0 ?? EMBED Equation.3 .
Теорема. Нехай 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, | EMBED Equation.3 | = (p - 1) / 2.
Тобто половина елементів Zp* є квадратичними лишками, а половина – ні.
Приклад. Число a = 3 є генератором Z7*. Степені a наведені у наступній таблиці
Звідси 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 та | EMBED Equation.3 | = 3 (p - 1)(q - 1) / 4.
Приклад. Нехай n = 21. Тоді |Q21| = (2 * 6) / 4 = 3, Q21 = {1, 4, 16},
| EMBED Equation.3 | =. (3 * 2 * 6) / 4 = 9, EMBED Equation.3 = {2, 5, 8, 10, 11, 13, 17, 19, 20}.
Означення. Нехай a ? Qn. Якщо x ? Zn* задовольняє x2 ? a (mod n), то x називається квадратним коренем числа a за модулем n.
Теорема. Нехай p – просте, p ? 3 (mod 4), a ? Qp. Тоді розв’язком рівняння
x2 ? a (mod p)
будуть числа r та -r, де r = EMBED Equation.3 (mod p).
Доведення. r2 ? EMBED Equation.3 (mod p) ? EMBED Equation.3 (mod p) ? EMBED Equation.3 (mod p) ? EMBED Equation.3 (mod p) ? a (mod p), оскільки за теоремою Ферма ap-1 (mod p) ??1.
Доведення теореми можна провести, використовуючи критерій Ейлера. Оскільки a – квадратичний лишок за модулем p, то
EMBED Equation.3 ? EMBED Equation.3(mod p) = 1
Враховуючи що число p можна подати у вигляді p = 4m + 3 для деякого натурального m, то EMBED Equation.3 = 2m + 1. Тобто EMBED Equation.3 = EMBED Equation.3 ? 1(mod p) , EMBED Equation.3? a (mod p). Візьмемо квадратний корінь лівої та правої частини останньої рівності:
EMBED Equation.3? ? EMBED Equation.3 (mod p)
Приклад. Обчислити EMBED Equation.3 та EMBED Equation.3 в Z11*.
p = 11 – просте, p ? 3 (mod 4), EMBED Equation.3 = 3.
EMBED Equation.3 : 53 (mod 11) ? 4. –4 ? 7 (mod 11).
Перевірка: 42 (mod 11) ? 5, 72 (mod 11) ? 5.
EMBED Equation.3 : 33 (mod 11) ? 5. –5 ? 6 (mod 11).
Перевірка: 52 (mod 11) ? 3, 62 (mod 11) ? 3.
Теорема. Нехай n = p * q, де p, q – непарні прості числа. Число а ? Zn* є квадратичним лишком за модулем n тоді і тільки тоді, коли а є квадратичним лишком за модулем p та q. Тобто
а ? Qn ? ?а ? Qp та а ? Qq
Звідси |Qn| = |Qp| * |Qq| = (p – 1)(q – 1) / 4.
Приклад. Нехай n = 21 = 3 * 7. а ? Q21 ? ?а ? Q3 та а ? 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}.