Progetto Olimpiadi di Matematica GARA di SECONDO LIVELLO, 2005

Solution:

The answer is (C). Let us first consider $d = MCD(a+b, a-b)$. The GCD of two numbers also divides their sum and their difference, so $d$ divides $2a$ and $2b$. Since $a$ and $b$ are coprime, no odd prime can appear in $d$, and $2$ appears at most with exponent $1$ (this happens if and only if $a$ and $b$ are both odd).

Moving on to the case $c = MCD((a+b)^n, a-b)$, one observes that the prime factors of $(a+b)^n$ are the same as those of $a+b$, with the exponents multiplied by $n$, so $c$ is a power of $2$ (and it remains $1$ if $a$ and $b$ are not both odd). In that case, however, $a+b$ and $a-b$ cannot both be multiples of $4$, because their difference $2b$ is not.

Now if $a-b$ is not a multiple of $4$, then $c$ cannot be either. So what remains is the case in which $a+b$ is not a multiple of $4$, and hence $c$ can be at most $2^n$. But this value can always be attained, just take for example $a = 2^n + 1$, $b = 1$.