Can you mod under the root?

Question

I've been using the following fact for a long time, and as I have never seen it fail, I've started to believe it. However, I have never actually seen a proof. For $m, n, p ∈ \Bbb Z, p$ prime:

$m ≡ n \mod p \Rightarrow \sqrt{m} ≡ \sqrt{n} \mod p$

This usually comes up when doing something like applying the quadratic formula in a finite field.

Answer 1

hint

$$m\equiv n\mod p \iff$$

$$m-n\equiv 0 \mod p \iff$$

$$(\sqrt{m}+\sqrt{n})(\sqrt{m}-\sqrt{n})\equiv 0 \mod p$$

If $ p$ is prime, we will have $$\sqrt{m}\equiv \sqrt{n} \mod p$$ Or $$\sqrt{m}\equiv -\sqrt{n}\mod p$$

example $$m=16; n=9 ;p=7$$

Answer 2

I think your problem is with the square root sign. In the real numbers, $\sqrt{a}$ is always the positive square root of a positive number $a$. The ordering allows you to single out one of the two solutions to $x^2 =a$ and call it "the" square root.

When $a \ne 0$ is complex it has two square roots, but we don't use the square root symbol to specify one of them unless $a$ is real and positive.

In a finite field $a \ne 0$ may have two square roots or none (or one if the characteristic is $2$). When there are two, neither is "the" square root. The square root symbol in the quadratic equation must be interpreted appropriately. Equal squares need not have equal square roots in your phrasing of the question.

Answer 3

I guess the reason no-one talks about even though it is true (if $p$ is prime)

[If $a,b\in \mathbb N;$ and $a^2 = n; b^2 = m$ then if $n\equiv m \pmod p$ so $p|m^2 - n^2=(a-b)(a+b)$ so either $a-b=1$ and $a+b=p$ so $\sqrt{n}=a\equiv -b=-\sqrt m \pmod p$ or $a-b=-p$ and $a+b=-1$ and $\sqrt n = a \equiv b=\sqrt m \pmod p$]

Is that it is naive to think about $n \pmod p$ as the integer $n$. If he integer $n$ happens to be a perfect square that is pretty irrelevant as the integer $m = n+kp$ wont be. And we don't care at all about $n$ as an integer; we only care about $n$ as a representative of an equivalence class, so $n$ and $n+kp$ are considered to be the exact same thing.

Which makes the only reasonable meaning for $\sqrt n$ is that $\sqrt n\equiv a\pmod p$ if $a^2 \equiv n\pmod p$ and we have some criterion for selecting $a$ for from all the other representatives whose square are equivalent to $n$ (possibly in the lowest integer representative between $0$ and $p-1$....).

But then the observation is trivial and near meaningless. If $m \equiv n\pmod p$ then $m$ and $n$ are the same thing. So if $\sqrt{n} \equiv a$ so $a^2 \equiv n$ then... $a^2 \equiv m$ and $\sqrt{m} \equiv a$.

However... To put it in more sophisticated terms:

If $p$ is prime the if $a^2 \equiv b^2 \equiv n\pmod p$ then $a\equiv \pm b \pmod p$. But only half of the residue class $1,...., p-1$ will have solutions to $x^2\equiv a\pmod p$ and for those classes there will be exactly $2$ solutions.

If $p$ is not prime $x^2 \equiv n$ may have more than two solutions. Or may have none at all.