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

Respuesta: 7

Conceptos:aritmética modular orden multiplicativo emparejamiento y agrupación

Nivel de dificultad: 2990

Pista pequeña:

A partir de

2^3

, todo residuo es múltiplo de

8,

y las potencias de

2

se repiten módulo

125

con período

100

From

2^3

on, every remainder is a multiple of

8,

and the powers of

2

repeat mod

125

with period

100

Pista grande:

Demuestra que

2^{50} \equiv -1 \pmod{125},

de modo que los residuos separados por

50

en el ciclo suman exactamente

1000

Show

2^{50} \equiv -1 \pmod{125},

so remainders

50

apart in the cycle sum to exactly

1000

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 por

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 por

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 por

125

y por

8,

así que es divisible por

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

Respuesta: 7

Nivel de dificultad: 2990

Pista pequeña:

Pista grande:

Solución:

El Problema 11 en otros años