Hensel Lifting

Suppose you want a square root of $2$, but only working modulo a prime $p$. Mod $7$, that's easy: $3^2 = 9 \equiv 2 \pmod 7$. So $x = 3$ solves $x^2 \equiv 2 \pmod 7$.

Now raise the stakes: can you solve $x^2 \equiv 2 \pmod{49}$? Mod $2401$ ($7^4$)? You could search by brute force, but there is a much sharper tool. Hensel lifting takes the solution you already have mod $p$ and repairs it into a solution mod $p^2$, then mod $p^4$, then mod $p^8$ — with the number of correct "digits" (in base $p$) roughly doubling at every step.

It is, quite literally, Newton's method transplanted from real numbers into the world of modular arithmetic — and it is one of the workhorses behind how computers factor polynomials and reason about numbers modulo prime powers.

Below, $x = 3$ already solves $x^2 \equiv 2 \pmod 7$. Press Lift one step and watch the same root get promoted to a solution modulo $7^2$, then $7^4$, then $7^8$ — each click roughly doubles how many base-$7$ digits of the true $\sqrt{2}$-like value are locked in.

<p class="hint">{{hint_para}}</p>
<div class="stage">
  <div class="row"><span class="lbl">{{lbl_modulus}}</span><span id="modulus" class="val">7</span></div>
  <div class="row"><span class="lbl">{{lbl_root}}</span><span id="root" class="val">3</span></div>
  <div class="row"><span class="lbl">{{lbl_check}}</span><span id="check" class="val">x² − 2 ≡ 0</span></div>
</div>
<div class="ladder" id="ladder"></div>
<div class="status" id="status">{{status_start}}</div>
<div class="btns">
  <button id="lift" type="button">{{btn_lift}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.stage { display: flex; flex-direction: column; gap: .3rem; background: #eef2f6; border: 1px solid #cdd9e3;
         border-radius: 8px; padding: .6rem .8rem; margin-bottom: .6rem; }
.row { display: flex; justify-content: space-between; font: 600 14px ui-monospace, monospace; }
.lbl { color: #445; font: 600 13px system-ui, sans-serif; }
.val { color: #1d3557; }
.ladder { display: flex; flex-direction: column-reverse; gap: .3rem; margin: .5rem 0; max-height: 190px;
          overflow-y: auto; }
.step { display: flex; justify-content: space-between; gap: .6rem; font: 600 13px ui-monospace, monospace;
        background: #fff; border: 1px solid #dbe2e8; border-radius: 6px; padding: .3rem .6rem;
        animation: appear .25s ease-out; }
.step .mod { color: #457b9d; }
.step .x { color: #1d3557; }
@keyframes appear { from { opacity: 0; transform: translateY(4px); } to { opacity: 1; transform: translateY(0); } }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.done { color: #6a4c93; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }

// Code not found

Notice what never happens: the algorithm never throws away the previous answer and starts over. It reuses the current root $x$, computes how wrong $f(x) = x^2 - 2$ still is, and nudges $x$ by an amount that cancels that error modulo a much larger power of $p$. That reuse is exactly what makes lifting so fast compared to searching from scratch at each new modulus.

Hensel lifting is a solved, constructive method — there is no open question here, just a beautiful piece of 20th-century algebra due to Kurt Hensel (1897, 1904). Here is why it works and why it is fast.

• The starting condition. You need a simple root: some $x_0$ with $f(x_0) \equiv 0 \pmod p$ and $f'(x_0) \not\equiv 0 \pmod p$ (the derivative doesn't vanish). That non-vanishing derivative is what guarantees the root can be lifted uniquely at every stage.
• The lifting step. Given a root $x_k$ valid modulo $p^k$, define

  $$x_{k+1} = x_k - f(x_k)\cdot f'(x_k)^{-1} \pmod{p^{2k}}$$

  where the inverse of $f'(x_k)$ is taken modulo $p^{2k}$ (it exists precisely because $f'(x_0) \not\equiv 0 \pmod p$). This is exactly Newton's update rule $x - f(x)/f'(x)$, just computed with modular inverses instead of real division.
• Quadratic convergence. If $f(x_k) \equiv 0 \pmod{p^k}$, a short Taylor-expansion argument shows $f(x_{k+1}) \equiv 0 \pmod{p^{2k}}$. The precision doubles every step: $p \to p^2 \to p^4 \to p^8 \to \dots$ — reaching $p^{1024}$ takes only about ten steps, not a thousand.
• Cost per step. Each lift is one polynomial evaluation plus one modular inverse computed via the extended Euclidean algorithm — cheap, and independent of how large the target modulus eventually gets.

The one thing lifting cannot do is manufacture a root that isn't there: if $f$ has no root mod $p$, or the derivative vanishes at every root (a repeated root), the simple version of the lemma does not apply and a more delicate analysis is needed.

Lifting a solution instead of re-deriving it from nothing shows up anywhere numbers modulo a prime power need to be pinned down precisely:

• Polynomial factorization. The Zassenhaus and later LLL-based factoring algorithms first factor a polynomial modulo a small prime $p$ — cheap and reliable — then Hensel-lift that factorization to modulo $p^k$ for $k$ large enough to reconstruct the true integer factors.
• p-adic numbers. A compatible sequence of roots mod $p, p^2, p^4, \dots$ is, by construction, a single p-adic number — Hensel's lemma is the classical tool for showing an equation has a solution in $\mathbb{Z}_p$.
• Cryptography and coding theory. Arithmetic over rings $\mathbb{Z}/p^k\mathbb{Z}$ appears in some lattice-based and code-based schemes, where lifting square roots or inverses through increasing powers of $p$ avoids recomputing from scratch.
• Numerical algorithms in computer algebra. Whenever an exact integer or rational answer is reconstructed from modular data (rational reconstruction, Gröbner basis computations), lifting through prime powers is the standard way to get enough precision cheaply.

It's the same idea as Newton's method for real roots, just replaying inside modular arithmetic instead of the real line.

Hensel lifting turns a single lucky guess modulo a prime into an entire tower of increasingly precise answers, each one built cheaply from the last. No brute-force search modulo $p^{100}$ is ever needed — just repeated applications of the same tiny Newton-style correction.

It is a quiet reminder that "solved modulo a small number" and "solved exactly" are sometimes only a handful of doubling steps apart, the same spirit that drives Newton's method everywhere else in computation.