Factor $n=59305397$ given that $ p-q \le 10 $

Question

So what is given is that $n=pq\ ; \ p-q = \sqrt{(p+q)^2 -4n}$

Rearranging the $p-q$ equation, I get $$ p+q = \sqrt{(p-q)^2 +4n}$$

So, $$2p = (p+q) + (p-q) \ \text{and} \ q=\cfrac{n}{p}$$

However $p-q$ is given to us as an inequality. Not sure how to find the exact value for $p-q$.

Answer 1

This method is guaranteed to find the largest factor of $n$ below the square root: Compute $q_0=\lfloor\sqrt n\rfloor$ and try $q_0, q_0-1, q_0-2, \ldots$ for $q$. By the given constraint, you will succeed within a few steps. (Of course you can speed up by trying only odd values for $q$).

Actually, we could exploit a bit more: From $pq\equiv 7\pmod{10}$ we conclude that $(p\bmod 10,q\bmod 10)\in\{(1,7),(3,9),(7,1),(9,3)\}$ and hence $p=q+4$ or $p=q+6$. Hence $\le10$ could be replaced by $\le 6$, i.e. the algorithm above will succed in even fewer steps.

Answer 2

$$4n \leq (p+q)^2 = (p-q)^2 +4n \leq 4n+100 \,.$$

Now, given that $n$ is so large, it is very easy to argue that there is at most a perfect square between $4n$ and $4n+100$. Therefore $p+q$ is $\sqrt{4n}$ rounded up.