Математика / Арифметика и теория чисел

Лемма Гензеля: подъём простого корня по степеням p

Лемма Гензеля позволяет уточнить корень сравнения от модуля pᵏ до pᵏ⁺¹. Если производная обратима по модулю p, нужная поправка определяется одним линейным сравнением.

Опубликовано: Обновлено:

Формула

$$r_{k+1}=r_k+t p^k,\qquad t\equiv-\frac{f(r_k)}{p^k}\bigl(f\prime(r_k)\bigr)^{-1}\pmod p$$
Схема Один класс и семь кандидатов
x ≡ 3 (mod 7)310172431384510² − 2 = 98 кратно 49

Из чисел, равных 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 делит значение многочлена; арифметика остаётся целочисленной и точной.

Как пользоваться формулой

  1. Проверьте, что p простое, k не меньше единицы и целое значение f(r) действительно кратно текущему модулю pᵏ.
  2. Вычислите целое частное f(r)/pᵏ до перехода к остаткам по модулю p, чтобы не потерять нужную цифру.
  3. Вычислите производную в r и найдите её обратный остаток по модулю p; если остаток нулевой, этот способ неприменим.
  4. Умножьте частное со знаком минус на обратный элемент, сократите результат по модулю p и прибавьте t·pᵏ к r.
  5. Подставьте уточнённый корень в исходный многочлен и проверьте целочисленную делимость на 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

Связанные формулы

Математика

Обратный элемент по модулю через расширенный алгоритм Евклида

$au+mv=1\quad\Longrightarrow\quad a^{-1}\equiv u\pmod m$

Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.

Математика

Критерий Эйлера для квадратичных вычетов

$\left(\frac ap\right)\equiv a^{(p-1)/2}\pmod p,\qquad \left(\frac ap\right)\in\{-1,0,1\}$

Чтобы узнать, имеет ли сравнение x² ≡ a решение по нечётному простому модулю p, достаточно вычислить степень a^((p−1)/2) по модулю p и прочитать её остаток.

Математика

Китайская теорема об остатках для двух взаимно простых модулей

$x\equiv r+m\bigl((s-r)m^{-1}\bmod n\bigr)\pmod{mn}$

Китайская теорема об остатках восстанавливает общий класс чисел по остаткам r и s при делении на взаимно простые m и n. Решение существует для любой пары остатков и единственно по модулю произведения mn.

Математика

Линейное сравнение: решения через НОД коэффициента и модуля

$ax\equiv b\pmod m\text{ разрешимо}\iff d\mid b,\quad d=\gcd(a,m);\quad x=x_0+k\frac md,\ k=0,\ldots,d-1$

Сравнение ax ≡ b по модулю m имеет решения тогда и только тогда, когда НОД(a,m) делит b. При выполнении условия получается ровно d разных классов по исходному модулю, где d — этот НОД.