2016 AMC 12B Problema 24

Question

Hay exactamente

77{,}000

cuádruplas ordenadas

(a,b,c,d)

tales que

\gcd(a,b,c,d)=77

y

\text{lcm}(a,b,c,d)=n.

¿Cuál es el menor valor posible de

n

?

There are exactly

77{,}000

ordered quadruples

(a,b,c,d)

such that

\gcd(a,b,c,d)=77

and

\text{lcm}(a,b,c,d)=n.

What is the smallest possible value of

n?

13{,}860

20{,}790

21{,}560

27{,}720

41{,}580

Respuesta: D

Conceptos:máximo común divisor mínimo común múltiplo factorización en primos

Nivel de dificultad: 2550

Pista pequeña:

Divide todo entre

77.

Con

m=\frac{n}{77},

necesitas cuádruplas reducidas de mcd

1

y mcm

m,

analizadas primo por primo.

Divide everything by

77.

With

m=\frac{n}{77},

you need reduced quadruples of gcd

1

and lcm

m,

analyzed one prime at a time

Pista grande:

Para un primo con exponente máximo

M,

la cantidad de cuádruplas de exponentes es

2(6M^2+1).

Usa la factorización de

77000

para determinar cuántos primos dividen a

m

y qué valores puede tomar

M

For a prime with maximum exponent

M,

the count of exponent quadruples is

2(6M^2+1).

Use the factorization of

77000

to determine how many primes divide

m

and which values of

M

can occur

Solución:

Al escribir cada entrada como

77

por un valor reducido, necesitamos

\gcd=1

y

\text{lcm}=m=\frac{n}{77}.

Para cada primo

p

que divide a

m

con exponente máximo

M,

la cantidad de cuádruplas de exponentes válidas es

(M+1)^4-2M^4

+(M-1)^4

=2(6M^2+1).

El producto sobre todos los primos debe ser

77{,}000=2^3\cdot5^3\cdot7\cdot11.

Como

2(6M^2+1)

vale

14,

50,

y

110

para

M=1,2,3,

y

14\cdot50\cdot110=77{,}000,

los exponentes

1,2,3

dan una factorización candidata.

Cada primo aporta exactamente un factor

2,

así que exactamente tres primos dividen a

m.

Sus factores impares

6M^2+1

deben dividir a

\frac{77{,}000}{2^3}=9625.

Al revisar los divisores se obtiene

M=1,2,3,8,

con factores impares

7,25,55,385.

La opción

M=8

deja solo

25

como producto de los otros dos factores impares, pero cada uno es al menos

7,

lo cual es imposible. Por tanto, los exponentes máximos son exactamente

1,2,3.

Para minimizar

m=\frac{n}{77},

asignamos el exponente mayor al primo menor:

m=2^3\cdot3^2\cdot5=360,

así que

n=77\cdot360=27{,}720.

Por lo tanto, la respuesta correcta es D.

Writing each entry as

77

times a reduced value, we need

\gcd=1

and

\text{lcm}=m=\frac{n}{77}.

For each prime

p

dividing

m

with maximum exponent

M,

the number of valid exponent quadruples is

(M+1)^4-2M^4

+(M-1)^4

=2(6M^2+1).

The total over all primes must equal

77{,}000=2^3\cdot5^3\cdot7\cdot11.

Since

2(6M^2+1)

equals

14,

50,

and

110

for

M=1,2,3,

and

14\cdot50\cdot110=77{,}000,

the exponents

1,2,3

give one candidate factorization.

Every prime contributes exactly one factor of

2,

so exactly three primes divide

m.

Their odd factors

6M^2+1

must divide

\frac{77{,}000}{2^3}=9625.

Checking the divisors gives

M=1,2,3,8,

with odd factors

7,25,55,385.

The choice

M=8

leaves only

25

for the product of the other two odd factors, but each is at least

7,

so this is impossible. Therefore the maximum exponents are exactly

1,2,3.

To minimize

m=\frac{n}{77},

assign the largest exponent to the smallest prime:

m=2^3\cdot3^2\cdot5=360,

so

n=77\cdot360=27{,}720.

Thus, the correct answer is D.