Can someone please prove that $\sqrt{a} \bmod p$, for some prime $p$, and $\sqrt{a} \bmod q$, for some prime $q$, evenly distributed?
In other words, modulo all primes, either $\sqrt{a}$ is an integer modulo some prime, or it basically does not exist as an integer. I want to know if I can expect this distribution to be random. For instance, if I pick a set of primes, can I expect $\sqrt{a}$ to have approximately a 50% chance of existing modulo each prime?
One other thing… It would be helpful to know if $\sqrt{a}$ and $\sqrt{b}$ are independent modulo the same prime, for randomly chosen $a$ and $b$.
Best Answer
Let $p$ be an odd prime. $a \equiv b^2 \mod p$ has either two solutions or none. So the preimage of $a$ under the map $x \mapsto x^2$ is either empty or consists of two elements, showing that the squaring function $\Bbb Z_p \to \Bbb Z_p$ has an image of cardinality $(p-1)/2$.
Therefore you're right: for arbitrary $a$, save for cases where $p \mid a$, there is a $50\%$ chance that $a$ is a square modulo $p$.