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: 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$.
A: 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 :-)
