# Thread: Probability of a square Mod

1. ## 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.

2. You say that $x$ is a square root mod $p$? That is true all of the time. $x$ is the square root of $x^2$, mod $p$.

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

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