1
$\begingroup$

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$.

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – rb612 Dec 7 '17 at 8:21
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Dec 7 '17 at 8:31
  • $\begingroup$ 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}$. $\endgroup$ – rb612 Dec 7 '17 at 8:47
  • 2
    $\begingroup$ 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$? $\endgroup$ – Gerry Myerson Dec 7 '17 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.