Symmetric Divisibility

WLOG let $m$ be greater than or equal to $n$ . When $m\leq5$ we can check the solutions to be $(2, 2), (5, 29)$ .

Suppose $m=n> 5$ . Then we have $m$ divides 4, contradiction.

Hence we can assume $m> n> 5$ . Let $(m, n)$ be the solution such that $m+n$ is minimised (we suppose for sake of contradiction that such a solution exists). Then consider the solution $(n,\frac {n^{2}+4}{m})$ . Note that $\frac {n^{2}+4}{m}$ is an integer and divides $n^{2}+4$ . Also, $(\frac {n^{2}+4}{m})^{2}+4=\frac {(n^{2}+4)^{2}+4m^{2}}{m^{2}}$ . Since $m$ and $n$ are distinct primes, to show that this is a valid solution we just need to show that $n$ divides $(n^{2}+4)^{2}+4m^{2}=n^{4}+8n^{2}+4 (m^{2}+4)$ . But this is clearly true by the fact that $n|m^{2}+4$ . Hence the solution $(n, \frac {n^{2}+4}{m})$ is valid.

Also,, $n^{2}+4<n^{2}+n=n (n+1)$ which does not exceed $mn$ which implies that $\frac {n^{2}+4}{m}<n <m$ . If $\frac {n^{2}+4}{m}$ was greater than 5, then the minimality condition has been contradicted. Otherwise, it is equal to 2 or 5. (Refer to the two solutions above). If it was 2, then $n$ is even, contradiction. If it was 5, then $n|5m-4, m^{2}+4$ hence $n|5m^{2}+20, 5m^{2}-4m$ . This implies that $n|m+5, n|m^{2}+10m+25$ . Together with the fact that $n|m^{2}+4$ , $n|10m+21$ . With the fact that $n|m+5$ we have $n|10m+50, n|29$ . This gives the solution (5, 29).

We have just shown that $n$ cannot be greater than 5. Hence, from the two solutions above, we obtain the answer as $2+5+29=36$ .

This is a completely uneducated guess.

Primes $\geq 5$ are of the form $6x\pm1$ . Thus, for smaller primes, the difference between two is either $2$ or $4$ .

Now, if difference is $2$ , then $n|n^2+4n+8 \Rightarrow n|8$ . The only prime which satisfies this is $2$ . The corresponding $m$ when $n=2$ , is when $m|8\Rightarrow m=2$ .

Now, if the difference is $4$ , then $n|n^2+8n+20 \Rightarrow n|20$ . Since $n$ can be $2$ , $n$ can also be $5$ . The corresponding $m$ , when $n=5$ , is when $m|29\Rightarrow m=29$ .

Thus, the possible values of $n=2,5,29$ , whose sum is $\boxed{36}$ .

Could someone else post a real solution, and explain to me how I got the answer by fluke?