2018 AMC 10A Problem 22

Question

Let

a,

b,

c,

and

d

be positive integers such that

\gcd(a, b)=24,

\gcd(b, c)=36,

\gcd(c, d)=54,

and

70 < \gcd(d, a) < 100.

Which of the following must be a divisor of

a?

5

7

11

13

17

Answer: D

Concepts:greatest common divisor prime factorization bounding to limit cases

Difficulty rating: 2010

Small hint:

Track the forced powers of

2

and

3

in the gcds

Big hint:

The remaining factor of

\gcd(d,a)

must lie between

12

and

17

Solution:

From

\gcd(a,b)=24=2^3\cdot3

and

\gcd(b,c)=36=2^2\cdot3^2

, the number

a

is divisible by

2^3\cdot3

but not by

3^2

.

From

\gcd(b,c)=36

and

\gcd(c,d)=54=2\cdot3^3

, the number

d

is divisible by

2\cdot3^3

but not by

2^2

. Therefore

\gcd(d,a)=2\cdot3\cdot n

, where

n

has no factor

2

or

3

.

Since

70<6n<100,

the integer

n

satisfies

12\le n\le16.

The only value in this range with no factor

2

or

3

is

13,

so

13

must divide

a.

Thus, D is the correct answer.