Trial Division and Quadratic Reciprocity

Question

I am reading The Joy of Factoring by Samuel Wagstaff and I am having trouble understanding a paragraph from this book. It says the following

One can use quadratic residues to speed Trial Division by skipping some primes that cannot be divisors. This device was used by Euler, Gauss, and others hundreds of years ago. Let N be the number to factor. Suppose we know a nonsquare quadratic residue r modulo N. Then r is also a quadratic residue modulo any prime factor p of N. If r is not a square, the Law of Quadratic Reciprocity restricts p to only half of the possible residue classes modulo 4|r|.

There are two things which I am not sure I understand correctly:

-When it says that a nonsquare quadratic residue mod $N$ is also a quadratic residue mod any prime factor $p$ of $N$. (I think this is because of the Chinese Remainder Theorem but I am not sure)

-When it says that if $r$ is not a square, the law of quadratic reciprocity restricts $p$ to only half of the possible residue classes modulo $4|r|$. I know that for example if $r$ is a quadratic residue mod $p$ then $p$ must also be a quadratic residue mod $m$ by the law of quadratic reciprocity, however this would restrict the possible values of $p$ to half of the residue classes mod $r$ not mod $4|r|$.

I am confused

Answer 1

When it says that a nonsquare quadratic residue mod N is also a quadratic residue mod any prime factor p of N. (I think this is because of the Chinese Remainder Theorem but I am not sure)

$\ r\equiv a^2\pmod{\!N\!=\!\color{#c00}pk}\,\Rightarrow\, r\equiv a^2\pmod{\!\color{#c00}p}\,$ by congruences persist mod $\rm\color{#c00}{factors}$ of the modulus

When it says that if r is not a square, the law of quadratic reciprocity restricts p to only half of the possible residue classes modulo 4|r|. I know that for example if r is a quadratic residue mod p then p must also be a quadratic residue mod m by the law of quadratic reciprocity, however this would restrict the possible values of p to half of the residue classes mod r not mod 4|r|.

Consider first the case $\,r = q\,$ prime. By quadratic reciprocity

$$\chi(p) := (q|p) = (p|q)^{\large \frac{p-1}2 \frac{q-1}2}$$

so $\,\chi(p+\color{#c00}4q) = \chi(p)$ since adding $4q$ to $p$ preserves the parity of $(p-1)/2$ so doesn't affect the sign factor, and preserves $(p/q)$ by $\,p+4q\equiv p\pmod{\!q}.\,$ Generally $4q$ is the least such value, e.g.

$$\begin{align} (3|p) = 1 &\iff p\equiv -1,1\ \ \ \pmod {\color{#c00}4\cdot 3}\\[.2em] (-5|p) \equiv 1 &\iff p\equiv 1,3,7,9\!\!\pmod{\color{#c00}4\cdot 5}\end{align}$$

When $r$ is a product of odd primes $q_i$ this extends by multiplicativity to the lcm of $\,4q_i$ which is $ 4\prod q_i = 4r.\,$ For a rigorous proof see e.g. section $2.5$ (Quadratic Residue Characters) in Harvey Cohn's book Advanced Number Theory. It derives this resolution modulus for the Jacobi symbol.