Ключевой ход — алгебра и НОД. Сначала перепишем
$$a^2+b^2=(a+b{)}^2-2ab,$$ поэтому условие $a+b\mid a^2+b^2$ эквивалентно
$$a+b\mid 2ab.$$
Пусть $g=\gcd (a,b)$, $a=gx,b=gy$ и $\gcd (x,y)=1$. Тогда $a+b=g(x+y)$ и из $a+b\mid 2ab$ следует
$$g(x+y)\mid 2g^{2}xy⟹x+y\mid 2g,$$ поскольку $\gcd (x+y,x)=\gcd (x+y,y)=1$. И наоборот, любые целые $g,x,y$ с $\gcd (x,y)=1$ и $x+y\mid 2g$ дают решение $a=gx,b=gy$. (Случай $a+b=0$ исключаем — деление на ноль бессмысленно.)
Следствия и удобные частные случаи:
- Полное описание: все решения (при $a+b\ne 0$) — пары вида $a=gx,b=gy$ с $\gcd (x,y)=1$ и $x+y\mid 2g$.
- Если $\gcd (a,b)=1$ (т.е. $g=1$), то $x+y\mid 2$, значит $a+b\in \{\pm 1,\pm 2\}$.
- Если $x+y$ нечётно, то из $x+y\mid 2g$ следует $x+y\mid g$, т.е. $x+y$ делит оба $a$ и $b$.
- Неравенство: $|x+y|\le 2|g|$, отсюда сумма по модулю не слишком большая относительно общего делителя.
Методы, которые естественны здесь:
- Алгебраическое преобразование через $(a+b{)}^2-2ab$.
- Сведение по НОД: представление $a=gx,b=gy$ и использование свойств взаимной простоты $x,y$.
- Модулярный подход: подстановка $b\equiv -a(\mathrm{mod}a+b)$ даёт $2a^2\equiv 0(\mathrm{mod}a+b)$, откуда через НОД получают то же условие $x+y\mid 2g$.
Примеры: $(a,b)=(6,3)$: $g=3,x+y=3$ и $3\mid 6$ — подходит. Для взаимно простых: $(a,b)=(3,-2)$ — $a+b=1$ и $1\mid a^2+b^2$.