Question

¿Cuántos múltiplos enteros positivos de $1001$ se pueden expresar en la forma $10^{j} - 10^{i},$ donde $i$ y $j$ son enteros y $0 \le i \lt j \le 99$ ?

How many positive integer multiples of $1001$ can be expressed in the form $10^{j} - 10^{i},$ where $i$ and $j$ are integers and $0 \le i \lt j \le 99?$

Respuesta

Solución:

Factoriza $10^j - 10^i = 10^i(10^{j-i} - 1).$ Como $1001 = 7 \cdot 11 \cdot 13$ es coprimo con $10^i,$ necesitamos $1001 \mid 10^{j-i} - 1.$ El orden multiplicativo de $10$ es $6$ módulo $7,$ $2$ módulo $11,$ y $6$ módulo $13,$ así que $10^k \equiv 1 \pmod{1001}$ exactamente cuando $k$ es múltiplo de $6.$ Pares distintos $(i, j)$ dan valores distintos, así que basta con contar los pares.

Para $j - i = 6d$ con $1 \le d \le 16,$ el índice $i$ puede ser $0, 1, \ldots, 99 - 6d,$ lo que da $100 - 6d$ opciones. El total es $\begin{aligned} &\sum_{d=1}^{16} (100 - 6d) \\ &= 94 + 88 + \cdots + 4 \\ &= \frac{(94 + 4) \cdot 16}{2} \\ &= 784. \end{aligned}$

Factor $10^j - 10^i = 10^i(10^{j-i} - 1).$ Since $1001 = 7 \cdot 11 \cdot 13$ is coprime to $10^i,$ we need $1001 \mid 10^{j-i} - 1.$ The multiplicative order of $10$ is $6$ modulo $7,$ $2$ modulo $11,$ and $6$ modulo $13,$ so $10^k \equiv 1 \pmod{1001}$ exactly when $k$ is a multiple of $6.$ Distinct pairs $(i, j)$ give distinct values, so we just count the pairs.

For $j - i = 6d$ with $1 \le d \le 16,$ the index $i$ can be $0, 1, \ldots, 99 - 6d,$ giving $100 - 6d$ choices. The total is $\begin{aligned} &\sum_{d=1}^{16} (100 - 6d) \\ &= 94 + 88 + \cdots + 4 \\ &= \frac{(94 + 4) \cdot 16}{2} \\ &= 784. \end{aligned}$

2001 AIME II Problema 10

Solución:

El Problema 10 en otros años