Quadratic Residues $\pmod {2^n}$

Question

I'd imagine this is a duplicate question, but I can't find it:

How many quadratic residues are there $\pmod{2^n}$.

I tried small $n$: $n=1: 2, n=2:2, n=3: 3, n=4: 4, n=5: $not 5: 0, 1, 4, 9, 16, 25

No pattern :/

Answer 1

The multiplicative group $\bmod 2^n$ is isomorphic to $\mathbb Z_{2^{n-2}}\times \mathbb Z_2$ so we have $\mathbb Z_{2^{n-3}}$ odd quadratic residues.

How many even quadratic residues do we have? How many do we have of the form $d2^{2k}?$ with $d$ odd? $d$ is an odd quadratic residue $\bmod 2^{n-2k}$ so there are $2^{n-2k-3}$ options.

Hence the answer is $\sum\limits_{k=0}^{\lceil\frac{n}{2}\rceil}\lceil2^{n-2k-3}\rceil$

Answer 2

There is a basic solution that only uses modular arithmetic. Let $p(n)$ be the number of quadratic residues modulo $2^n$. We know that $p(1) = p(2) = 2$. Now suppose $n \geq 3$. We will proof 3 small lemmas.

Lemma 1. It suffices to consider the residues of the numbers $0,1,...,2^{n-2}$

Proof. Indeed, the following relations hold: $$(2^n-x)^2 \equiv x^2 \mod 2^n, \quad (2^{n-1}-x)^2 \equiv x^2 \mod 2^n $$ So every square can be reduced to the square of one of the numbers $0,1,...2^{n-2}$

Lemma 2. If $x,y$ are distinct odd integers and $1 \leq x,y \leq 2^{n-2}-1$, then $x^2\not\equiv y^2 \mod 2^n$.

Proof. Suppose that $2^n \mid x^2-y^2 = (x-y)(x+y)$. Now $\text{gcd}(x+y,x-y)$ is divisible by $2$ but not by $4$ (because it divides $2x = (x+y)+(x-y)$). This implies that one of the two factors is divisible by $2$ and the other one is divisible by $2^{n-1}$. But $x+y \leq 2^{n-1}-2$, so $x-y$ should be divisible by $2^{n-1}$. We conclude that $x = y$.

These two lemmas imply that there are exactly $2^{n-3}$ odd quadratic residues modulo $2^n$. Now we look at the even residues:

Lemma 3. There are $p(n-2)$ even quadratic residues mod $2^n$.

Proof. Indeed, if $x = 2m$ and $y = 2n$, then $x^2 \equiv y^2 \mod 2^n$ if and only if $m^2\equiv n^2 \mod 2^{n-2}$. This gives the result immediately.

We conclude that $p(n) = p(n-2)+2^{n-3}$. From this recurrence relation it is quite easy to prove by induction that

• $p(n) = \frac{5+2^{n-1}}{3}$ if $n$ is odd
• $p(n) = \frac{1+2^{n-1}}{3}$ if $n$ is even

If you like to put everything together, we get the following result:

There are $$\frac{2^{n-1}+3+2.(-1)^{n-1}}{3}$$ quadratic residues modulo $2^n$