# Quadratic residue test for mod powers of 2

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

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?

• Comments are not for extended discussion; this conversation has been moved to chat.
– Pedro
Aug 2, 2021 at 8:17

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.