Question

Halle el menor entero positivo

n

para el cual

2^n + 5^n - n

es un múltiplo de

1000.

Find the least positive integer

n

for which

2^n + 5^n - n

is a multiple of

1000.

Respuesta

Respuesta: 797

Conceptos:Teorema chino del resto exponenciación modular orden multiplicativo

Nivel de dificultad: 3160

Pista pequeña:

Descomponga

1000 = 8 \cdot 125:

para

n \ge 3

se necesita

n \equiv 5^n \pmod 8

y

n \equiv 2^n \pmod{125}

Split

1000 = 8 \cdot 125:

for

n \ge 3

you need

n \equiv 5^n \pmod 8

and

n \equiv 2^n \pmod{125}

Pista grande:

2^n \bmod 125

depende solo de

n \bmod 100.

Fuerce la consistencia módulo

5,

luego

25,

para fijar

n \bmod 100,

y termine con el teorema chino del resto.

2^n \bmod 125

depends only on

n \bmod 100.

Force consistency modulo

5,

then

25,

to pin down

n \bmod 100,

and finish with CRT.

Solución:

Trabajamos módulo

8

y

125.

Para

n \ge 3

tenemos

2^n \equiv 0 \pmod 8,

así que necesitamos

n \equiv 5^n \pmod 8.

Si

n

es par, entonces

5^n \equiv 1,

lo que obliga a que el número par

n

sea

\equiv 1 \pmod 8,

imposible; así que

n

es impar,

5^n \equiv 5,

y

n \equiv 5 \pmod 8.

Además

5^n \equiv 0 \pmod{125}

para

n \ge 3,

así que necesitamos

n \equiv 2^n \pmod{125}.

El orden de

2

es

4

módulo

5,

20

módulo

25,

y

100

módulo

125.

Como

n \equiv 5 \pmod 8

da

n \equiv 1 \pmod 4,

obtenemos

2^n \equiv 2 \pmod 5,

así que

n \equiv 2 \pmod 5

y por lo tanto

n \equiv 17 \pmod{20}.

Entonces

2^n \equiv 2^{17} = 2^{10} \cdot 2^7

\equiv (-1)(3) \equiv 22 \pmod{25},

así que

n \equiv 22 \pmod{25},

lo que junto con

n \equiv 1 \pmod 4

da

n \equiv 97 \pmod{100}.

Finalmente

2^{10} \equiv 24,

2^{20} \equiv 76,

2^{40} \equiv 26,

2^{80} \equiv 51 \pmod{125},

así que

\begin{aligned} &2^n \equiv 2^{97} = 2^{80} \cdot 2^{10} \cdot 2^7 \\ &\equiv 51 \cdot 24 \cdot 3 \equiv 47 \pmod{125}, \end{aligned}

lo que da

n \equiv 47 \pmod{125}.

Combinando

n \equiv 47 \pmod{125}

con

n \equiv 5 \pmod 8

se obtiene

n \equiv 797 \pmod{1000},

y

n = 1, 2

fallan por comprobación directa, así que el menor

n

de este tipo es

797.

Work modulo

8

and

125.

For

n \ge 3

we have

2^n \equiv 0 \pmod 8,

so we need

n \equiv 5^n \pmod 8.

If

n

is even then

5^n \equiv 1,

forcing the even number

n

to be

\equiv 1 \pmod 8,

impossible; so

n

is odd,

5^n \equiv 5,

and

n \equiv 5 \pmod 8.

Also

5^n \equiv 0 \pmod{125}

for

n \ge 3,

so we need

n \equiv 2^n \pmod{125}.

The order of

2

is

4

modulo

5,

20

modulo

25,

and

100

modulo

125.

Since

n \equiv 5 \pmod 8

gives

n \equiv 1 \pmod 4,

we get

2^n \equiv 2 \pmod 5,

so

n \equiv 2 \pmod 5

and hence

n \equiv 17 \pmod{20}.

Then

2^n \equiv 2^{17} = 2^{10} \cdot 2^7

\equiv (-1)(3) \equiv 22 \pmod{25},

so

n \equiv 22 \pmod{25},

which with

n \equiv 1 \pmod 4

gives

n \equiv 97 \pmod{100}.

Finally

2^{10} \equiv 24,

2^{20} \equiv 76,

2^{40} \equiv 26,

2^{80} \equiv 51 \pmod{125},

so

\begin{aligned} &2^n \equiv 2^{97} = 2^{80} \cdot 2^{10} \cdot 2^7 \\ &\equiv 51 \cdot 24 \cdot 3 \equiv 47 \pmod{125}, \end{aligned}

giving

n \equiv 47 \pmod{125}.

Combining

n \equiv 47 \pmod{125}

with

n \equiv 5 \pmod 8

yields

n \equiv 797 \pmod{1000},

and

n = 1, 2

fail by direct check, so the least such

n

is

797.

2021 AIME II Problema 13

Respuesta: 797

Nivel de dificultad: 3160

Pista pequeña:

Pista grande:

Solución:

El Problema 13 en otros años