Exercise 1647Number theory › Divisibility and gcdOlympiadAdded 3 Nov 2026

Coprime sums and products

#coprime#sum#product

Statement

Let $a,b\in\mathbb{N}^*$ with $\gcd(a,b)=1$ . Show that $\gcd(a+b,a^2-ab+b^2)=1$ or $3$ .

Hint

Note that $a^2-ab+b^2=(a+b)^2-3ab$ . Any common divisor of $a+b$ and $a^2-ab+b^2$ divides $3ab$ and $a+b$ .

Show solutionHide solution

Solution

Setup. Let $d=\gcd(a+b,a^2-ab+b^2)$ .

$d$ divides $3ab$ . $a^2-ab+b^2=(a+b)^2-3ab$ , and $d\mid(a+b)^2$ , so $d\mid3ab$ .

$d$ coprime to $ab$ . If a prime $p\mid d$ and $p\mid ab$ : WLOG $p\mid a$ . Then $p\mid a+b$ gives $p\mid b$ , contradicting $\gcd(a,b)=1$ . So $\gcd(d,ab)=1$ .

Conclusion. $\gcd(d,3ab)=1$ and $d\mid 3ab$ together give $d\mid3$ . So $d\in\{1,3\}$ .

Coprime sums and products

Statement

Solution

More problems in Divisibility and gcd