Знак Лежандра и символ Якоби

Определение и интуиция знака Лежандра

Знак Лежандра - $\displaystyle a^{\frac{p-1}{2}}\equiv\left(\frac{a}{p}\right)\pmod p$

Знак Лежандра вводится для описания того, является ли ненулевой остаток по простому модулю квадратом или нет. Это удобный способ сжато записывать информацию о квадратичных вычетах и работать с ними в теории чисел. Определение отражено в виде функции, принимающей значения трёх типов, и позволяет быстро использовать алгебраические свойства остатков.

Одно из важнейших равенств, связывающих знак Лежандра с возведением в степень, называется критерием Эйлера. Оно даёт практический способ вычисления знака через вычисление степеней по модулю.

$\displaystyle \left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$

Основные свойства и простые следствия

Знак Лежандра обладает рядом удобных свойств, которые делают его удобным инструментом. Во‑первых, он мультипликативен по аргументу: произведение двух аргументов даёт произведение соответствующих значений знака, это упрощает расчёты для сложных чисел.

$\displaystyle \left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$

Есть также явные формулы для значений знака Лежандра на специальных аргументах: для минус единицы и для двойки имеются компактные выражения, которые зависят только от арифметических свойств простого модуля p.

$\displaystyle \left(\frac{2}{p}\right)=(-1)^{\frac{p^{2}-1}{8}}$

$\displaystyle \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$

Квадратичная рекрипроцичность

Ключевым теоретическим результатом о квадратичных вычетах является закон квадратичной взаимности. Он устанавливает связь между знаками Лежандра для двух различных нечётных простых чисел и существенно упрощает вычисления знака при числе вида простого.

$\displaystyle \left(\frac{a}{n}\right)=\prod_{i=1}^{k}\left(\frac{a}{p_i}\right)^{e_i},\quad\text{где }n=\prod_{i=1}^{k}p_i^{e_i}$

Благодаря этому закону и вспомогательным результатам (формулам для {-1} и 2) можно свести вычисление знака для сложных оснований к более простым случаям. Применение закона рекрипроцичности часто идёт в связке с разложением числа на простые множители и использованием мультипликативности.

Практически это означает: чтобы вычислить знак Лежандра при большом аргументе, достаточно по возможности поменять местами модуль и основание, при этом появится поправочный множитель, вычисляемый по простой формуле, приведённой выше.

Символ Якоби: обобщение на составные модули

Символ Якоби - $\displaystyle \left(\frac{ab}{n}\right)=\left(\frac{a}{n}\right)\left(\frac{b}{n}\right)$

Символ Якоби расширяет понятие знака Лежандра на случай произвольного нечётного положительного нечётного модуля n, разложимого на простые множители. По определению он получается как произведение соответствующих значений знака Лежандра по простым делителям модуля (с учётом их кратностей), благодаря чему наследует многие удобные алгебраические свойства.

В частности, символ Якоби также мультипликативен по числу в числителе и по модулю. Это даёт формулы, аналогичные свойствам знака Лежандра и удобные для практических вычислений и теоретических рассуждений.

$\displaystyle a^{\frac{n-1}{2}}\equiv\left(\frac{a}{n}\right)\pmod n$

Отличия между знаком Лежандра и символом Якоби

Важное отличие состоит в том, что символ Якоби при значении $\displaystyle \left(\frac{a^{2}}{p}\right)=1\quad\text{при }\gcd(a,p)=1$ не гарантирует, что число действительно является квадратичным вычетом по модулю n, если n составное. То есть значение $\displaystyle \left(\frac{a^{2}}{p}\right)=1\quad\text{при }\gcd(a,p)=1$ для Jacobi не эквивалентно существованию квадратного корня по модулю n, а значение $\displaystyle \left(\frac{2}{9}\right)=\left(\frac{2}{3}\right)^{2}=1$ всё ещё означает, что число не сравнимо с нулём и не является квадратом в случае простого модуля.

Это отличие делает символ Якоби удобным для быстрой проверки «возможного» квадратичного характера, но при этом он не даёт полной информации для составных модулей. Тем не менее комбинация символа Якоби с вычислением степеней по модулю используется в алгоритмах тестирования простоты.

Применения: тесты на простоту и вычислительные методы

Критерий Эйлера и его обобщения служат основой для синтетических тестов на простоту. Для простых модулей p критическое равенство связывает возведённую в степень информацию с символом Якоби/Лежандра. В частном случае для простого p это именно критерий Эйлера; для произвольного n подобная формула используется в тесте Соловея — Штрассена как признак составности.

$\displaystyle 2^{3}\equiv1\pmod7$

Идея теста Соловея — Штрассена: выбирают случайное a с 1<a<n−1, вычисляют $\displaystyle 2^{3}\equiv1\pmod7$ и сравнивают с символом Якоби $\displaystyle \left(\frac{ab}{n}\right)=\left(\frac{a}{n}\right)\left(\frac{b}{n}\right)$. Если равенство не выполняется, то n составное; если выполняется для случайного набора оснований с высокой вероятностью n простое (вероятностный тест).

Дополнительные полезные свойства и замечания

Если число a взаимно просто с простым модулем p, то любая полная степень квадрата даёт тривиальное значение для знака Лежандра. Это записывается компактно и часто используется в доказательствах и преобразованиях при работе с символами.

{FORMULA_12}

При вычислениях полезно сочетать свойства: мультипликативность, критерий Эйлера, закон квадратичной взаимности и формулы для {-1} и 2. В практических задачах часто сначала раскладывают модуль на простые множители, затем применяют мультипликативность, а в конце используют рекурсивное снижение с помощью рекрипроцичности.

В учебных задачах полезно упражняться на примерах с малыми простыми числами и составными модулями для закрепления различий и свойств, а также для понимания того, какие утверждения обратимы, а какие — нет.