Открыть сервисСервис

Полный квадрат — понятие теории чисел

Полный квадрат (также полный квадратичный остаток) — это понятие теории чисел, связанное с квадратичными вычетами по модулю. В современной математике термин «полный квадрат» чаще всего используется в двух значениях: как квадрат целого числа (то есть число вида $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 (полуразрядные алгоритмы)
Заметили ошибку или не согласны с информацией в статье? Напишите нам support@bfometr.ru