Exercise 1651Number theory › Divisibility and gcdOlympiadAdded 3 Nov 2026

GCD of sums

#gcd#sums#congruence

Statement

Let $a,b\in\mathbb{Z}$ . Show that $\gcd(a+b,a^2+b^2)$ divides $2\gcd(a,b)^2$ .

Hint

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

Show solutionHide solution

Solution

Setup. $d=\gcd(a+b,a^2+b^2)$ . Then $d\mid a+b$ and $d\mid a^2+b^2=(a+b)^2-2ab$ , so $d\mid 2ab$ .

Bound. Since $d\mid a+b$ , let $g=\gcd(a,b)$ and $a=ga'$ , $b=gb'$ with $\gcd(a',b')=1$ . Then $d\mid g(a'+b')$ and $d\mid2g^2a'b'$ . Since $\gcd(a'+b',a'b')=1$ (shown earlier), $d$ divides $2g^2$ .

Conclusion. $\gcd(a+b,a^2+b^2)\mid2\gcd(a,b)^2$ .

GCD of sums

Statement

Solution

More problems in Divisibility and gcd