Математика / Арифметика и теория чисел
Символ Якоби по нечётному составному модулю
Символ Якоби перемножает символы Лежандра по простым множителям нечётного модуля. Значение −1 исключает квадрат, а значение 1 по составному модулю ещё требует проверки.
Формула
Сравнение по модулю 15 невозможно уже по модулю 3. Положительный знак произведения этого не показывает.
Обозначения
- $n$
- Положительный нечётный модуль, —
- $a$
- Верхний целый аргумент, —
- $p_j$
- Различные простые делители n, —
- $e_j$
- Показатели простых множителей, —
- $r$
- Число различных простых делителей, —
Условия применения
Нижний аргумент n — положительное нечётное целое; для n = 1 по соглашению берут пустое произведение 1. Формула по разложению учитывает кратности простых множителей. Интерпретация знака как необходимого признака квадрата при +1 относится к числам a, взаимно простым с n.
Ограничения
По символу +1 нельзя заключить, что a является квадратом, если n составное. Ноль говорит об общем делителе, но сам по себе не отличает квадрат от невычета. Чётный модуль требует другого определения, например более общего символа Кронекера.
Подробное объяснение
Символ Лежандра работает над одним простым модулем. Символ Якоби собирает несколько таких проверок в одно число из множества {−1, 0, 1}. Он совпадает с символом Лежандра при простом нижнем аргументе, но при составном аргументе отдаёт лишь произведение знаков.
Если a взаимно просто с n и x² ≡ a по модулю n, то то же сравнение выполняется для каждого простого делителя. Все множители равны 1, и произведение тоже равно 1. Обратный ход теряет сведения: два отрицательных знака дают плюс, как и одна отрицательная величина, возведённая в чётную степень.
При ненулевом символе кратность важна только по модулю 2. Если хотя бы один символ Лежандра нулевой, произведение равно нулю при любой положительной кратности. Поэтому проверять общий делитель полезно до работы со знаками: случай нуля имеет иной смысл, чем несовпадение квадратов среди обратимых остатков.
Разложение используют здесь для понимания и небольших ручных расчётов. Сам символ можно вычислять и без факторизации n: закон взаимности для символов Якоби, выделение степеней двойки и уменьшение аргументов дают алгоритм, похожий на алгоритм Евклида. Но даже быстрый расчёт не возвращает потерянные сведения об отдельных множителях.
Как пользоваться формулой
- Проверьте, что n положительно и нечётно; при n = 1 запишите 1, а в других случаях разложите n на простые степени.
- Сведите числитель a по каждому простому модулю отдельно, сохраняя показатель соответствующего простого множителя.
- Найдите каждый символ Лежандра по таблице квадратов, критерию Эйлера или правилам взаимности простых чисел.
- Возведите множители в нужные степени и перемножьте; если вышло +1, не объявляйте составное сравнение разрешимым.
Историческая справка
К началу XIX века квадратные сравнения с простым модулем уже систематически изучали Лежандр и Гаусс. В «Арифметических исследованиях» Гаусса 1801 года существенна классификация по квадратам и невычетам. Якоби расширил обозначение Лежандра на нечётные составные нижние аргументы; это расширение относится к первой половине XIX века. В современной записи удобно определить новое значение сразу произведением по простым степеням. Тем самым сохраняется возможность применять закон взаимности к паре нечётных аргументов, даже если они не простые. Меняется смысл положительного результата: вычислительная экономия достигается за счёт объединения нескольких ответов в один знак.
Историческая линия формулы
Имя Якоби закрепилось за расширением символа Лежандра на положительные нечётные нижние аргументы. Современная формула через простые степени описывает это расширение: она сохраняет произведение квадратичных характеров и не переносит на составной случай критерий существования корня.
Пример
Проверим, позволяет ли символ Якоби признать число 2 квадратом по модулю 15. Разложение 15 = 3·5 содержит два различных нечётных простых множителя. По модулю 3 ненулевые квадраты дают только 1, значит (2/3) = −1. По модулю 5 ненулевые квадраты дают 1 и 4, значит (2/5) = −1. Тогда (2/15) = (−1)(−1) = 1. Корня при этом нет: из x² ≡ 2 (mod 15) следовало бы x² ≡ 2 (mod 3), а это невозможно. Так проверка по одному простому делителю выявляет потерянный при умножении знак. Символ и остатки — безразмерные числа.
Частая ошибка
Принимают значение 1 за доказательство наличия корня. Пропускают показатели степеней и получают неверный знак для повторяющегося простого. Считают значение 0 синонимом невычета: например, 9 — квадрат по модулю 15, хотя имеет с модулем общий делитель и нулевой символ.
Практика
Задачи с решением
Вклад кратности
Условие. Вычислите (2/45) при 45 = 3²·5.
Решение. Получаем (2/3)²(2/5) = (−1)²(−1) = −1. Квадрат, взаимно простой с 45, дал бы +1.
Ответ. Символ −1; квадратного корня из 2 нет.
Нулевой символ
Условие. Вычислите (9/15) и проверьте наличие корня.
Решение. Получаем (9/3) = 0 и (9/5) = (4/5) = 1. Произведение нулевое. При этом 3² = 9.
Ответ. Символ 0; один из корней x ≡ 3 (mod 15).
Дополнительные источники
- https://dlmf.nist.gov/27.9
- https://crypto.stanford.edu/pbc/notes/numbertheory/quadrecip.html
- https://www.math.uni-bielefeld.de/~sieben/h284_gauss_1801.pdf
- https://www.lehigh.edu/~shw2/q-recip/jacobi-legendre.pdf
Связанные формулы
Математика
Критерий Эйлера для квадратичных вычетов
Чтобы узнать, имеет ли сравнение x² ≡ a решение по нечётному простому модулю p, достаточно вычислить степень a^((p−1)/2) по модулю p и прочитать её остаток.
Математика
Закон квадратичной взаимности для двух простых чисел
Закон квадратичной взаимности связывает два символа Лежандра при перестановке нечётных простых чисел. Знак меняется, только если оба числа дают остаток 3 при делении на 4.
Математика
Китайская теорема об остатках для двух взаимно простых модулей
Китайская теорема об остатках восстанавливает общий класс чисел по остаткам r и s при делении на взаимно простые m и n. Решение существует для любой пары остатков и единственно по модулю произведения mn.