6
$\begingroup$

Problem

Prove that $x^2 \equiv a \pmod{p}$ has solution if and only if $x^2 \equiv a \pmod{p^e}$ has solution.

I attempted to prove this by induction, but I was struggling with the proving the converse.
If $x^2 \equiv a \pmod{p^{e+1}}$ then $x^2 = a + kp^{e+1}$. Hence, $x^2 \equiv a \pmod{p^e}$ is straightforward. However, the converse drove me nuts. By assuming that $x^2 \equiv a \pmod{p^e}$, then I have $x^2 = a + kp^e$, take this number modulo $p^{e+1}$, I can't see how this becomes $a \pmod{p^e}$. I used calculator to generate many cases to see how the pattern worked, and I realized the key idea is in $k$. But I couldn't figure out how to bring $k$ up from $p^e$ to $p^{e+1}$. Any idea?

Thank you

  • 2
    Surely you are assuming $p$ is odd. Otherwise, take $p=2$, $a=3$, $e=2$.2011-04-13

2 Answers 2

6

You need to lift one solution to the next power. See Hensel's lemma.

Here is how to lift one solution $u$ of $x^2 \equiv a \pmod p$ to a solution $v$ of $x^2 \equiv a \pmod {p^2}$: Write $u^2=a+kp$ for some $k$. Consider $v=u+tp$ with $t$ to be determined. Then $v^2 = u^2+2utp+p^2 = a+kp+2utp+p^2$. So we need $t$ such that $k \equiv 2ut \bmod p$. Assuming $p$ odd and $a \not\equiv 0 \bmod p$, you can solve for $t$.

  • 0
    Thank you. To be honest, when asking, I hope the answer won't be Hensel's lemma. Don't know why I don't like this lemma at all :( !2011-04-13
  • 0
    @Chan, you can do the lifting without invoking Hensel's lemma. Several books do that.2011-04-13
6

For $p=2$, the result is not true: taking $p=2$, $a=3$, $e^2$, we have that $x^2 \equiv 3\pmod{2}$ has a solution (any odd integer), but $x^2\equiv 3\pmod{2^2}$ has no solutions.

If $\gcd(a,p)=p$ the result is also not necessarily true: take $a=p$; then $x^2\equiv p\pmod{p}$ has a solution, but $x^2\equiv p\pmod{p^2}$ does not, since $x$ would have to be a multiple of $p$, and hence $x^2\equiv 0\pmod{p^2}$.

If $a$ is restricted to lying in $\{0,1,\ldots,p-1\}$, then these two conditions don't matter: for $p=2$, it is clear that both $x^2\equiv 0\pmod{2^e}$ and $x^2\equiv 1\pmod{2^e}$ have solutions for all $e\gt 0$; and if $p$ is odd and $a=0$, then $x^2\equiv 0\pmod{p^e}$ has solutions for all $e\gt 0$.

So, in any case, we can restrict to the case where $p$ is odd and $\gcd(a,p)=1$. In particular, any solution to $x^2\equiv a\pmod{p}$ or to $x^2\equiv a \pmod{p^e}$ must be relatively prime to $p$.

For odd primes, the problem can be solved using Hensel's Lemma, but one does not actually need it; just pushing it through what you are trying to do will do it, if you figure out what you need out of $k$ for things to work out.

Suppose $b^2 \equiv a \pmod{p^r}$, and you want to find $k$ such that $(b+kp^r)^2\equiv a \pmod{p^{r+1}}$.

Doing simple squaring, you have $$b^2 + 2bkp^r + k^2p^{2r}\equiv b^2 +2bkp^r \pmod{p^{r+1}}.$$ Now, $b^2 = a + tp^r$ for some $t$, so we want $$tp^r + 2bkp^r = p^r(t+2bk)\equiv 0 \pmod{p^{r+1}}.$$ This is equivalent to asking that $$t + 2bk\equiv 0 \pmod{p}.$$

So pick $k$ with $k(2b) \equiv -t\pmod{p}$ (which can be done because both $b$ and $2$ are relatively prime to $p$), and we are done.

By the way: one way to think of Hensel's Lemma is that it is the modular version of Newton's Method for approximating roots.

In Newton's Method, if $f'(b)\neq 0$, then you can go from $b$ to $b - \frac{f(b)}{f'(b)}$ as the "next approximation". Hensel's Lemma works the same way: you need $f'(b)$ to not be zero modulo $p$. Here we are working with $f(x) = x^2-a$; as long as $p\neq 2$, the formal derivative is not identically zero, which suggests what to do.

Notice the similarity with Newton's method in what we did: if $f(x) = x^2 - a$, then $f'(x)=2x$, so $f'(b)=2b$, and $f(b) = b^2-a = tp^r$, so $$ b - \frac{f(b)}{f'(b)} = b - \frac{tp^r}{2b} = b + \left(\frac{-t}{2b}\right)p^r$$ and what we are going to do is take $b+kp^r$ with $k$ given by $$k(2b)\equiv -t\pmod{p};$$ that is, $k$ is congruent to $\frac{-t}{2b}$ modulo $p$; precisely $-\frac{f(b)}{f'(b)}$ modulo $p$.

  • 0
    @Arturo Magidin: Thank you. But could you explain this line $x^2 \equiv 3 \pmod{2}$?. I'm confused because from my understanding, $1, 0$ are the only remainders of $2$, right? How come the $3$ was there?2011-04-13
  • 0
    @Chan: When one writes $x\equiv y \pmod{n}$, one is saying that $x$, $y$, and $n$ are integers, and that $n$ divides $x-y$. Neither $x$ nor $y$ are restricted to being "remainders" (that is, we do **not** require $0\leq x,y\lt n$). So one can certainly write $x^2\equiv 3 \pmod{2}$. Since $3\equiv 1\pmod{2}$, you have that $x^2\equiv 3\pmod{2}$ if and only if $x^2\equiv 1\pmod{2}$, which is why $x^2\equiv 3\pmod{2}$ has a solution (take $x$ to be any odd integer). The proposition you are trying to prove does **not** restrict $a$ to be among $0$, $1,\ldots,p-1$ unless you omitted the condition.2011-04-13
  • 0
    @Arturo Magidin: very interesting point which I could never think of. Thanks a lot. The original problem was $n = 2^{a}.m$ where $m$ is odd and $(a, n) = 1$. So I really don't know these conditions could implicitly implies that a $p_i$ factor of $n$ must be less than $a$ or not. Once again, many thanks.2011-04-13
  • 0
    @Arturo Magidin: Another question is if $x^2 \equiv 3 \pmod{2}$, is this equivalent to $x^2 \equiv 1 \pmod{2}$ because $3 \equiv 1 \pmod{2}$?2011-04-13
  • 0
    @Chan: Yes. $\equiv\pmod{n}$ is an equivalence relation, so if $b\equiv c\pmod{n}$, then $a\equiv b\pmod{n}$ if and only if $a\equiv c\pmod{n}$.2011-04-13
  • 0
    @Arturo Magidin: Thanks again.2011-04-13
  • 0
    @Arturo Magidin: Hi there, I read your proof and I did not understand how did you go from $$(b + kp^r)^2 \equiv a \pmod{p^{r+1}}$$ to $$b^2 - 2bkp^r + k^2p^{2r}\equiv b^2 -2bkp^r \pmod{p^{r+1}}$$? Because $(b + kp^r)^2 = b^2 + 2bkp^r + k^2p^{2r}$. How did the minus come in, was it a typo?2011-04-14
  • 0
    And from $b^2 = a + tp^r$, did you plug $b^2$ into the equation $b^2 - 2bkp^r \pmod{p^{r+1}}$ because we want the solution to be $\equiv a$, hence we implicitly meant $tp^r - 2bkp^r$ divides $p^{r+1}$. I'm just guessing, please correct if I was wrong. Thank you.2011-04-14
  • 0
    @Chan: I got the sign wrong. Should be $+$; fixed.2011-04-14
  • 0
    @Chan: Your final comment ("implicitly meant") makes no sense to me. We know $b^2 =a +tp^r$, and we want $(b+kp^r)^2$ to be congruent to $a$ modulo $p^{r+1}$. That is, we want $p^{r+1}$ to divide $(b+kp^r)^2-a = (b+kp^r)^2 -(b^2 - tp^r) = 2bkp^r + k^2p^{2r}+tp^r$. This is the same as having $p$ divide $2bk + t$. This is **explicit**, not implicit, and we want it to be *multiple* of $p^{r+1}$, not a divisor.2011-04-15
  • 0
    @Arturo Magidin: Thanks, now I got it.2011-04-15