Квадратичні лишки, Детальна інформація

(mod p) = 1

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

(mod p)

в Z11*.

= 3.

: 53 (mod 11) \xF0BA 4. –4 \xF0BA 7 (mod 11).

Перевірка: 42 (mod 11) \xF0BA 5, 72 (mod 11) \xF0BA 5.

: 33 (mod 11) \xF0BA 5. –5 \xF0BA 6 (mod 11).

Перевірка: 52 (mod 11) \xF0BA 3, 62 (mod 11) \xF0BA 3.

Теорема. Нехай n = p * q, де p, q – непарні прості числа. Число а \xF0CE Zn* є квадратичним лишком за модулем n тоді і тільки тоді, коли а є квадратичним лишком за модулем p та q. Тобто

а \xF0CE Qn \xF0DB \xF020а \xF0CE Qp та а \xF0CE Qq

Звідси |Qn| = |Qp| * |Qq| = (p – 1)(q – 1) / 4.

Приклад. Нехай n = 21 = 3 * 7. а \xF0CE Q21 \xF0DB \xF020а \xF0CE Q3 та а \xF0CE 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}.