Математика / Арифметика и теория чисел
Критерий Эйлера для квадратичных вычетов
Чтобы узнать, имеет ли сравнение x² ≡ a решение по нечётному простому модулю p, достаточно вычислить степень a^((p−1)/2) по модулю p и прочитать её остаток.
Формула
Для ненулевых x достаточно проверить 1–6: остальные x дают те же квадраты с противоположным знаком корня.
Обозначения
- $a$
- Целое число под знаком квадрата, —
- $p$
- Нечётный простой модуль, —
- $\left(\frac ap\right)$
- Символ Лежандра: 1 для ненулевого квадрата, −1 для невычета, 0 для числа, кратного p, —
Условия применения
Модуль p должен быть нечётным простым числом, а a — целым. Для ненулевого остатка показатель (p−1)/2 положителен и цел. Если a делится на p, символ равен нулю и сравнение имеет решение x ≡ 0.
Ограничения
Для составного модуля тот же показатель не образует общего признака наличия квадратного корня. Степенной тест даёт только существование ненулевого корня при простом p; сами корни получают отдельным алгоритмом.
Подробное объяснение
У квадрата по модулю p есть обычное определение: существует остаток x, квадрат которого даёт a. Для ненулевого a символ Лежандра сводит ответ к двум значениям. Критерий Эйлера превращает вопрос о существовании x в вычисление одной степени, которое можно выполнить последовательным возведением в квадрат.
Если a ≡ x² и x не делится на p, то a^((p−1)/2) ≡ x^(p−1) ≡ 1 по малой теореме Ферма. Ненулевые остатки x разбиваются на пары x и −x с одинаковым квадратом. Других совпадений нет: из x² ≡ y² следует, что простое p делит x−y или x+y.
Таким образом, у многочлена X^((p−1)/2)−1 уже есть (p−1)/2 различных корней — все ненулевые квадраты. Степень ограничивает число корней над полем, поэтому ни один невычет не может дать единицу. При этом квадрат вычисленной степени равен 1 по теореме Ферма: у невычета остаётся значение −1.
В машинном расчёте отрицательный знак обычно представлен остатком p−1. Например, 6 для модуля 7 — это −1. Число 0 обрабатывают отдельно: его квадратный корень нулевой, но символ Лежандра не записывают равным 1, даже когда вопрос о разрешимости получает положительный ответ.
Как пользоваться формулой
- Проверьте, что p нечётно и просто: в доказательстве используется поле остатков, а не кольцо произвольного модуля.
- Замените a его остатком между 0 и p−1; если остаток нулевой, запишите символ 0 и корень x ≡ 0.
- Разложите показатель (p−1)/2 в сумму степеней двойки и вычислите нужные степени последовательным возведением в квадрат.
- Перемножьте выбранные остатки и приведите результат к виду 0, 1 или p−1; последнему соответствует символ −1.
Историческая справка
В исследованиях сравнений XVIII века учёные выясняли, когда целое число встречается среди квадратов по заданному модулю. Степенной признак носит имя Эйлера; компактная современная запись связывает его с символом Лежандра. В «Опыте о теории чисел» 1798 года Лежандр систематизировал задачи о делимости и квадратичных остатках. В «Арифметических исследованиях» 1801 года Гаусс посвятил квадратам по модулю отдельный раздел. Его изложение различает вычеты и невычеты, но записывает их не тем символом, который принят теперь. Современный справочник NIST помещает степенной критерий рядом с определением символа и законом взаимности; эти три записи отвечают на разные вопросы о квадратах по модулю.
Историческая линия формулы
Эйлеру приписывают степенной критерий, Лежандру — обозначение квадратичного характера простого модуля. Запись критерия через символ Лежандра — современное объединение этих элементов, а равенство классов остатков опирается ещё и на малую теорему Ферма.
Пример
Нужно решить, существует ли квадратный корень из 3 по модулю 13. Модуль прост, основание ненулевое, требуемый показатель равен (13−1)/2 = 6. Считаем с приведением после каждого умножения: 3² ≡ 9, 3⁴ ≡ 81 ≡ 3. Тогда 3⁶ ≡ 3·9 = 27 ≡ 1 (mod 13). Символ Лежандра равен 1, значит сравнение x² ≡ 3 (mod 13) разрешимо. Проверка другим способом: 4² = 16 даёт остаток 3; второе решение 9 тоже даёт этот остаток, потому что 9 ≡ −4. Эти корни получены проверкой квадратов, а из самой степени 3⁶ мы узнали лишь факт их существования. В задаче используются безразмерные целые числа.
Частая ошибка
Берут показатель p−1 и получают единицу для любого ненулевого основания: эта степень проверяет другое свойство. Читают остаток p−1 как отдельное значение символа: он представляет −1. Применяют признак к составному p без проверки, хотя доказательство подсчётом корней тогда уже не действует.
Практика
Задачи с решением
Проверка невычета
Условие. Есть ли корень у x² ≡ 2 по модулю 11?
Решение. Вычисляем 2⁵ = 32 ≡ 10 ≡ −1 (mod 11). По критерию Эйлера это невычет.
Ответ. Корней нет.
Кратное модулю
Условие. Найдите символ Лежандра для 34 по модулю 17.
Решение. Число 34 делится на 17, поэтому его класс нулевой. Квадрат нулевого класса равен нулю.
Ответ. Символ 0, единственный класс решения x ≡ 0.
Дополнительные источники
- https://dlmf.nist.gov/27.9
- https://www.e-rara.ch/zut/content/titleinfo/1089237
- https://www.math.uni-bielefeld.de/~sieben/h284_gauss_1801.pdf
Связанные формулы
Математика
Быстрое возведение в степень по модулю двоичным методом
Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ.
Математика
Малая теорема Ферма: степени по простому модулю
Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.
Математика
Закон квадратичной взаимности для двух простых чисел
Закон квадратичной взаимности связывает два символа Лежандра при перестановке нечётных простых чисел. Знак меняется, только если оба числа дают остаток 3 при делении на 4.
Математика
Символ Якоби по нечётному составному модулю
Символ Якоби перемножает символы Лежандра по простым множителям нечётного модуля. Значение −1 исключает квадрат, а значение 1 по составному модулю ещё требует проверки.