# Show the congruence $x^2 \equiv a \mod p^{k+1}$ has exactly two solutions...

Show that if $p$ is an odd prime, $p \nmid a$, and the congruence

$x^2 \equiv a \mod p^k$

has exactly the solutions $x \equiv \pm t \mod p^k$, then the congruence

$x^2 \equiv a \mod p^{k+1}$

has exactly two solutions, and that they are of the form $\equiv \pm(t + \ell \cdot p^k) \mod p^{k+1}$, where $\ell$ satisfies the congruence

$\ell \cdot 2t \equiv \frac{a - t^2}{p^k} \mod p.$

Hi, I'm stuck on this problem.

• Have you studied Hensel's lifting lemma? Oct 29, 2014 at 23:30
• @hardmath we have not.
– Ken
Oct 29, 2014 at 23:36

Hint: Let $q:=p^k$ and write $x=u\cdot q+t$ where $t<q$ and $u<p$, and take its square (modulo $p^{k+1}$).
• Thanks for your help, I get $u^{2}q^{2} + 2uqt + t^{2}$, which is equal to $u^{2}p^{2k} + 2utp^{2k} + t^{2}$ I don't understand what this means $\mod p^{k+1}$ though
• Well, as $k\ge 1$, $\ 2k\ge k+1$, so $p^{2k}$ gives remainder $0$ modulo $p^{k+1}$, so that $x^2\equiv 2uqt+t^2 \pmod{p^{k+1}}$. Now, given $a$ and $t$, such that $t^2\equiv a\pmod{q}$ we are looking for $u$ with which $x=uq+t$ satisfies $x^2\equiv a\pmod{pq}$. Oct 30, 2014 at 1:14
• @Berci This allows us to obtain a solution modulo $p^{k+1}$ from a solution modulo $p^{k}$, but how do we know that there are only $2$? Mar 26, 2016 at 12:27