# Quadratic Sieve Algorithm: Why is $(x − \lfloor \sqrt{n} \rfloor)^2 ≡ n ($mod $p)$?

If someone here understands the Quadratic Sieve Algorithm, I'm having trouble understanding why every prime $p$ in the factor base needs to a prime such that $n$ is a quadratic residue modulo $p$. It is explained on the bottom of page 2 of the paper found here.

The sentence I'm struggling on is near the bottom of page 2, where it says

Now if $x$ is in this sieving interval, and if some prime $p$ divides $Q(x)$, then $(x − \lfloor \sqrt{n} \rfloor)^2 ≡ n ($mod $p)$.

Why is this statement true?

Since $Q(x)$ is defined as $(x+\lfloor \sqrt{n} \rfloor)^2 -n$, that follows directly from this definition.
I've looked at $(x+\lfloor \sqrt{n} \rfloor)^2 -(x-\lfloor \sqrt{n} \rfloor)^2 =4x\lfloor \sqrt{n} \rfloor$, but this doesn't seem to help.
• How do you get from ($x + \lfloor \sqrt{n} \rfloor )^2$ to ($x - \lfloor \sqrt{n} \rfloor )^2$ here? – Jimm Nov 27 '15 at 7:09
• Since the author only appears to use that formula to show thatn $n$ is a quadratic residue, modulo $p$, it would appear that the minus sign in the paper was a typo. – Thomas Andrews Nov 27 '15 at 7:20
• I found this paper link and it seems that the it should have been $x + \lfloor \sqrt n \rfloor)^2$ – steven gregory Jan 17 '16 at 15:48