$ab$ divides $3^a+1$ and $3^b+1$ Find all positive integers $a,b$ such that $ab$ divides $3^a+1$ and $3^b+1$.
It is clear that $3$ cannot divide either $a$ or $b$, because $3$ doesn't divide $3^a+1$ or $3^b+1$. 
$(a,b)=(1,1),(2,1),(1,2)$ all work. If $b=1$, the condition reduces to $a$ divides $3^a+1$ and $4$, so $a=1,2,4$, but this has already been covered.
[Source: Korean competition problem]

Here is an unfinished idea. Maybe it's useful, maybe not - I'll post it and anyone is welcome to try to finish or adapt it. 

Of course, a number $n$ divides both $x$ and $y$ if and only if $n$ divides $\gcd(x,y)$.
Assume without loss of generality that $b\geq a$, and write $b=qa+r$ for $0\leq r<a$. Observe that
$$\begin{align*}
\gcd(3^a+1,3^b+1)=\gcd(3^a+1,3^b-3^a)&=\gcd(3^a+1,3^{b-a}-1)\\
=\gcd(3^a+1,3^{b-a}+3^a)&=\gcd(3^a+1,3^{b-2a}+1)\\
&=\cdots\\
&=\gcd(3^a+1,3^r+(-1)^q)
\end{align*}$$
In fact by making an analogous argument, we always have
$$\gcd(3^a\pm1,3^b\pm 1)=\gcd(3^a\pm1,3^r\pm 1)\qquad \text{(signs not intended to match)}$$
Therefore, we can conclude
$$\gcd(3^a\pm 1,3^b\pm 1)=\gcd(3^a\pm1,3^{\gcd(a,b)}\pm 1)=\gcd(3^{\gcd(a,b)}\pm1,3^{\gcd(a,b)}\pm1)\\
=\begin{cases}
3^{\gcd(a,b)}\pm 1  & \text{if signs match},\\
2 & \text{if signs don't match}
\end{cases}$$
Suppose that $\gcd(3^a+1,3^b+1)=3^{\gcd(a,b)}\pm 1$. Then to say that this is divisible by $ab$ means
$$3^{\gcd(a,b)}\equiv\pm1\bmod ab$$
Thus, the order of $3$ in $(\mathbb{Z}/ab\mathbb{Z})^\times$ divides $2\gcd(a,b)$. Of course it also must divide $\varphi(ab)$... but that's not a contradiction yet.
