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

Solución. La suma de los dígitos de un número tiene el mismo resto que el número al dividirla por $9$. Por tanto, el dígito que resulta al final de hacer sumas reiteradas de dígitos es el propio resto del número o bien $9$ (si el resto es $0$). Entonces, se trata de ver si hay más números que dan resto $1$ o más números que dan resto $2$ del $1$ al $10^9$. Como empezamos en $1$ y terminamos en $10^9$, ambos dan resto $1$ y el resto se repite periódicamente, deducimos que hay exactamente un número más que da resto $1$ que números que dan resto $2$. Por lo tanto, habrá más unos entre los $10^9$ resultados.

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.

Solución. Observemos que $f^n(x)$ es un polinomio con coeficientes enteros y vamos a probar que su término independiente es $1$. Esto se prueba fácilmente por inducción sobre $n$, teniendo en cuenta que el término independiente se obtiene evaluando en $x=0$. Para $n=1$, tenemos que $f^1(0)=f(0)=1$; supuesto cierto que $f^n(0)=1$ para cierto $n\geq1$, podemos calcular $f^{n+1}(0)=f(f^n(0))=f(1)=1$.

Esto nos dice que, para cada $n\in\mathbb{N}$ podemos expresar $f^{n-1}(x)=x p_{n-1}(x)+1$ para cierto polinomio $g_{n-1}(x)$. Tenemos así que \begin{align*} \mathrm{mcd}(f(x),f^n(x))&=\mathrm{mcd}(f(x),f^{n-1}(f(x)))\\ &=\mathrm{mcd}(f(x),f(x) p_{n-1}(f(x))+1)=1. \end{align*}

Nota. El resultado es también cierto cambiando $f(x)=x^{1997}-x+1$ por cualquier polinomio $f(x)$ con coeficientes enteros y $f(0)=f(1)=1$. También es cierto que $f^n(y)$ y $f^m(y)$ son primos relativos para cualesquier $m,n\in\mathbb{N}$ (basta aplicar el enunciado a $x=f^{m-1}(y)$ con $n+1$ en lugar de $n$).