3
$\begingroup$

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.

  • 0
    $a=17, n=5.\ a\equiv17\mod2^5,$ but 17 is not a square... or didn't I understand your statement?2011-09-22
  • 0
    @FUZxxl: Is 17 a square *modulo* $2^5$? That is, does there exist $x$ such that $x^2\equiv 17\pmod{2^5}$?2011-09-22
  • 0
    Ah! I missunderstood. Thank you.2011-09-22
  • 2
    @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"?2011-09-22
  • 2
    @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.2011-09-22

2 Answers 2