Thread: Probability of a square Mod

I really have no idea where to start , or how to do this problem.

Suppose x is relatively prime to p; it's claimed when p is large that x is a square root mod p with probability of 1/2.

I'm supposed to justify the claim.

If anyone could help me with this it would be greatly appreciated.

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.