Let $k = (a+b,a^2+b^2-ab)$. If $(a,b)=1$ then $k = 1$ or $k=3$.

Question

Yes, I know that this questions has two answers, but I can't see why $k$ can't be 27, or any other $3^n$ with $n \neq 2$.

Answer 1

Here is a simpler proof that makes it clear why that cannot occur.

${\rm mod}\ k\!:\ b\!+\!a\equiv 0\,\Rightarrow\, b\equiv -a\,\Rightarrow\, 0\equiv a^2\!+b^2\!-ab\equiv 3a^2,\, $ so $\ \color{#0a0}{k\mid 3a^2}$

But $\ k\mid a\!+\!b\,\Rightarrow\, \color{#c00}{(k,a)} = (k,a,a\!+\!b) = (k,a,b) \color{#c00}{= 1},\,$ by $\ (a,b)= 1$

Therefore, by Euclid's Lemma, $\ \color{#c00}{(k,a)=1},\ \color{#0a0}{k\mid 3a^2}\,\Rightarrow\, k\mid 3\quad $ QED

Answer 2

Following the accepted answer if $3^n|\gcd(a+b,3ab)$ with $n\gt 2$ then since $9\mid 3^n$ therefore $9|\gcd(a+b,3ab)$... now proceed according to the answer...