UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75834
останнє поновлення: 2016-11-29
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваКвадратичні лишки (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось1225
Скачало279
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

.

 

Теорема. Нехай 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.

 

| = (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 ? Q7, 4 ? Q7 : 2 * 4 = 8 ? 1 ? Q7

 

: 5 * 6 = 30 ? 2 ? 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 ? Qn. Якщо x ? Zn* задовольняє x2 ? a (mod n), то x

називається квадратним коренем числа a за модулем n.

 

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

рівняння

 

x2 ? a (mod p)

 

(mod p).

 

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

 

Доведення теореми можна провести, використовуючи критерій Ейлера.

Оскільки a – квадратичний лишок за модулем p, то

 

(mod p) = 1

 

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

останньої рівності:

 

(mod p)

 

в Z11*.

 

= 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}.

 

0

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ