Математика / Арифметика и теория чисел
Лемма Гензеля: подъём простого корня по степеням p
Лемма Гензеля позволяет уточнить корень сравнения от модуля pᵏ до pᵏ⁺¹. Если производная обратима по модулю p, нужная поправка определяется одним линейным сравнением.
Формула
Из чисел, равных 3 по модулю 7, только 10 удовлетворяет x² ≡ 2 по модулю 49.
Обозначения
- $f$
- Целочисленный многочлен, —
- $p$
- Простое число, —
- $k$
- Показатель известного модуля, —
- $r_k$
- Корень по модулю pᵏ, —
- $t$
- Поправка из классов по модулю p, —
- $(f\prime(r_k))^{-1}$
- Обратный элемент к значению производной по модулю p, —
Условия применения
f — многочлен с целыми коэффициентами, p — простое число, k ≥ 1. Исходное r должно удовлетворять f(r) ≡ 0 (mod pᵏ), а производная f′(r) не должна делиться на p. Тогда поправка t единственна по модулю p.
Ограничения
При нулевой по модулю p производной нельзя делить на неё. Подъём тогда может отсутствовать или допускать несколько поправок. Эта форма леммы продолжает один уже найденный простой корень и не заменяет поиск остальных корней по модулю p.
Подробное объяснение
Корень r по модулю pᵏ задаёт первые k цифр в системе счисления с основанием p, если взять его неотрицательный остаток. Корни по модулю pᵏ⁺¹, которые дают прежний r после сокращения, имеют вид r + tpᵏ для t от 0 до p−1. Нужно выбрать ровно одну следующую цифру.
Подставим этот вид в многочлен. Постоянный член разложения равен f(r), линейный — tpᵏf′(r). Все остальные члены содержат множитель p²ᵏ, который делится на pᵏ⁺¹ при k ≥ 1. Поэтому нелинейное сравнение на следующем шаге сводится к одной линейной поправке.
Оба оставшихся слагаемых уже делятся на pᵏ. После этого точного деления модуль уменьшается до p. Если f′(r) ненулевая по модулю p, у неё есть обратный остаток, и линейное сравнение даёт единственный t. Поскольку новый корень совпадает со старым по модулю p, производная сохраняет обратимость на следующем шаге.
Расчёт напоминает шаг метода Ньютона: поправка строится по значению функции и производной. Здесь не сравнивают расстояния между вещественными числами. Уточнение означает, что очередная степень p делит значение многочлена; арифметика остаётся целочисленной и точной.
Как пользоваться формулой
- Проверьте, что p простое, k не меньше единицы и целое значение f(r) действительно кратно текущему модулю pᵏ.
- Вычислите целое частное f(r)/pᵏ до перехода к остаткам по модулю p, чтобы не потерять нужную цифру.
- Вычислите производную в r и найдите её обратный остаток по модулю p; если остаток нулевой, этот способ неприменим.
- Умножьте частное со знаком минус на обратный элемент, сократите результат по модулю p и прибавьте t·pᵏ к r.
- Подставьте уточнённый корень в исходный многочлен и проверьте целочисленную делимость на pᵏ⁺¹.
Историческая справка
В конце XIX века Курт Гензель начал развивать арифметику p-адических чисел. Одна из идей состоит в том, чтобы изучать число через согласующиеся остатки по степеням простого p. Это делает задачу о корне многочлена последовательностью уточнений: каждый новый шаг оставляет без изменений уже найденные разряды. В опубликованном изложении Гензеля об арифметических свойствах чисел описаны p-адические числа и предшествующие работы о действиях над ними и корнях уравнений. Современные учебные формулировки разделяют конечный шаг и вывод о существовании корня в кольце p-адических целых. В приведённой здесь формуле достаточно целых чисел и одного перехода между соседними степенями.
Историческая линия формулы
Шаг носит имя Курта Гензеля и относится к его p-адическому подходу к уравнениям. В этой статье рассматривается частный вариант с обратимой производной: он даёт единственное уточнение заданного класса и служит строительным шагом для полной леммы.
Пример
Поднимем корень 3 сравнения x² ≡ 2 (mod 7) до модуля 49. Здесь f(x) = x²−2, p = 7 и k = 1; значение f(3) = 7 подтверждает исходное сравнение. Частное f(3)/7 = 1. Производная f′(3) = 6 даёт обратный остаток 6, так как 36 ≡ 1 (mod 7). Значит, t ≡ −1·6 ≡ 1 (mod 7), новый корень 3 + 1·7 = 10. Проверка: f(10) = 98 = 2·49. В ряду 3, 10, 17, 24, 31, 38, 45 это единственный корень по модулю 49: обратимая производная даёт единственную цифру t. Возможные корни, происходящие от других остатков по модулю 7, сюда не входят.
Частая ошибка
Сначала берут f(r) по модулю p вместо точного деления на pᵏ, из-за чего поправка беспричинно обнуляется. Делят на производную обычной дробью вместо взятия обратного остатка. Утверждают единственность среди всех корней по большому модулю, хотя лемма утверждает её только в исходном классе.
Практика
Задачи с решением
Ещё одна цифра
Условие. Продолжите корень 10 для x²−2 по модулю 343.
Решение. Частное 98/49 = 2. Производная 20 ≡ 6, обратный остаток 6; t ≡ −12 ≡ 2. Получаем 10 + 2·49 = 108. Проверка: 108²−2 = 11662 = 34·343.
Ответ. x ≡ 108 (mod 343).
Нулевая производная
Условие. Можно ли поднять корень 0 для x²−5 от модуля 5 до модуля 25?
Решение. Производная в 0 равна 0, поэтому формула простого подъёма неприменима. Любой кандидат 5t имеет квадрат, кратный 25, тогда как требуется остаток 5.
Ответ. Подъёма нет.
Дополнительные источники
- https://math.mit.edu/classes/18.782/2013fa/LectureNotes8.pdf
- https://gdz.sub.uni-goettingen.de/fulltext/PPN37721857X_0016/00000355?_format=xml
Связанные формулы
Математика
Обратный элемент по модулю через расширенный алгоритм Евклида
Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.
Математика
Критерий Эйлера для квадратичных вычетов
Чтобы узнать, имеет ли сравнение x² ≡ a решение по нечётному простому модулю p, достаточно вычислить степень a^((p−1)/2) по модулю p и прочитать её остаток.
Математика
Китайская теорема об остатках для двух взаимно простых модулей
Китайская теорема об остатках восстанавливает общий класс чисел по остаткам r и s при делении на взаимно простые m и n. Решение существует для любой пары остатков и единственно по модулю произведения mn.
Математика
Линейное сравнение: решения через НОД коэффициента и модуля
Сравнение ax ≡ b по модулю m имеет решения тогда и только тогда, когда НОД(a,m) делит b. При выполнении условия получается ровно d разных классов по исходному модулю, где d — этот НОД.