Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Supongamos que $d\geq 2$ es un divisor común a $m^2+n^2$ y $m+n$. Entonces también es un divisor de $(m+n)^2-(m^2+n^2)=2mn$ pero no puede ser divisor de $m$ ni de $n$ (al ser divisor de $m+n$, si lo fuera también de $m$, lo sería de $n=(m+n)-m$, pero $m$ y $n$ son primos relativos). Por lo tanto, $d$ debe dividir a $2$ y no queda otra que $d=2$.

Como el máximo común divisor de $m+n$ y $m^2+n^2$ es, en particular, un divisor común, tiene que ser $1$ o $2$. Será igual a $2$ cuando $m$ y $n$ tengan la misma paridad y $1$ cuando tengan distinta paridad.