1
$\begingroup$

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.

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

1 Answer 1

Reset to default
1
$\begingroup$

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}$).

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – Ken
    Oct 29, 2014 at 23:35
  • $\begingroup$ 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}$. $\endgroup$
    – Berci
    Oct 30, 2014 at 1:14
  • $\begingroup$ ahh ok, that makes sense. Thanks! $\endgroup$
    – Ken
    Oct 30, 2014 at 1:22
  • $\begingroup$ @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$? $\endgroup$
    – H. Jackson
    Mar 26, 2016 at 12:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .