<s>[INST] If $\gcd(a,b)=1$, then $\gcd(a+b,a^2 -ab+b^2)=1$ or $3$. Hint:  $a^2 -ab +b^2 = (a+b)^2 -3ab.$
I know we can say that there exists an $x,y$ such that $ax + by = 1$.  So in this case,
$(a+b)x + ((a+b)^2 -3ab)y =1.$
I thought setting $x = (a+b)$ and $y = -1$ would help but that gives me $3ab =1.$  Any suggestions?
 [/INST] A solution and some generalization:
First of all, we can replace $b$ by $-b$, since $\gcd(a,b)=\gcd(a,-b)$. So we need to show $\gcd(a^2+ab+b^2,a-b)$.
If $p$ is a prime dividing the gcd, then it also divides $a-b$ which means $a \equiv b \mod p$, hence: 
$$0 = a^2+ab+b^2=a^2+a^2+a^2=3a^2 \mod p$$
So either $p|3$ or $p|a$. $p$ can't divide $a$, because then it also divides $b$ and so $\gcd(a,b) \neq 1$. Thus $p=3$. So $\gcd(a^2+ab+b^2,a-b)$ is a power of 3 (this includes 1).
Can it be divisible by 9? No, since $a^2+ab+b^2=(a-b)^2+3ab$, so if $9$ divides the gcd, it divides $(a-b)^2$ and $a^2+ab+b^2$, and so it divides $3ab$, i.e. $3|ab$, so one of $a,b$ is divisible by 3, a contradiction ($3|a-b,a\implies 3|b \implies (a,b)!= 1$).
The proof resembles Hagen von Eitzen's proof, but it can be generalized. What is very noticeable is that $a^2+ab+b^2,a-b$ are both homogenizations of Cyclotomic polynomials, $\phi_1(x)=x-1$ and $\phi_3(x)=x^2+x+1$.
The following more general statement can be proved in a similar way: let $\phi_n(x), \phi_m(x)$ be 2 Cyclotomic polynomials. Assume $m=1$ and $n=p$, a prime, so $\phi_m(x)=x-1,\phi_n(x)=x^{p-1}+x^{p-2} + \cdots + 1$.
Define their homogenization as $h_n(x,y)=\phi_n(\frac{x}{y})y^{\phi(n)}=\sum_{i=0}^{p-1}x^i y^{p-1-i},h_m(x,y)=\phi_m(\frac{x}{y})y^{\phi(m)}=x-y$.
I claim that $\gcd(x,y)=1 \implies \gcd(\phi_m(x,y),\phi_m(x,y)) \in \{1,p \}$.
Proof (for $p \neq 2$): 


*

*If a prime $q$ divides the gcd, then $\sum_{i=0}^{p-1}x^i y^{p-1-i} = px^{p-1} \equiv 0 \mod q \implies p=q$, as before.

*$p^2$ can't divide the gcd: assume $x \equiv y \mod p$, i.e. $x=y+pk$ for some integer $k$. Note that $x^i = y^i + y^{i-1}pki \mod p^2$. Thus:
$$\sum_{i=0}^{p-1}x^i y^{p-1-i} = \sum_{i=0}^{p-1} ( y^i + y^{i-1}pki) y^{p-1-i} =$$
$$p y^{p-1} + pk y^{p-2} \sum_{i=1}^{p-1} i = py^{p-1} + pk y^{p-2} \binom{p}{2} =$$
$$ y^{p-2}p (y+k\frac{p-1}{2}) \mod {p^{2}}$$
Since $p$ doesn't divide $y$ (as $\gcd(x,y)=1$), if this is zero modulo $p^2$ it means $y+k\frac{p-1}{2} \equiv 0 \mod p$, and so $p \nmid k$ (else $p|y$, contradiction), so $p^2 \nmid x-y$.
A new question arises - what are the possible values of $gcd(\phi_n(x), \phi_m(x))$, for general $n,m$? From this problem I can probably deduce a similar result for homogeneous polynomials.
EDIT: I think that the fact $\phi_n(1) = p$ if $n=p^{k}$ and $1$ otherwise should help, it gives $\gcd(h_n(x,y),h_m(x,y))=1$ if $(n,m)=1$ and one of $n,m$ is not a prime power or 1, and $\gcd(h_n(x,y),h_m(x,y))$ is a power of $p$ if $n=1, m=p^k, k>1$.
</s>