, 2013

Denote $a = 2^{2n} + 2^{n+1} + 1$ and $b = 2^{2m} + 2^{m+1} + 1$. We notice that $a = (2^n + 1)^2$ and $b = (2^m + 1)^2$. Because we have $(2^{2n} - 1)^2 = (2^n + 1)^2(2^n - 1)^2 = a(2^n - 1)^2$ and $(2^{2m} - 1)^2 = b(2^m - 1)^2$, the greatest common divisor $D(a,b)$ divides $D((2^{2n} - 1)^2, (2^{2m} - 1)^2)$. We also know that
$$D((2^{2n} - 1)^2, (2^{2m} - 1)^2) = D(2^{2n} - 1, 2^{2m} - 1)^2 = (2^{D(2m,2n)} - 1)^2.$$
This equals $(2^2 - 1)^2 = 9$ because numbers $m$ and $n$ are coprime. The greatest common divisor $D(a,b)$ can thus only be 1, 3 or 9.
But one of the numbers $n$ and $m$ must be even since they are of different parity. Suppose this is $n$. We then have $2^n \equiv 1 \pmod 3$ and hence $a = (2^n+1)^2 \equiv (1+1)^2 \equiv 1 \pmod 3$. This is to say, number $a$ is not divisible by 3, it is coprime to 3. The greatest common divisor $D(a,b)$ of the numbers $a$ and $b$ must thus be 1, which means that $a$ and $b$ are coprime.