If $\gcd(a, b) = 1$ then prove that $\gcd(a+b, a^2-ab+b^2) = 1$ or $3$? [duplicate]

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.

Solution 4:

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