Go Factor!

We write $p = u^2 + v^2$ and $q = x^2 + y^2$ . Then $pq = (ux \pm vy)^2 + (uy \mp vx)^2.$ Thus, assigning $u, v, x, y$ in such a way that $ux \pm vy$ are even and $uy \mp vx$ are odd, $ux + vy = 616,\ \ ux - vy = 464,\ \ uy + vx = 429,\ \ uy - vx = 141.$ It follows that $\begin{array}{ll} ux = \tfrac12(616 + 464) = 540 & uy = \tfrac12(429 + 141) = 285 \\ vx = \tfrac12(429 - 141) = 144 & vy = \tfrac12(616 - 464) = 76 \end{array}$ Determine common factors: $\begin{array}{cc|l} 540 & 285 & 15 \\ 144 & 76 & 4 \\ \hline 36 & 19 & \end{array}$ Thus we have the prime factors $36^2 + 19^2 = 1296 + 361 = 1657;\ \ \ 15^2 + 4^2 = 225 + 16 = 241.$ So $399\:337 = 1657\cdot 241$ , and the answer to the problem is $1657 + 241 = \boxed{1898}$ .

Using the Euclidean Division Algorithm in the Gaussian integers, we calculate that the highest common factor of $616 + 141i$ and $464 + 429i$ is $36 + 19i$ . Since $399337 \; =\; (616 + 141i)(616 - 141i) \; = \; (464 + 429i)(464 - 429i)$ we deduce that $36 + 19i$ divides $399337$ in the Gaussian integers, and hence $1657 = |36 + 19i|^2$ divides $399337^2$ . Since $1657$ is prime, this means that $1657$ divides $399337$ .

If we want to avoid dividing $399337$ by $1657$ , we could also note that the highest common factor of $616 + 141i$ and $464 - 429i$ is $4 + 15i$ . Since $241 = |4 + 15i|^2$ is prime, we deduce as above that it must divide $399337$ .

Thus $399337 = 241 \times 1657$ , so the answer is $\boxed{1898}$ .