factor 9997 using quadratic reciprocity I looked up the factorization and it is $13\cdot769$, but I have no idea how quadratic reciprocity allows you to deduce this without knowing it.
I thought maybe $(\frac{9997}{p})=(\frac{a}{p})(\frac{b}{p})$ with $ab=9997$ but I don't know if you can go anywhere from there, or if that is useful. Can somebody help me out? Also $9997=1 \bmod 4$ which will probably be useful. Thanks.
 A: Assume that $p$ is a prime factor of $9997$. Then $10000=100^2\equiv3\pmod p$, so $3$ is a quadratic residue modulo $p$. As $p>3$ this implies by quadratic reciprocity that $p\equiv\pm1\pmod{12}$. It suffices to check the cases $p<100(>\sqrt{9997})$, so that leaves
$p\in\{11,13,23,37,47,59,61,71,73,83,97\}$ as possible factors.
Also $10201=101^2\equiv204\pmod{9997}$, so $204=2^2\cdot3\cdot17\pmod p$. Therefore also $17$ is a QR modulo $p$. Reciprocity then dictates that $p\equiv1,4,9,16,8,2,15,13\pmod{17}$. Taking this into account shortens the list of possible prime factors $<100$ to
$$p\in\{13,47,59,83\}.$$
It is no longer a daunting task to check this list. 
A: As far as I know, quadratic reciprocity doesn't let you factor numbers.  However, it does allow you to test for primality.  We use Jacobi symbols (or possibly Legendre symbols) to calculate $$\left(\frac{5}{9997}\right)=\left(\frac{9997}{5}\right)=\left(\frac{2}{5}\right)=-1$$
If $9997$ were prime, then these are all Legendre symbols and we would also know that $5^{(9996/2)}\equiv -1\pmod{9997}$.  However, we calculate $5^{(9996/2)}\equiv 5628\pmod{9997}$.  Hence these are not Legendre symbols, i.e. $9997$ is composite.  $5$ serves as a witness to this.
