| Головна » Статті » Математика | [ Додати статтю ] |
Квадратичні лишки - реферат українською
|
Означення. Число 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 наведені у наступній таблиці I 0 1 2 3 4 5 6 ai mod 7 1 3 2 6 4 5 1 Звідси 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. Теорема. Нехай p – просте, p 3 (mod 4), a Qp. Тоді розв’язком рівняння x2 a (mod p) будуть числа r та -r, де r = (mod p). Доведення. r2 (mod p) (mod p) (mod p) (mod p) a (mod p), оскільки за теоремою Ферма ap-1 (mod p) 1. Доведення теореми можна провести, використовуючи критерій Ейлера. Оскільки a – квадратичний лишок за модулем p, то (mod p) = 1 Враховуючи що число p можна подати у вигляді p = 4m + 3 для деякого натурального m, то = 2m + 1. Тобто = 1(mod p) , a (mod p). Візьмемо квадратний корінь лівої та правої частини останньої рівності: (mod p) Приклад. Обчислити та в Z11*. p = 11 – просте, p 3 (mod 4), = 3. : 53 (mod 11) 4. –4 7 (mod 11). Перевірка: 42 (mod 11) 5, 72 (mod 11) 5. : 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}. | |
| Переглядів: 504 | |
| Всього коментарів: 0 | |