Take the 2-minute tour ×
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.

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

share|improve this question
2  
Surely you are assuming $p$ is odd. Otherwise, take $p=2$, $a=3$, $e=2$. –  Arturo Magidin Apr 13 '11 at 3:18
add comment

2 Answers

up vote 6 down vote accepted

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

share|improve this answer
    
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 :( ! –  Chan Apr 13 '11 at 2:57
    
@Chan, you can do the lifting without invoking Hensel's lemma. Several books do that. –  lhf Apr 13 '11 at 3:00
    
Many thanks ;) –  Chan Apr 13 '11 at 3:25
add comment

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

share|improve this answer
    
@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? –  Chan Apr 13 '11 at 4:43
    
@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. –  Arturo Magidin Apr 13 '11 at 4:48
    
@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. –  Chan Apr 13 '11 at 5:27
    
@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}$? –  Chan Apr 13 '11 at 19:39
    
@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}$. –  Arturo Magidin Apr 13 '11 at 19:48
show 6 more comments

Your Answer

 
discard

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.