Question

Sea $R$ el conjunto de todos los residuos posibles cuando un número de la forma $2^n,$ con $n$ entero no negativo, se divide entre $1000.$ Sea $S$ la suma de los elementos de $R.$ Halla el residuo cuando $S$ se divide entre $1000.$

Let $R$ be the set of all possible remainders when a number of the form $2^n,$ $n$ a nonnegative integer, is divided by $1000.$ Let $S$ be the sum of the elements in $R.$ Find the remainder when $S$ is divided by $1000.$

Respuesta

Solución:

Los residuos $2^0 = 1,$ $2^1 = 2,$ y $2^2 = 4$ aparecen, y para $n \ge 3$ todo $2^n$ es divisible entre $8.$ Módulo $125$ las potencias de $2$ para $n \ge 3$ se repiten con período $100,$ así que $R$ consta de $1,$ $2,$ $4,$ y los $100$ residuos distintos de $2^3, 2^4, \ldots, 2^{102}.$

El hecho clave es $2^{50} \equiv -1 \pmod{125}:$ en efecto $2^{50} + 1 = (2^{10} + 1)$ $\cdot (2^{40} - 2^{30} + 2^{20} - 2^{10} + 1),$ donde $2^{10} + 1 = 1025$ es divisible entre $25$ y el segundo factor es $\equiv 1 + 1 + 1 + 1 + 1$ $\equiv 0 \pmod 5$ porque $2^{10} \equiv -1 \pmod 5.$ Por lo tanto, para $n \ge 3,$ la suma $2^{n+50} + 2^n$ es divisible entre $125$ y entre $8,$ así que entre $1000.$

Emparejar cada residuo del ciclo con el que está $50$ pasos después da entonces $50$ pares de residuos distintos, cada par sumando exactamente $1000,$ así que esos $100$ residuos contribuyen un múltiplo de $1000$ a $S.$ Por lo tanto, $S \equiv 1 + 2 + 4 = 7 \pmod{1000}.$

The remainders $2^0 = 1,$ $2^1 = 2,$ and $2^2 = 4$ occur, and for $n \ge 3$ every $2^n$ is divisible by $8.$ Modulo $125$ the powers of $2$ for $n \ge 3$ repeat with period $100,$ so $R$ consists of $1,$ $2,$ $4,$ and the $100$ distinct remainders of $2^3, 2^4, \ldots, 2^{102}.$

The key fact is $2^{50} \equiv -1 \pmod{125}:$ indeed $2^{50} + 1 = (2^{10} + 1)$ $\cdot (2^{40} - 2^{30} + 2^{20} - 2^{10} + 1),$ where $2^{10} + 1 = 1025$ is divisible by $25$ and the second factor is $\equiv 1 + 1 + 1 + 1 + 1$ $\equiv 0 \pmod 5$ because $2^{10} \equiv -1 \pmod 5.$ Hence for $n \ge 3,$ the sum $2^{n+50} + 2^n$ is divisible by $125$ and by $8,$ so by $1000.$

Pairing each remainder in the cycle with the one $50$ steps later therefore gives $50$ pairs of distinct remainders, each pair summing to exactly $1000,$ so those $100$ remainders contribute a multiple of $1000$ to $S.$ Thus $S \equiv 1 + 2 + 4 = 7 \pmod{1000}.$

2011 AIME I Problema 11

Solución:

El Problema 11 en otros años