Use congruences to factor $n=87463$ (Fermat's Factorization?)

Question

I'm studying for my number theory test tomorrow, and these are the last questions in my study guide. I think I understand Fermat's factorization, however, I can't tell how my professor wants us to answer these questions. One of them is going to be on the exam.

1. Set $n= 87463$ and $q(x) = x^2 - n$. Explain how to use the congruences \begin{eqnarray*} q(265) &=& -2\times3\times13^2\times17,\\ q(278) &=& -3^3\times13\times29,\\ q(296) &=& 3^2\times17,\\ q(299) &=& 2\times3\times17\times19,\\ q(307) &=& 2\times3^2\times13\times29,\\ q(316) &=& 3^6\times17, \end{eqnarray*} to factor $n$.

2. Explain how the congruences below prove that $n = 2821$ is composite \begin{eqnarray*} 2^{705} &=& 2605 \pmod n,\\ 2^{1410} &=& 1520 \pmod n,\\ 2^{2820} &=& 1 \pmod n. \end{eqnarray*} I'm not so sure if these questions are related or not. In the second one, it is easy to see $705 = \frac{n-1}4$, $1410 = \frac{n-1}{2}$ and $2820 = n-1$ however I'm not sure on which property to use here.

Answer 1

For the first part, you can factor $n$ by using $q(316) = 3^4 q(296)$.

For the second part, if $n$ were prime, then $Z/nZ$ would be a field, so the congruence $x^2 = 1$ would have only two solutions. But you have another solution staring you right in the face.

Answer 2

Let's try to use Fermat's factorization. The given factorizations of $q(296)$ and $q(316)$ differ by a factor $3^4$, which is a square. This allows us to write $$n=316^2-3^6\times17=316^2-3^4\times(3^2\times17)=316^2-3^4\times(296^2-n).$$ Isolating $n$ yields $(1-3^4)n=316^2-3^4\times296^2$, or equivalently $$2^4\times5\times n=3^4\times296^2-316^2=2^4\times\left((3^2\times74)^2-79^2\right).$$ Taking out the factor $2^4$ then leaves $5\times n$ as a difference of squares: $$5\times n=(3^2\times74)^2-79^2=666^2-79^2.$$ Then Fermat's factorization tells us that $5\times n=587\times745$, giving the factorization $$n=149\times587.$$