2

What is the standard approach to solve $x^2=a\bmod p^2$ or more general $x^n = a\bmod p^n$ ?

Michael Hardy
  • 1
Ibrahim
  • 225

1 Answers1

1

The usual method for solving polynomial equations modulo $p^n$ is to solve it mod $p$, then use some method to extend a solution from mod $p$ to mod $p^2$, then to mod $p^3$, and so forth.

This can be done easily in an ad-hoc fashion: if you know that $f(a) = 0 \bmod p$, then you can make a new equation $f(a+px) = 0 \bmod p^2$ and solve it for $x$. If $f$ is a polynomial, we usually have

$$ f(a+px) = f(a) + px f'(a) \pmod{p^2}$$

so, as you can see, it's just solving a linear equation in this typical case. But you don't have to memorize differential approximation: just plug $a+px$ into $f$ and simplify it. This will result in something correct even when the above formula isn't true.

Sometimes, you have to solve an equation modulo $p^2$ (or worse) before you start getting unique extensions, and there can be other subtleties. But these problems manifest themselves clearly when you try to use the ad-hoc method. (e.g. $f'(a)$ will be zero modulo $p^2$)

A more systematic way to carry out this method is to use Hensel's lemma. This is essentially equivalent to use Newton's method for finding the roots of an equation, and is closely related to the $p$-adic numbers.