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?

Solution 1:

We have $\gcd(a+b,a^2-ab+b^2)=\gcd(a+b,3ab)$. If $p$ is a prime with $p|\gcd(a+b,3ab)$, then $p=3$ or $p|a$ or $p|b$. If $p|a$, then $p\nmid b$, hence $p\nmid a+b$. Similarly, if $p|b$, then $b\nmid a+b$. Thus we conclude $p=3$. But then if $9|\gcd(a+b,3ab)$, clearly $3|a$ or $3|b$ and again $3\nmid a+b$.

Solution 2:

Hint $\,\ c\mid a\!+\!b,\overbrace{a^2\!-\!ab\!+\!b^2}^{\large f(b)}\Rightarrow\,c\mid 3a^2,3ab,3b^2\Rightarrow\,c\mid(3a^2,3ab,3b^2)=3(a,b)^2 = 3 $

by $\,\ {\rm mod}\ \ a\!+\!b\!:\ \ \color{#c00}{b\equiv -a}\,\Rightarrow\, f(\color{#c00}b)\equiv f(\color{#c00}{-a})\equiv 3a^2\equiv 3a(-b)\equiv 3(-b)(-b) $

Solution 3:

$\gcd(a+b, a^2 - ab + b^2) = \gcd(a+b, (a+b)^2 - 3ab) = \gcd(a+b, 3ab)$

Since $\gcd(a,b) = 1$ hence $\gcd(a+b,a) = 1$ and $\gcd(a+b, b)$ = 1.

Thus, $\gcd(a+b, 3ab) = \gcd (a+b, 3) $ by applying the Lemma below.

Hence, $\gcd(a+b, a^2 -ab + b^2) = \gcd(a+b, 3)=1$ or 3. (This is very simple to evaluate for given values.)

Lemma If $\gcd(m,n) = 1$, then $\gcd (m, np) = \gcd(m,p)$.

Proof: This is obvious when you consider GCD via prime factorization.