Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've always known the famous Hensel's lemma in number theory which allows us to lift solutions of an equation $f(x) \equiv 0 \pmod p$ to solutions modulo $p^n$ under non-degeneracy.

What about the following problem : if I start with a linear system of equations of the form $Px \equiv 0 \pmod p$ where $P$ is an $n \times n$ matrix with integer coefficients and $x = \begin{bmatrix} x_1, \dots, x_n \end{bmatrix}^{\top}$. Is there any way I can lift a solution $x \pmod p$ to a solution $\hat x \pmod {p^m}$ such that $\hat x \equiv x \pmod p$? I'd be more than happy to have an answer for $p^2$ and $n=2$ or $n=3$, if that's possible ; I'm usually working with matrices whose lines have one $2$ and two $1$'s, with the rest all zeros, such as this one : $$ \begin{bmatrix} 2 & 1 & 1 & 0 \\ 0 & 2 & 1 & 1 \\ 1 & 0 & 2 & 1 \\ 1 & 1 & 0 & 2 \\ \end{bmatrix} $$ (The reason for the symmetry is because this matrix arose from some nice knot in knot theory, but I don't think this context is relevant here.)

I could possibly be interested in a simple existence result, but I am way more interested in being able to count the number of solutions for a particular example, because that's what I need to do in my number-theoretic context ; an understanding of the shape of the solutions would be heaven. Either way, any kind of answer is appreciated as long as it gives some insight.

share|cite|improve this question
up vote 5 down vote accepted

You have found $x_0$ with $Px\equiv b\pmod p$. Make the ansatz $x=x_0+px_1$. Then $Px\equiv b\pmod{p^2}$ is equivalent to $Px_1\equiv \frac{b-Px_0}{p}\pmod{p}$ (where the division on the right hand side is possible by assumption). So you have to solve a linear equation mod $p$ again (though with different right hand side).

Your specific example $P$ is not invertible (rank is $n-1$), so it may depend: either you have no or you have $p$ solutions above a given one.

share|cite|improve this answer
Man. I feel humiliated I didn't give it a try myself. Thanks! That was helpful! – Patrick Da Silva Jul 21 '13 at 22:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.