Quadratic residue test for mod powers of 2

Question

For odd primes, you can test using Euler's criteria if a number is a Quadratic Residue $\bmod p$.

I am looking for a test for mod powers of 2 (which are even & hence cannot use Euler's criteria).

I found this – https://www.johndcook.com/blog/quadratic_congruences/

Here it says

For $n ≥ 3$, $x^2 \equiv a \pmod {2^n}$ has four unique solutions if $a \equiv 1 \pmod 8$ and no solutions otherwise.

If this works, it's a pretty simple test to check if any number $a$ is a QR $\bmod {2^n}$ – just check if $a \equiv 1 \pmod {2^3}$. However, I am unable to find this is any textbook.

UPDATE/EDIT:

Looking at the proof from the webpage (proof by Induction).

Let ${x_k}^2 \equiv a \pmod {2^k}$ for $k \ge 3$

So ${x_k}^2 – a$ divides $2^k$
Let $\frac {{x_k}^2 – a}{2^k} = m$

Case 1: m is even.

Divide both sides by 2

$\frac {{x_k}^2 – a}{{2^k} . 2} = \frac{m}{2}$

m is even, so 2 divides m. Let $n = \frac{m}{2}$

$\frac {{x_k}^2 – a}{2^{k+1}} = n$

So ${x_k}^2 \equiv a \pmod {2^{k+1}}$

So it's proven when m is even

Case 2: m is odd

I am not able to figure out how to prove the case when m is odd. Can someone help?

Answer 1

For simplicity, I am using x instead of $x_k$.

i.e. we know $x^2 \equiv a \pmod 2^k$

Case 2: m is odd.

Calculate $ {(x+ 2^{k-1})}^2 \bmod 2^{k+1}$

Expanding the LHS we get

LHS = $x^2 + 2*2^{k-1}*x + 2^{2k-2}$

$ = x^2 + x.2^k + 2^{2k-2}$

The 3rd term in the above evaluates to $0 \bmod 2^{k+1}$

So we have $x^2 + x.2^k \bmod 2^{k+1}$

$\frac {x^2 - a}{2^k} = m$

$x^2 = m.{2^{k}} + a$

So $x^2 + x.2^k \bmod 2^{k+1}$

$ = m.{2^{k}} + a + x.2^k \bmod 2^{k+1}$

$ = 2^k(m + x) + a \bmod 2^{k+1}$

• $a\equiv1\bmod 8$, so a is odd.

• $m$ is odd.

• $x^2 = a + m.2^k$. Since $a$ & $m$ are odd, RHS here is odd & hence $x^2$ is odd & hence $x$ is odd

• Since $m$ & $x$ are odd, $m+x$ is even & hence can be expressed as $2*n$ i.e. Let $m+x = 2n$

So we have $2^k(m + x) + a \bmod 2^{k+1}$

$ = 2^k * 2n + a \bmod 2^{k+1}$

$ = 2^k * 2n + a \bmod 2^{k+1}$

$ = 2^{k+1} + a \bmod 2^{k+1}$

$ = a \bmod 2^{k+1}$

Which is what we set out to prove

${(x+2^{k-1})}^2 \equiv a \pmod {2^{k+1}}$

So it's proven for both cases - when m is odd or even.

A big thank you to GerryMyerson for guiding me through this.