$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]

Let us start with a lemma.
Lemma For integer $m>2$, $gcd(m^{a}-1,m^{b}-1)=m^{gcd(a,b)}-1$
Proof Suppose wlg that $a>b$. Then 
\begin{align*}
gcd(m^{a}-1,m^{b}-1)= \enspace&gcd(m^{a}-1,m^{a-b}(m^{b}-1))\\
=\enspace&gcd(m^{a}-1,m^{a-b}-1)\\
=\enspace&gcd(m^{b}-1,m^{a-b}-1)
\end{align*}
since $gcd(x,y)=gcd(x,x-y)$. By reiterating, $gcd(m^{a}-1,m^{b}-1)=gcd(m^{b}-1,m^{r}-1)$ with $r$ being the rest of the euclidiean division of $a$ by $b$. We can proceed so with Euclides' algortihm until we get $gcd(m^{a}-1,m^{b}-1)=gcd(m^{dk}-1,m^{d}-1)=m^{d}-1$ where $d=gcd(a,b)$.
Since $3^{a}+1$ divides $9^{a}-1$, here we get $ab | 9^{d}-1$ with $d=gcd(a,b)$. We shall prove that this implies $d=1$, hence solving the problem since then $ab | 8$. Suppose $d>1$ and let $p$ be the smallest prime factor of $d$. Then $9^{d}=1 \pmod p$. The order of $9$ must divide both $p-1$ and $d$ so that, since $p$ is the smallest prime factor of $d$, $9$ has order $1$ and $p=2$. 
Now note that $3=-1  \pmod 4$ so that if $a$ is even $3^{a}+1=2 \pmod 4$.Consequently $a$ and $b$ can't be both even, otherwise $ab=0 \pmod 4$ and $3^{a}+1=2 \pmod 4$ which is impossible if $ab|3^{a}+1$. So $d$ cannot have $2$ as a prime factor. We get the desired contradiction, showing that $d=1$.
