Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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 heard the statement from the title of this question. $\newcommand{\of}[1]{\left(#1\right)}$ $\newcommand{\df}{\mathrel{\mathop:}=}$

So if I am not totally confused, this formalizes to:

Let $p\neq 2$ and $u\in\mathbb{Z}_p^*$ with canonical form $\sum_{i=0}^\infty u_ip^i$. Then \begin{align*} \exists\ x\in\mathbb{Z}_p:\ x^2=u \quad \Leftrightarrow \quad u_0 \ \text{is a quadratic residue modulo} p. \end{align*}

I think that the direction "$ \Rightarrow $" is straightforward:

Let $x\in\mathbb{Z}_p$ with canonical form $\sum_{i=0}^\infty x_ip^i\in\mathbb{Z}_p$ such that $x^2 =u$. By the Cauchy-Product-Fomrula, we have that \begin{align*} x^2=\of{\sum_{i=0}^\infty x_ip^i}^2=\sum_{i=0}^\infty \sum_{j=0}^i x_{i-j} x_jp^i\stackrel{!}{=}\sum_{i=0}^\infty u_ip^i. \end{align*} Comparing the coefficient of $p^0$ yields $x_0^2=u_0$ which means that $u_0$ is a quadratic residue modulo $p$.

Now it is left to prove the direction "$ \Leftarrow $" and that's where I get stuck. Here is what I have:

Define $f(X)\df X^2-u_0$. Since $u_0$ is a quadratic residue modulo $p$, we have that \begin{align*} \exists\ 0<y<p:\ u_0=y^2\pmod{p} \end{align*} which means that $f(y)\equiv 0\pmod{p}$ and since $\gcd\of{y,p}=1$ and $\gcd\of{p,2}=1$, we get that $f'(y)=2y\not\equiv 0\pmod{p}$. So the conditions for Hensel's lemma are fullfilled and we get a unique $a\in\mathbb{Z}_p$ with $a\equiv y\pmod{p}$ and $f(a)=0$.

I am quite sure that I need to use the condition that $u$ is a unit i.e. that $\left|| u \right||_p=1$ or that $u^{-1}\in\mathbb{Z}_p$ but I don't know how. Or maybe I got the statement wrong and am missing any premises?

share|cite|improve this question
I think you have it all almost ready to serve: the unit thing requirement comes, I guess, to avoid the boring case $\,u_0=0\,$ – DonAntonio Dec 3 '12 at 12:22
You have already used the fact that $u$ is a unit by knowing that $0<y$ in the existential statement. – anon Dec 3 '12 at 13:03
where do I use that $u$ is a unit, when $0<y$? For this direction, we may assume that $u_0$ is a quadratic residue modulo $p$ which by definition means that there is an element $y$ not zero less then $p$ such that $y^2=u_0$. It's a statement for rational integers and I don't see why it is important that $u$ is a unit in the $p$-adic integers. – born Dec 3 '12 at 13:11
If $u$ is not a unit, then what is it mod $p$? It's zero. How many things square to zero in the integers mod p? Only zero. – anon Dec 3 '12 at 16:46
up vote 2 down vote accepted

You can see that $u$ is a square in $\mathbb Z_p$ simply by computing successive digits of its square root $x$:

Choose $x_0$ such that $x_0^2\equiv u_0 \mod p$ (either square root will do).
Then $x_1$ is determined uniquely by $(x_1p+x_0)^2 \equiv u \mod p^2$
$x_2$ is determined uniquely by $(x_2p_2+x_1p+x_0)^2 \equiv u \mod p^3$
And so on.

At each stage, we have $(x_{r-1}p^{r-1}+\cdots+x_0)^2 \equiv u \mod p^r$, so the equation for $x_r$ is of the form $(x_rp^r+y)^2 \equiv u \mod p^{r+1}$ for some $y$ with $y^2\equiv u \mod p^r$. This reduces so a linear equation which is always soluble.

Edited to add: The equation for $x_1$ has a solution only if $x_0 \ne 0 \mod p$, which is why $u$ is required to be a unit.

share|cite|improve this answer
I hoped, that I could avoid this sort of inductive argumentation. I'll lock over it and accept your answer. Thanks a lot! – born Dec 3 '12 at 13:13
why exactly is $x_1$ determined uniquely by $(x_1p+x_0)^2\equiv u \pmod{p^2}$? I see, that $p, x_0$ and $u$ are given but I don't see why such an $x_1$ must exist. – born Dec 3 '12 at 15:11
Expand it out: $x_1^2p^2+2x_1px_0+x_0^2\equiv u \mod p^2$. Because $x_0^2\equiv u \mod p$, we can divide this by $p$ to get $x_1p+2x_1x_0\equiv (u-x_0^2)/p \mod p$, which has a unique solution $\mod p$. (But only if $u$ is a unit! $-$ see my edit.) – TonyK Dec 3 '12 at 15:33
maybe I'm wrong but $(u-x_0^2)/p=x_1^2p+2x_1x_0$ (so the $x_1$ has a square) and therefore it is not a linear equation and does not need to have a solution. And i still don't see that all this has to do with $u$ being a unit or not :-/ – born Dec 3 '12 at 15:46
Yes, my mistake $-$ the first term should be $x_1^2p$. But the equation is to be solved $\mod p$, so $x_1^2p$ disappears. (This is the whole point really.) – TonyK Dec 3 '12 at 15:48

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.