What Determines the Existence of Solutions for Quadratic Residues Modulo N?

[jostpuur]

Suppose $N=1,2,3,\ldots$ and $y=0,1,2,\ldots, N-1$ are fixed. How do solve $x$ out of

$$y=x^2\quad \textrm{mod}\quad N ?$$

I went through some of the smallest values for $N$ and all $y$, and I could not see a pattern. For example, if $N=5$, then at least one $[x]$ exists if $[y]=[0],[1]$ or $[4]$, but no solution $[x]$ exists if $[y]=[2]$ or $[3]$. You can produce similar result for other small $N$ with finite amount of work, but I failed to see a pattern that I could try to generalize.

 

[mfb]

For prime N, there is an algorithm. The article also has a link for the other cases.

 

[Joffan]

You're talking about quadratic residues.

Modulo 2, every integer is a quadratic residue.

Modulo an odd prime number p there are (p + 1)/2 residues (including 0) and (p − 1)/2 nonresidues. In this case, it is customary to consider 0 as a special case

Edit to add: If you just want to determine whether a given k is a solution to $k \equiv x^2 \text{ mod } p$, for $p$ prime, you can use Euler's criterion: $k^\frac{p-1}{2} \equiv 1 \text{ mod } p$