Reduction of the question of quadratic residues mod $m$ to the primary decomposition of $m$.

Question

Let $m\geq 1$ and $k$ be integers.

If $m=p_1^{q_1}...p_l^{q_l}$ is the primary decomposition of $m$, it's easy to see with the Chinese remainder theorem that $k$ is a square mod $m$ iff for all $j\in\{1,...,l\}$ the $k$ is a square mod $p_j^{q_j}$.

Wikipedia states ''A number relatively prime to an odd prime $p$ is a residue modulo any power of $p$ if and only if it is a residue modulo $p$.'' which means for an odd prime $p$, that $k$ is a square mod $p_j^{q_j}$ iff $k$ is a square mod $p_j$. With Euler's criterion, I can then decide if $k$ is a square mod $p$ or not.

To get a full answer to the original question (''when is $k$ a square mod $m$?''), I need to know what happens for the prime $p=2$ and powers of it. Mod $2$, every $k$ is a square. Is there a criterion like Euler's to decide if $k$ is a square mod $2^q$?

Answer 1

The multiplicative group $U_{2^q}$ for $q \ge 3$ is not cyclic, but is generated by $-1$ and $5$. If $k \equiv 1 \mod 4$, then $k \equiv 5^j \mod 2^q$ for exactly one $j \in \{0,1,\ldots,2^{q-2} - 1\}$, and $k$ is a square if and only if $j$ is even. If $k \equiv 3 \mod 4$, then $k \equiv -5^j \mod 2^q$ for exactly one such $j$, and $k$ is not a square.

The criterion can be written as:

$$k \equiv 1 \mod 4 \ \rm{and}\ k^{2^{q-3}} \equiv 1 \mod 2^q$$