The positive integer N is divisible by 60. If the greatest common divisor of N and 500 is … — GRE General Test

The positive integer $N$ is divisible by $60$ . If the greatest common divisor of $N$ and $500$ is $100$ , which of the following statements MUST be true? Select all such statements.

$N$ is a multiple of $300$ .Answer
B
$N$ is divisible by $125$ .
The prime factorization of $N$ contains at least two factors of $2$ .Answer
D
$N$ is divisible by $9$ .
The greatest common divisor of $N$ and $250$ is $50$ .Answer

Answer

The statements asserting that

N

is a multiple of

300

, that the prime factorization of

N

contains at least two factors of

2

, and that the greatest common divisor of

N

and

250

50

must all be true.

Analyzing the prime factorizations:

60 = 2^2 \cdot 3^1 \cdot 5^1

and

500 = 2^2 \cdot 5^3

. Since

N

is divisible by

60

, the prime factorization of

N

must have exponents

a \ge 2

for prime

2

b \ge 1

for prime

3

, and

c \ge 1

for prime

5

. Furthermore,

\gcd(N, 500) = 100 = 2^2 \cdot 5^2

. The GCD rule requires taking the minimum exponent for each prime factor:

\min(a, 2) = 2 \implies a \ge 2

, and

\min(c, 3) = 2 \implies c = 2

. Therefore,

N = 2^{a} \cdot 3^{b} \cdot 5^{2}

where

a \ge 2

and

b \ge 1

. This means

N

is divisible by

2^2 \cdot 3^1 \cdot 5^2 = 300

, contains at least two prime factors of

2

, and has

\gcd(N, 250) = \gcd(2^a \cdot 3^b \cdot 5^2, 2^1 \cdot 5^3) = 2^1 \cdot 5^2 = 50

Step-by-Step Solution

Express

60

and

500

in their prime factorizations.

60 = 2^2 \cdot 3^1 \cdot 5^1

and

500 = 2^2 \cdot 5^3

Prime factorization allows us to analyze divisibility and GCD conditions in terms of prime exponents.

Apply the condition that

N

is divisible by

60

The exponent of

2

N

is at least

2

, the exponent of

3

is at least

1

, and the exponent of

5

is at least

1

For

N

to be divisible by an integer,

N

must contain at least as many of each prime factor as that integer.

Apply the GCD condition

\gcd(N, 500) = 100 = 2^2 \cdot 5^2

The exponent of

5

N

must be exactly

2

Since

500

has

5^3

and the GCD has

5^2

, taking the minimum exponent of

5

between

N

and

500

yields

2

. Thus,

N

has

5^2

and not

5^3

or higher.

Evaluate each statement against the established exponent bounds for

N

N

has prime factor powers

2^{\ge 2} \cdot 3^{\ge 1} \cdot 5^2

. This guarantees

N

is a multiple of

2^2 \cdot 3^1 \cdot 5^2 = 300

, contains at least two factors of

2

, and yields

\gcd(N, 250) = 2^1 \cdot 5^2 = 50

Comparing the prime factor requirements of each choice confirms which statements MUST be true.

Key Concept

Prime factorization rules for divisibility and greatest common divisor (GCD)

Question

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Topics

More questions from this topic