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

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$?

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.
$$k \equiv 1 \mod 4 \ \rm{and}\ k^{2^{q-3}} \equiv 1 \mod 2^q$$
• Dear @Robert Israel, thanks for your answer. Are you saying that: if $q=1$ or $q=2$, I can test by hand and for $q\geq 3$ the $k$ is a square mod $2^q$ iff your criterion holds? Sorry for my stupidity but why haven't we to check the cases $k\equiv 0 \mod 4$ and $k\equiv 2 \mod 4$ also? Nov 15, 2013 at 10:33
• Suppose the highest power of $2$ in $k$ is $2^r$. If $r \ge q$, then $k \equiv 0^2 \mod 2^q$. If $r < q$ and is odd, $k$ is not a square mod $2^q$. If $r < q$ and is even, $k$ is a square mod $2^q$ if and only if $k/2^r$ is a square mod $2^{q-r}$. Nov 15, 2013 at 15:35