Квадратичні лишки, Детальна інформація
Квадратичні лишки
Реферат на тему:
Квадратичні лишки
.
Теорема. Нехай 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) \xF0BA\xF0201.
Доведення теореми можна провести, використовуючи критерій Ейлера. Оскільки a – квадратичний лишок за модулем p, то
Квадратичні лишки
.
Теорема. Нехай 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) \xF0BA\xF0201.
Доведення теореми можна провести, використовуючи критерій Ейлера. Оскільки a – квадратичний лишок за модулем p, то
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021