$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]
 A: 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$.
A: 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.
