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

<br /> y=x^2\quad \textrm{mod}\quad N ?<br />

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$