Progetto Olimpiadi di Matematica GARA di SECONDO LIVELLO, 2005

Solution:

The solutions are all pairs of these three types:
(a) $(m, 1)$ for every positive integer $m$
(b) $(m, 2)$ for every positive integer $m$
(c) $(m, 3)$ for every even positive integer $m$

We can first factor out a 3 from the numerator and the denominator of the fraction:
$$\frac{3^{m}+3}{2^{n}+2^{n-1}}=\frac{3\left(3^{m-1}+1\right)}{2^{n-1}(2+1)}=\frac{3^{m-1}+1}{2^{n-1}}$$
So we must determine by which powers of 2 the number $3^{m-1}+1$ is divisible. It is trivial to note that this number is always odd, hence $(m, 1)$ and $(m, 2)$ are solutions for any value of $m$. Now, let us factor the numerator using these well-known identities:
$$x^{k}+y^{k}=(x+y)\left(x^{k-1}-x^{k-2} y+x^{k-3} y^{2}+\cdots-x y^{k-2}+y^{k-1}\right)$$
valid for $k$ odd, and
$$x^{k}-y^{k}=(x+y)\left(x^{k-1}-x^{k-2} y+x^{k-3} y^{2}+\cdots+x y^{k-2}-y^{k-1}\right)$$
valid for $k$ even. From the first, with $x=3, y=1$, we have
$$3^{m-1}+1=(3+1)\left(3^{m-2}-3^{m-3}+3^{m-4}-\cdots-3+1\right)$$
for $m$ even. Hence $3^{m-1}+1$ is a multiple of at least 4 when $m$ is even. Can it be a multiple of 8? No, because in the second parenthesis there is an odd number $(m-3)$ of odd terms, so their sum is an odd number.

Similarly, from the second identity we obtain
$$3^{m-1}-1=(3+1)\left(3^{m-2}-3^{m-3}+3^{m-4}-\cdots+3-1\right)$$
that is, $3^{m-1}-1$ is a multiple of 4 when $m$ is odd (actually it is also a multiple of 8 because this time there is an even number of terms in the parenthesis, but we will not need this in the proof). Then, since $3^{m-1}+1$ is a multiple of 4, $\left(3^{m-1}-1=+2=3^{m-1}+1\right.$ cannot also be one. Hence $3^{m-1}+1$ is a multiple of 2 but not of 4 in the case where $m$ is odd.

To sum up, we have:
- For $m$ even, $3^{m-1}+1$ is a multiple of 4 but not of 8, so the solutions are all and only those of the type $(m, 1),(m, 2)$ and $(m, 3)$ (for every even $m$)
- For $m$ odd, $3^{m-1}+1$ is a multiple of 2 but not of 4, so the solutions are all and only those of the type $(m, 1)$ and $(m, 2)$ (for every odd $m$)