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 $\displaystyle x$ is a square root mod $\displaystyle p$? That is true all of the time. $\displaystyle x$ is the square root of $\displaystyle x^2$, mod $\displaystyle p$.

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

To see that this is true, notice that the nonzero squares mod $\displaystyle p$ are precisely the roots of the polynomial $\displaystyle x^{(p-1)/2}-1$, which has no repeated roots.