# When can we take square root of one side in modular arithmetic?

Say we have $a^2 \equiv p \mod n$.

I know this implies $n | a^2 - p$. But I'm wondering when this must imply $n | a - p$ or, in a different but similar vein, $n|a-\sqrt{p}$. I know that we can't take the square root in general.

I thought of this when I did modulo $3.$ I discovered that $a^2 \equiv 0 \mod 3$ implies $a \equiv 0 \mod 3$ since $3$ is prime. But I can't figure out the more general case I stated above. It's essentially two different (but very similar) questions when $p \neq 0$.

• Factor $a^2-p^2=(a-p)(a+p)$. The extra factor of $a+p$ explains why $n$ need not divide $a-p$. – Matt Samuel Dec 7 '17 at 5:11
• @MattSamuel I understand why that's the case, but I'm wondering when it's implied that such is true. – rb612 Dec 7 '17 at 6:06

If $n$ is prime, then $x^2-a\equiv0\bmod n$ has one solution, $x=0$, if $a=0$; of the other $n-1$ possible values of $a$ (working modulo $n$ here), for exactly half of them there are no solutions, and for the other half there are two solutions. It doesn't make too much sense to use the notation $\sqrt a$, since, when there are two solutions, there's no good reason to favor one of them over the other.
If $n$ is not prime, life is more difficult.
• Thank you! And what are the two solutions to the other half? Also, when you say there’s no reason to favor one of them over the other, is that because $a$ represents either solution so $\sqrt{a}$ would force one solution? – rb612 Dec 7 '17 at 8:21
• I mean $x^2-2\equiv0\pmod7$ has the solutions $x=3$ and $x=4$, so how would you decide between $\sqrt2=3$ and $\sqrt2=4$? Anyway, there's no simple formula for solving $x^2-a\equiv0\bmod n$ in general, but there are algorithms that are fairly efficient. Do you see, listed under "Related", the question, "How to compute modular square roots when modulus is non-prime"? That might be a good place to start. – Gerry Myerson Dec 7 '17 at 8:31
• Sorry, I’m a bit lost here. In the example, of course $\sqrt{2}\neq 3$ and $\sqrt{2} \neq 4$, so in either case, $x\neq \sqrt{a}$. – rb612 Dec 7 '17 at 8:47
• If $\sqrt2$ means anything, it means the thing which, when you square it, gives you 2. Well, $3^2\equiv2\bmod7$, and also $4^2\equiv2\bmod7$. So, why do you say $\sqrt2\ne3$ and $\sqrt2\ne4$? – Gerry Myerson Dec 7 '17 at 9:52