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.
The comments below show that I jumped too soon. However, looking more closely at the paper, I am inclined to agree with Thomas Andrews that this is indeed a typo.
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.