Question

Sea $N$ el número de ternas ordenadas de enteros positivos $(a, b, c)$ tales que $a, b, c \le 3^6$ y $a^3 + b^3 + c^3$ es múltiplo de $3^7.$ Halle el residuo cuando $N$ se divide entre $1000.$

Let $N$ denote the number of ordered triples of positive integers $(a, b, c)$ such that $a, b, c \le 3^6$ and $a^3 + b^3 + c^3$ is a multiple of $3^7.$ Find the remainder when $N$ is divided by $1000.$

Respuesta

Respuesta: 735

Conceptos:aritmética modular potencia perfecta conteo recursivo

Nivel de dificultad: 3370

Solución:

Como $(a + 3^6 t)^3 \equiv a^3 \pmod{3^7},$ el cubo de $a$ módulo $3^7$ depende solo de $a \bmod 3^6,$ y cada residuo aparece exactamente una vez en $1 \le a \le 3^6.$ Además, las únicas raíces cúbicas de $1$ módulo $3^7$ son $1 + 3^6 t,$ que coinciden todas módulo $3^6;$ por lo tanto elevar al cubo es una biyección de las $486$ unidades módulo $3^6$ sobre el conjunto de cubos de unidades módulo $3^7,$ que es exactamente el conjunto de unidades $\equiv \pm 1 \pmod 9.$ Si los tres $a, b, c$ son primos con $3$ (o exactamente uno lo es), entonces módulo $9$ la suma de cubos es $\pm 1 \pm 1 \pm 1$ o $\pm 1,$ nunca $0:$ no hay soluciones.

Exactamente un múltiplo de $3,$ digamos $c = 3z:$ para cada una de las $486$ unidades $a$ y $243$ elecciones de $c,$ el requisito $b^3 \equiv -a^3 - 27z^3 \pmod{3^7}$ tiene un lado derecho que es una unidad $\equiv \pm 1 \pmod 9,$ y por lo tanto tiene exactamente una solución $b$ módulo $3^6.$ Con $3$ elecciones de cuál variable es el múltiplo de $3,$ este caso da $3 \cdot 486 \cdot 243 = 354294$ ternas.

Los tres múltiplos de $3:$ escribiendo $a = 3x$ etc. con $x, y, z$ recorriendo módulo $3^5,$ la condición se vuelve $x^3 + y^3 + z^3 \equiv 0 \pmod{3^4},$ que depende solo de los residuos módulo $3^3,$ así que el conteo es $9^3$ veces el conteo módulo $27.$ Repitiendo el mismo análisis un nivel más abajo: el caso de dos unidades da $3 \cdot 18 \cdot 9 = 486,$ y el caso en que todos son divisibles se reduce a $u + v + w \equiv 0 \pmod 3$ con $u, v, w$ módulo $9,$ dando $243;$ es decir $486 + 243 = 729$ ternas módulo $27,$ de donde $729 \cdot 729 = 531441$ aquí. En total $N = 354294 + 531441 = 885735,$ cuyo residuo módulo $1000$ es $735.$

Since $(a + 3^6 t)^3 \equiv a^3 \pmod{3^7},$ the cube of $a$ modulo $3^7$ depends only on $a \bmod 3^6,$ and each residue occurs exactly once in $1 \le a \le 3^6.$ Moreover, the only cube roots of $1$ modulo $3^7$ are $1 + 3^6 t,$ which all agree modulo $3^6;$ hence cubing is a bijection from the $486$ units modulo $3^6$ onto the set of unit cubes modulo $3^7,$ which is exactly the set of units $\equiv \pm 1 \pmod 9.$ If all three of $a, b, c$ are prime to $3$ (or exactly one is), then modulo $9$ the sum of cubes is $\pm 1 \pm 1 \pm 1$ or $\pm 1,$ never $0:$ no solutions.

Exactly one multiple of $3,$ say $c = 3z:$ for each of the $486$ units $a$ and $243$ choices of $c,$ the requirement $b^3 \equiv -a^3 - 27z^3 \pmod{3^7}$ has a right side that is a unit $\equiv \pm 1 \pmod 9,$ hence has exactly one solution $b$ modulo $3^6.$ With $3$ choices for which variable is the multiple of $3,$ this case gives $3 \cdot 486 \cdot 243 = 354294$ triples.

All three multiples of $3:$ writing $a = 3x$ etc. with $x, y, z$ ranging modulo $3^5,$ the condition becomes $x^3 + y^3 + z^3 \equiv 0 \pmod{3^4},$ which depends only on the residues modulo $3^3,$ so the count is $9^3$ times the count modulo $27.$ Repeating the same analysis one level down: the two-unit case gives $3 \cdot 18 \cdot 9 = 486,$ and the all-divisible case reduces to $u + v + w \equiv 0 \pmod 3$ with $u, v, w$ modulo $9,$ giving $243;$ that is $486 + 243 = 729$ triples modulo $27,$ hence $729 \cdot 729 = 531441$ here. In total $N = 354294 + 531441 = 885735,$ whose remainder modulo $1000$ is $735.$

2025 AIME I Problema 15

Respuesta: 735

Nivel de dificultad: 3370

Solución:

El Problema 15 en otros años