0
$\begingroup$

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?

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

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.