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!

  • $\begingroup$ This form reminds me of the Lagrange's theorem about the representability of a number by four squares. Wiki $\endgroup$
    – awllower
    Aug 22, 2013 at 14:41
  • 2
    $\begingroup$ 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.) $\endgroup$
    – anon
    Aug 22, 2013 at 14:53
  • 1
    $\begingroup$ @awllower: I think you mean the Gauss' theorem about THREE squares... But I need this theorem to prove Gauss' theorem. $\endgroup$ Aug 22, 2013 at 14:54
  • 3
    $\begingroup$ 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$. $\endgroup$
    – anon
    Aug 22, 2013 at 15:01
  • 4
    $\begingroup$ 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$. $\endgroup$
    – user8268
    Aug 22, 2013 at 16:05

1 Answer 1


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

  • 2
    $\begingroup$ Having a root in ${\Bbb F}_2$ is not enough for Hensel's to guarantee a lift up to ${\Bbb Z}_2$. $\endgroup$
    – anon
    Aug 25, 2013 at 14:34
  • 8
    $\begingroup$ 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. $\endgroup$
    – Cantlog
    Aug 25, 2013 at 15:44
  • 2
    $\begingroup$ 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$. $\endgroup$ Aug 28, 2013 at 21:11
  • $\begingroup$ Oh I am surprised but happy to receive this bounty, thanks @JyrkiLahtonen ! $\endgroup$
    – Cantlog
    Sep 15, 2013 at 19:41

You must log in to answer this question.

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