1. ## Quadratic residue mod 2^r

If $n \equiv 1$(mod 8), then n is a quadratic residue modulo $2^r$ for any $r \geq 3$

I don'T see how to prove this, maybe by induction on r ?

2. This was a fun problem. There may be a simpler answer, but this is what I came up with (eventually). And yeah, it's induction on r.

Suppose n is a quadratic residue mod $2^r$, i.e. there exist integers a,k such that $a^2=n+2^rk$. If k is even, then k=2c and then $a^2=n+2^{r+1}c$ and we're done, so assume k odd.

Then $(a+2^{r-1})^2=a^2+2^ra+2^{2r-2}$

$=n+2^rk+2^ra+2^{2r-2}$

$=n+2^r(k+a)+2^{2r-2}$

Since k+a is even and $2r-2\ge r+1$ if $r\ge 3$, we have that $(a+2^{r-1})^2=n$ mod $2^{r+1}$.

That just leaves the base case, which is trivial: $1=1^2$ is a quadratic residue mod 8.