Sieve improvement for Fermat's factorization method

Question

I been reading the wiki article about, Sieve improvement for Fermat's factorization method.

And I don't understand the mode 16 example, I understand why $a^2$ must be $9$. But why $a$ must be $3$ or $5$ or $11$ or $13$ modulo $16$?

Answer 1

If $a^2 \equiv 9 \mod 16$ then $a$ must be odd. But if $a \in\{1,7,9,15\} \mod 16$ then $a^2 \equiv 1 \neq \mod 16$.

Answer 2

[Modular Improvement To Fermat's Factorization Method] If you take N=XY and cast it into a modular form say, $$Bz+r=(Bx+a)(By+b)$$ where $r$ is congruent to $ab$ mod $B$ (there will be $\phi(B)$ possibilities assuming $r$ and $B$ are co-prime.) The modular form can be reduced to $$Bxy+ax+by+m=z$$ where $m$ equals the floor of $ab$ divided by $z$. Now apply a change of variables to $x$ and $y$, let $x=t+s$, and $y=t-s$. You will arrive at $$B(t^2-s^2)+(a+b)t+(a-b)s+m=z$$ Trivially if $B=1$ this is Fermat. If $B>1$ you get a reduced search area and the structure of the reduced residue system to guide your efforts. There are many many interesting algorithms related to this idea which I have come to call a modular improvement of Fermat's Method. It is more straightforward than it even seems at first glance.

Cheers.