# Characterization of integers which has a $2$-adic square root

Does anyone know an "elementary" proof of the following theorem?

Let $k \neq 0$ be a rational integer. Then $k$ admits a square root in $\mathbb{Z}_2$ if $k = 4^a (8b+1)$ for some $a \in \mathbb{N}$, $b \in \mathbb{Z}$.

About $p$-adic numbers I don't know anything more sophisticated than Hensel lemma. Thank you!

• This form reminds me of the Lagrange's theorem about the representability of a number by four squares. Wiki Aug 22, 2013 at 14:41
• So do you accept the proof by Hensel's lemma as elementary? (Granted, the version of Hensel used has to have a little bit of teeth to it.)
– anon
Aug 22, 2013 at 14:53
• @awllower: I think you mean the Gauss' theorem about THREE squares... But I need this theorem to prove Gauss' theorem. Aug 22, 2013 at 14:54
• Hensel's can be upgraded so that the condition for existence of a lift is not that $f'(a)$ is nonzero mod $p$ but that $|f(a)|_p<|f'(a)|_p^2$. This allows you to lift square roots mod $2^3$.
– anon
Aug 22, 2013 at 15:01
• It's easy to see that it must be of this form (first take away $2^{2a}$, then look at odd squares mod 8). Then just use the binomial formula for $(1+x)^{1/2}$, with $x=8b$. Aug 22, 2013 at 16:05

You are looking for $x\in\mathbb Z_2$ such that $(1+2x)^2=8b+1$. This is equivalent to $$x^2+x-2b=0.$$ Now mod $2$, this polynomial is $x(x+1)$ and has (at least) one simple root in $\mathbb F_2$. By Hensel's lemma, the above equation has a solution in $\mathbb Z_2$.
• Having a root in ${\Bbb F}_2$ is not enough for Hensel's to guarantee a lift up to ${\Bbb Z}_2$.
• Dear @anon: I just acquired the necessary reputations to be allowed to comment. You are right that having a root in $\mathbb F_2$ is not enough, but when the root is simple as in my message, then we are in the position to apply Hensel's lemma. Aug 25, 2013 at 15:44
• Delightful! We also observe that if $x_1$ is one of the $2$-adic roots of this equation, then $x_2=-1-x_1$ is the other. Consequently $(1+2x_2)=-(1+2x_1)$ as it, of course, should be as the other square root of $8b+1$. Aug 28, 2013 at 21:11