Номер 11, страница 361 - гдз по алгебре 9 класс учебник Мерзляк, Поляков

Проектная работа - номер 11, страница 361.

Условие.

11. Квадратичные вычеты и невычеты. Квадратичный закон взаимности Гаусса

Рекомендуемые литература и интернет-ресурсы

1) Виноградов И. М. Основы теории чисел. — М. : Высшая школа, 1999.

2) Дэвенпорт Г. Высшая арифметика. — М. : Наука, 1965.

3) Заславский А. А. и др. Математика в задачах. — М. : МЦНМО, 2009.

4) Прасолов В. В. Задачи по алгебре, арифметике и анализу. — М. : МЦНМО, 2007.

5) Спивак А. В. Арифметика. — М. : Бюро Квантум, 2007.

6) Эвнин А. Ю. Задачи по дискретной математике. — М. : Книжный дом «ЛИБРОКОМ», 2011.

7) http://www.uic.unn.ru/~zny/compalg/Lectures/ca_02_quadraticresidue.pdf Квадратичные вычеты и невычеты

8) http://www.mathnet.ru/php/presentation.phtml?option_lang=rus&presentid=383 Арнольд В. И. Случайны ли квадратичные вычеты?

Решение.

Квадратичные вычеты и невычеты

Пусть $p$ — нечётное простое число. Целое число $a$, не делящееся на $p$ (то есть, $a \not\equiv 0 \pmod{p}$), называется квадратичным вычетом по модулю $p$, если сравнение $x^2 \equiv a \pmod{p}$ имеет решение. Если это сравнение не имеет решений, то $a$ называется квадратичным невычетом по модулю $p$.

Например, найдём квадратичные вычеты по модулю 7. Для этого вычислим квадраты всех ненулевых остатков по модулю 7:

• $1^2 \equiv 1 \pmod{7}$
• $2^2 \equiv 4 \pmod{7}$
• $3^2 = 9 \equiv 2 \pmod{7}$
• $4^2 = 16 \equiv 2 \pmod{7}$
• $5^2 = 25 \equiv 4 \pmod{7}$
• $6^2 = 36 \equiv 1 \pmod{7}$

Таким образом, квадратичными вычетами по модулю 7 являются числа 1, 2, 4. Квадратичными невычетами — числа 3, 5, 6. Среди чисел $1, 2, \dots, p-1$ всегда имеется ровно $(p-1)/2$ квадратичных вычетов и $(p-1)/2$ квадратичных невычетов.

Для удобства работы с квадратичными вычетами вводится символ Лежандра $(\frac{a}{p})$: $$ \left(\frac{a}{p}\right) = \begin{cases} 1, & \text{если } a \text{ — квадратичный вычет по модулю } p \\ -1, & \text{если } a \text{ — квадратичный невычет по модулю } p \\ 0, & \text{если } a \equiv 0 \pmod{p} \end{cases} $$

Важнейшим свойством символа Лежандра является критерий Эйлера, который гласит, что для нечётного простого $p$ и целого $a$, не кратного $p$: $$ \left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p} $$ Из этого критерия, в частности, следует мультипликативность символа Лежандра: $(\frac{ab}{p}) = (\frac{a}{p})(\frac{b}{p})$.

Ответ: Квадратичный вычет $a$ по модулю простого числа $p$ — это число, для которого разрешимо сравнение $x^2 \equiv a \pmod{p}$. В противном случае $a$ — квадратичный невычет. Символ Лежандра $(\frac{a}{p})$ принимает значения 1, -1 или 0 в зависимости от того, является ли $a$ квадратичным вычетом, невычетом или кратным $p$.

Квадратичный закон взаимности Гаусса

Квадратичный закон взаимности, открытый Гауссом, устанавливает глубокую и неочевидную связь между разрешимостью сравнений $x^2 \equiv p \pmod{q}$ и $x^2 \equiv q \pmod{p}$ для двух различных нечётных простых чисел $p$ и $q$.

Формулировка закона: Пусть $p$ и $q$ — различные нечётные простые числа. Тогда справедливо равенство: $$ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \frac{q-1}{2}} $$ Это означает, что:

• Если хотя бы одно из чисел $p$ или $q$ имеет вид $4k+1$, то $(\frac{p}{q}) = (\frac{q}{p})$.
• Если оба числа $p$ и $q$ имеют вид $4k+3$, то $(\frac{p}{q}) = -(\frac{q}{p})$.

Закон взаимности дополняется двумя утверждениями для символов Лежандра от -1 и 2:

Первое дополнение (для -1): $$ \left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} = \begin{cases} 1, & \text{если } p \equiv 1 \pmod{4} \\ -1, & \text{если } p \equiv 3 \pmod{4} \end{cases} $$

Второе дополнение (для 2): $$ \left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} = \begin{cases} 1, & \text{если } p \equiv 1 \text{ или } 7 \pmod{8} \\ -1, & \text{если } p \equiv 3 \text{ или } 5 \pmod{8} \end{cases} $$

Эти правила позволяют эффективно вычислять символ Лежандра $(\frac{a}{p})$, раскладывая числитель $a$ на простые множители и последовательно "переворачивая" символы.

Пример. Вычислим $(\frac{29}{43})$.

Числа 29 и 43 — простые. $29 = 4 \cdot 7 + 1$, $43 = 4 \cdot 10 + 3$. Так как $29 \equiv 1 \pmod{4}$, по закону взаимности: $$ \left(\frac{29}{43}\right) = \left(\frac{43}{29}\right) $$ Упрощаем числитель по модулю знаменателя: $43 \equiv 14 \pmod{29}$. $$ \left(\frac{43}{29}\right) = \left(\frac{14}{29}\right) $$ Используем мультипликативность: $14 = 2 \cdot 7$. $$ \left(\frac{14}{29}\right) = \left(\frac{2}{29}\right) \left(\frac{7}{29}\right) $$ Вычислим каждый множитель отдельно.

Для $(\frac{2}{29})$: $29 = 8 \cdot 3 + 5$, т.е. $29 \equiv 5 \pmod{8}$. По второму дополнению, $(\frac{2}{29}) = -1$.

Для $(\frac{7}{29})$: $29 \equiv 1 \pmod{4}$, значит $(\frac{7}{29}) = (\frac{29}{7})$. Упрощаем: $29 = 4 \cdot 7 + 1$, т.е. $29 \equiv 1 \pmod{7}$. $$ \left(\frac{29}{7}\right) = \left(\frac{1}{7}\right) = 1 $$ (поскольку 1 всегда является квадратом).

Собираем результат: $$ \left(\frac{29}{43}\right) = (-1) \cdot 1 = -1 $$ Следовательно, 29 является квадратичным невычетом по модулю 43.

Ответ: Квадратичный закон взаимности Гаусса связывает значения символов Лежандра $(\frac{p}{q})$ и $(\frac{q}{p})$ для различных нечётных простых $p$ и $q$. Вместе с двумя дополнениями (для $(\frac{-1}{p})$ и $(\frac{2}{p})$) он предоставляет полный алгоритм для вычисления любого символа Лежандра, а значит, и для определения, является ли число квадратичным вычетом по заданному простому модулю.