Problem 2188

Conditions $n \mid 3m + 1$ and $m \mid n^2 + 3$ we label by (1) and (2).
By (1) $3$ and $n$ are coprime: $(3, n) = 1$ (3).
Let $n \le 9$. Due to (3) $n$ can take $1, 5, 7$.
If $n = 1$ from (2) $m \mid 4$ and since $m$ is odd we get $m = 1$. $(m, n) = (1, 1)$ satisfies the conditions.
If $n = 5$ (1) and (2) become $5 \mid 3m + 1$ and $m \mid 28$. Since $m$ is odd $m \mid 7$ but $m = 1, 7$ do not satisfy the condition $5 \mid 3m + 1$.
If $n = 7$ (1) and (2) become $7 \mid 3m + 1$ and $m \mid 52$. Since $m$ is odd $m \mid 13$ but $m = 1, 13$ do not satisfy the condition $7 \mid 3m + 1$.
Now $n > 9$. By (1) and (2) there are positive integers $p, q$ such that $np = 3m + 1$ and $mq = n^2 + 3$.
Now let us prove that $m \ge n + 1$. If $m \le n$ then $4n > 3m + 1$. Therefore, $p$ can be only $1, 2$ or $3$. But if $p = 3$ then $3 \mid 1$ and if $p = 1$ we get $np \equiv 1 \not\equiv 0 \equiv 3m + 1 \pmod{2}$. Thus, $p = 2$.
Now $m \mid n^2 + 3 \Rightarrow m \mid 4n^2 + 12 = (2n)^2 + 12 = (3m+1)^2 + 12 \Rightarrow m \mid 13$. Thus, $m = 1, 13$. Since $n = \frac{3m+1}{2}$ if $m = 1$ then $n = 2$ and if $m = 13$ then $n = \frac{3 \cdot 13 + 1}{2} = 20$. In both cases $n$ is even, contradiction. Thus, we have proved that $m \ge n + 1$.
Now $n(n+1) > n^2 + 3 = mq \ge (n+1)q \Rightarrow q < n$.
From (1) $n \mid 3m+1 \Rightarrow n \mid 3mq + q = 3(n^2+3) + q \Rightarrow n \mid q+9$. Thus, $n \le q+9$.
Now since $q < n$ and $9 < n$ we get $n \le q+9 < n+n = 2n$. Therefore, $q+9 = n$ and we get $n^2+3 = mq = m(n-9)$.
Then $m(n-9) - n^2 - 3 = 0 \Rightarrow (m-n-9)(n-9) = 84 = 3 \cdot 4 \cdot 7$.
Since $m-n-9$ is odd and $n-9$ is even $4 \mid n-9$. Since by (1) $(n-9, 3) = 1$ we get that either $m-n-9 = 3, n-9 = 4 \cdot 7$ or $m-n-9 = 3 \cdot 7, n-9 = 4$.
In the first case $(m, n) = (49, 37)$ and in the second case $(m, n) = (43, 13)$. These pairs satisfy the conditions.
Thus, there are three solutions: $(m, n) = (1, 1)$, $(49, 37)$, $(43, 13)$.