Полный квадрат — понятие теории чисел¶
Полный квадрат (также полный квадратичный остаток) — это понятие теории чисел, связанное с квадратичными вычетами по модулю. В современной математике термин «полный квадрат» чаще всего используется в двух значениях: как квадрат целого числа (то есть число вида $n^2$) и как квадратичный вычет, который является квадратом некоторого элемента кольца вычетов. Оба значения тесно связаны между собой и находят применение в криптографии, теории Диофантовых уравнений и алгебраической теории чисел.
¶Полный квадрат как квадрат целого числа
В элементарном значении полным квадратом называется число, которое можно представить в виде $n^2$, где $n$ — целое число. Такие числа называются также квадратами натуральных чисел или полными квадратами в арифметике. Примеры: 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.
Квадраты обладают рядом свойств:
- квадрат любого целого числа неотрицателен;
- квадрат чётного числа делится на 4, квадрат нечётного числа имеет вид $8k+1$;
- разность между соседними квадратами $ (n+1)^2 - n^2 = 2n+1 $ — нечётное число;
- сумма первых $n$ нечётных чисел равна $n^2$ (законность этого факта часто используется как визуальное доказательство).
Проверка того, является ли число полным квадратом, выполняется за счёт извлечения квадратного корня и последующего возведения результата в квадрат. В вычислительной практике для больших чисел используются алгоритмы извлечения квадратного корня, например метод Ньютона.
¶Полный квадратичный вычет
В теории чисел более глубокое значение имеет понятие полного квадратичного вычета. Пусть $m > 1$ — целое число, а $a$ — целое, взаимно простое с $m$. Тогда $a$ называется квадратичным вычетом по модулю $m$, если существует целое $x$ такое, что $x^2 \equiv a \pmod{m}$. Если такого $x$ не существует, $a$ называется квадратичным невычетом.
Понятие «полный квадратичный вычет» иногда употребляется для обозначения вычета, который является квадратом в кольце вычетов $\mathbb{Z}/m\mathbb{Z}$, то есть принадлежит подгруппе квадратов мультипликативной группы. Для простого модуля $p$ число квадратичных вычетов среди чисел, взаимно простых с $p$, равно $(p-1)/2$.
¶Квадратичный символ Лежандра
Для простого модуля $p$ определяется квадратичный символ Лежандра:
$$\left(\frac{a}{p}\right) = \begin{cases} 1, & \text{если } a \text{ — квадратичный вычет по модулю } p, \\ -1, & \text{если } a \text{ — квадратичный невычет}, \\ 0, & \text{если } p \mid a. \end{cases}$$
Символ обладает свойством мультипликативности: $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$. Закон квадратичного взаимности, открытый Эйлером и Лежандром и доказанный Гауссом, устанавливает связь между символами $\left(\frac{p}{q}\right)$ и $\left(\frac{q}{p}\right)$ для различных простых $p$ и $q$ и является одним из фундаментальных результатов теории чисел.
¶Обобщения
Для составных модулей используются символ Якоби и символ Кронекера, которые обобщают символ Лежандра. Символ Якоби определяется через разложение модуля на простые множители и сохраняет мультипликативность, однако его значение $1$ не гарантирует, что число является квадратичным вычетом.
¶Применение
Понятие полного квадрата и квадратичных вычетов применяется в нескольких областях математики и информатики:
- Криптография. Алгоритмы, основанные на сложности извлечения квадратного корня по модулю составного числа (например, RSA), а также криптосистемы, использующие квадратичные вычеты (например, криптосистема Голдвахера — Микали), опираются на свойства квадратичных символов.
- Диофантовы уравнения. Условие существования целочисленных решений уравнения $x^2 \equiv a \pmod{m}$ является необходимым условием разрешимости ряда квадратичных уравнений.
- Алгебраическая теория чисел. Понятие квадратичного вычета обобщается на произвольные поля и кольца целостности, образуя основу теории квадратичных полей и классового поля.
¶Интересные факты
- Квадратичный символ Лежандра был введён Адриеном-Мари Лежандром в 1798 году в его «Опыте теории чисел».
- Закон квадратичного взаимности Карл Фридрих Гаусс назвал «золотым ключом теории чисел» и доказал его по крайней мере шестью различными способами.
- Проверка, является ли число полным квадратом, — одна из немногих арифметических операций, выполняемых за константное время на современных процессорах с помощью инструкции
SSE4.2-уровня и аналогичных.
¶Источники
- Новиков П. С. «Элементы теории чисел»
- Виноградов И. М. «Основы теории чисел»
- Лежандр А.-М. «Опыт теории чисел» (Essai sur la théorie des nombres, 1798)
- Гаусс К. Ф. «Арифметические исследования» (Disquisitiones Arithmeticae, 1801)
- Кнут Д. «Искусство программирования», том 2 (полуразрядные алгоритмы)
