Question

Halle el menor entero positivo $n$ tal que cuando $3^n$ se escribe en base $143,$ sus dos dígitos más a la derecha en base $143$ son $01.$

Find the least positive integer $n$ such that when $3^n$ is written in base $143,$ its two right-most digits in base $143$ are $01.$

Respuesta

Respuesta: 195

Conceptos:orden multiplicativo aritmética modular teorema del binomio mínimo común múltiplo

Nivel de dificultad: 2990

Pista pequeña:

La condición dice $3^n \equiv 1 \pmod{143^2};$ trabaje módulo $11^2$ y $13^2$ por separado, notando que $3^5 = 243 = 2 \cdot 11^2 + 1$

The condition says $3^n \equiv 1 \pmod{143^2};$ work modulo $11^2$ and $13^2$ separately, noting $3^5 = 243 = 2 \cdot 11^2 + 1$

Pista grande:

Como $3^3 = 1 + 2 \cdot 13,$ el teorema del binomio da $3^{3k} \equiv 1 + 26k \pmod{13^2};$ determine cuándo esto es $1,$ luego tome el mínimo común múltiplo

Since $3^3 = 1 + 2 \cdot 13,$ the binomial theorem gives $3^{3k} \equiv 1 + 26k \pmod{13^2};$ determine when this is $1,$ then take an lcm

Solución:

Los dos últimos dígitos en base $143$ son $01$ exactamente cuando $3^n \equiv 1 \pmod{143^2},$ y como $143^2 = 11^2 \cdot 13^2,$ esto se cumple exactamente cuando $3^n \equiv 1$ módulo tanto $11^2$ como $13^2.$

Módulo $121:$ $3^5 = 243 = 2 \cdot 121 + 1 \equiv 1,$ y como $5$ es primo y $3 \not\equiv 1,$ el orden de $3$ es exactamente $5.$ Módulo $169:$ el orden de $3$ módulo $13$ es $3,$ así que el orden módulo $169$ es un múltiplo de $3.$ Escribiendo $3^3 = 27 = 1 + 26$ y notando que $26^2 = 4 \cdot 169 \equiv 0 \pmod{169},$ el teorema del binomio da $3^{3k} = (1 + 26)^k$ $\equiv 1 + 26k \pmod{169},$ que es $1$ exactamente cuando $k$ es múltiplo de $13.$ Así el orden de $3$ módulo $169$ es $39.$

Por lo tanto $n$ debe ser un múltiplo común de $5$ y $39,$ y el menor es $\operatorname{lcm}(5, 39) = 195.$

The last two base- $143$ digits are $01$ exactly when $3^n \equiv 1 \pmod{143^2},$ and since $143^2 = 11^2 \cdot 13^2,$ this holds exactly when $3^n \equiv 1$ modulo both $11^2$ and $13^2.$

Modulo $121:$ $3^5 = 243 = 2 \cdot 121 + 1 \equiv 1,$ and since $5$ is prime and $3 \not\equiv 1,$ the order of $3$ is exactly $5.$ Modulo $169:$ the order of $3$ modulo $13$ is $3,$ so the order modulo $169$ is a multiple of $3.$ Writing $3^3 = 27 = 1 + 26$ and noting $26^2 = 4 \cdot 169 \equiv 0 \pmod{169},$ the binomial theorem gives $3^{3k} = (1 + 26)^k$ $\equiv 1 + 26k \pmod{169},$ which is $1$ exactly when $k$ is a multiple of $13.$ So the order of $3$ modulo $169$ is $39.$

Therefore $n$ must be a common multiple of $5$ and $39,$ and the least is $\operatorname{lcm}(5, 39) = 195.$

2018 AIME I Problema 11

Respuesta: 195

Nivel de dificultad: 2990

Pista pequeña:

Pista grande:

Solución:

El Problema 11 en otros años