2024 AMC 12B Problema 14

Question

¿Cuántos residuos distintos pueden resultar cuando la

100

-ésima potencia de un entero se divide entre

125

?

How many different remainders can result when the

100

th power of an integer is divided by

125?

1

2

5

25

125

Respuesta: B

Conceptos:Función φ de Euler exponenciación modular

Nivel de dificultad: 1760

Pista pequeña:

Divide en enteros coprimos con

5

y enteros divisibles entre

5

.

Split into integers coprime to

5

and integers divisible by

5

Pista grande:

Como

\varphi(125) = 100,

el teorema de Euler da

n^{100} \equiv 1 \pmod{125}

cuando

\gcd(n,5)=1;

un múltiplo de

5

tiene

n^{100}

divisible entre

125

.

Since

\varphi(125) = 100,

Euler’s theorem gives

n^{100} \equiv 1 \pmod{125}

when

\gcd(n,5)=1;

a multiple of

5

has

n^{100}

divisible by

125

Solución:

Si

n

es coprimo con

5,

entonces como

\varphi(125) = 100,

el teorema de Euler da

n^{100} \equiv 1 \pmod{125}.

Si

n

es un múltiplo de

5,

entonces

n^{100}

es divisible entre

5^{100},

y por tanto entre

125,

dejando residuo

0.

Así que los únicos residuos posibles son

0

y

1,

lo que da

2

valores distintos.

Por lo tanto, la respuesta correcta es B.

If

n

is coprime to

5,

then since

\varphi(125) = 100,

Euler’s theorem gives

n^{100} \equiv 1 \pmod{125}.

If

n

is a multiple of

5,

then

n^{100}

is divisible by

5^{100},

hence by

125,

leaving remainder

0.

So the only possible remainders are

0

and

1,

which is

2

distinct values.

Thus, the correct answer is B.