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

Question

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?

Answer 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$.

Answer 2

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$):

1. 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.

2. $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$.