Thread: Probability of a square Mod

You say that is a square root mod ? That is true all of the time. is the square root of , mod .

What you probably mean is that is a square mod with probability 1/2. This is because there are as many nonzero squares as there are non-squares mod (when is odd).

To see that this is true, notice that the nonzero squares mod are precisely the roots of the polynomial , which has no repeated roots.