Find all integers $m, n \geq 1$ such that $m n$ divides $3^{m}+1$ and $m n$ divides $3^{n}+1$.
Suppose $m, n \geq 2$. Let $p$ be the smallest divisor of $n$. Then $3^{2 n} \equiv 1 \bmod p$. Let $\omega$ be the order of 3 modulo $p$. Then $\omega$ divides $2 n$. On the other hand, by Fermat's Little Theorem, $3^{p-1} \equiv 1 \bmod p$. Thus $\omega$ divides $p-1$. We conclude that $\omega$ divides $\operatorname{gcd}(p-1, 2 n)$. Given the condition on $p$, we necessarily have $\omega=1$ or 2. In the first case,

In the first case, $3 \equiv 1 \bmod p$ and thus $p=2$. In the second case, $3^{2} \equiv 1 \bmod p$ and thus $p=2$. We conclude that $n$ is even. We show similarly that $m$ is even. Then 4 divides $3^{m n}+1$, which is not possible since $m n$ is even.

It remains to examine the case where $m$ or $n$ equals 1, and it follows that the solutions are $(1,1),(1,2)$ and $(2,1)$.