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 know some elementary proofs of this fact. I was wondering if there's some short slick proof of this fact using the structure of the $2$-adic integers? I'm looking for a proof of this fact that's easy to remember.

share|cite|improve this question
$a=17, n=5.\ a\equiv17\mod2^5,$ but 17 is not a square... or didn't I understand your statement? – FUZxxl Sep 22 '11 at 17:22
@FUZxxl: Is 17 a square modulo $2^5$? That is, does there exist $x$ such that $x^2\equiv 17\pmod{2^5}$? – Arturo Magidin Sep 22 '11 at 17:23
Ah! I missunderstood. Thank you. – FUZxxl Sep 22 '11 at 17:25
@asdfg: the shortest proof I can think of uses Hensel's Lemma. Do you count that as "using the structure of the $2$-adic integers"? – Pete L. Clark Sep 22 '11 at 17:28
@Pete: Now that you mention it, letting $f(X)=X^2-a$, we have $|f(1)|_2=1/8$ while $|f'(1)^2|_2=1/4$, so $|f(1)|<|f'(1)|_2$ i.e. by Hensel, we find a root in $\mathbb{Z}_2$ and hence modulo every $2^n$. I guess this is as short as it gets. – asdfg Sep 22 '11 at 18:04

There is indeed a $2$-adic proof. $(1+u)^{1/2} = 1+\sum_{k \geq 1} \binom{1/2}{k} u^k$ where $\binom{1/2}{k}= \frac{1/2(1/2-1) \ldots (1/2-k+1)}{k!} = 2^{-k}(-1)^{k-1}\frac{(2k-3) (2k-5) \ldots 3}{k!}$. We would like the sum to converge, and for this we only need the general term to go to $0$.

$v_2\left(\binom{1/2}{k} u^k\right)=k(v_2(u)-1)-v_2(k!)$. Furthermore, $v_2(k!) = \sum_{l \geq 1} \left\lfloor\frac{k}{2^l} \right\rfloor < k$, so if $v_2(u)>2$ the series converge and the fact that as formal series (i.e. in $\mathbb{Q}[[u]]$) $\left(1+\sum_{k \geq 1} \binom{1/2}{k} u^k\right)^2=1+u$ tells you that you really find a square root of $1+u$ by taking the limit.

Of course if $v_2(u)>2$ all the terms are in $\mathbb{Z}_2$, so the limit is also in $\mathbb{Z}_2$.

share|cite|improve this answer
Awesome. I've always wondered what can be done with those binomials involving fractions after I noticed them while flipping through Stanley's enumerative combinatorics. – asdfg Sep 22 '11 at 18:06
+1 Binomial series FTW. – Jyrki Lahtonen Sep 22 '11 at 20:53

The shortest proof I can think of goes as follows. Hensel is not needed. A counting argument will suffice.

We take as the starting point that the group of units $U_n$ of the ring $\mathbf{Z}/2^n\mathbf{Z}$ has the structure $U_n\simeq C_2\times C_{2^{n-2}}$. Therefore exactly one quarter of elements of $U_n$ are squares.

Assume $n\ge3$. For an odd integer $m$ to be a quadratic residue modulo $2^n$ it is surely necessary for $m$ to be a quadratic residue modulo 8. We easily check (or know in advance) that for $m$ to be a quadratic residue modulo 8 it has to be congruent to 1 modulo 8. Thus exactly one quarter of the odd integers in the range $[0,2^n]$ are quadratic residues modulo 8. As this is a subset of the equinumerous set of squares of $U_n$, the two sets must coincide.

Edit: Or was this exactly (one of) the elementary proof(s) you know? I think that this is easy to remember, though :-)

share|cite|improve this answer

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.