# Proof that $a\equiv 1\,(\textrm{mod }8)$ implies $a$ is a square modulo $2^n$ for all $n$

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.

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

-
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 :-)

-