Let S be the set of all positive integers n such that the least common multiple of n and 4… — ACT

Let $S$ be the set of all positive integers $n$ such that the least common multiple of $n$ and $40$ is $360$ , and the greatest common divisor of $n$ and $100$ is a prime number. What is the sum of all possible values of $n$ in set $S$ ?

A
18
B
45
63Answer
D
72
E
153

Answer

To find the sum of all possible values of

n

, we first analyze the prime factorizations:

40 = 2^3 \times 5

and

360 = 2^3 \times 3^2 \times 5

. The least common multiple of

n

and

40

360

, meaning

n

must be of the form

2^a \times 3^2 \times 5^c

where

0 \le a \le 3

and

0 \le c \le 1

. Testing the candidate values against the condition that

\text{GCD}(n, 100)

must be a prime number (where

100 = 2^2 \times 5^2

) reveals that only

n = 18

(with GCF of

2

) and

n = 45

(with GCF of

5

) satisfy the conditions. The sum of these values is

18 + 45 = 63

Step-by-Step Solution

Find the prime factorizations of the given numbers:

40

and

360

40 = 2^3 \times 5

and

360 = 2^3 \times 3^2 \times 5

Expressing the numbers in their prime factorizations helps determine the required prime factors of

n

to satisfy the least common multiple condition.

Determine the constraints on the prime factorization of

n

based on

\text{LCM}(n, 40) = 360

n

must be of the form

2^a \times 3^2 \times 5^c

, where

0 \le a \le 3

and

0 \le c \le 1

Since the least common multiple is the product of the highest powers of all prime factors present in either number,

n

must provide

3^2

(as

40

has

3^0

), can have

2^a

up to

2^3

, and can have

5^c

up to

5^1

List all 8 possible candidate values for

n

For

c=0

n \in \{9, 18, 36, 72\}

. For

c=1

n \in \{45, 90, 180, 360\}

Evaluating all combinations of the exponents

a

and

c

generates the complete list of candidates.

Calculate the greatest common divisor of each candidate

n

with

100 = 2^2 \times 5^2

, and check if the result is prime.

\text{GCD}(9, 100) = 1

(not prime);

\text{GCD}(18, 100) = 2

(prime);

\text{GCD}(36, 100) = 4

(not prime);

\text{GCD}(72, 100) = 4

(not prime);

\text{GCD}(45, 100) = 5

(prime);

\text{GCD}(90, 100) = 10

(not prime);

\text{GCD}(180, 100) = 20

(not prime);

\text{GCD}(360, 100) = 20

(not prime). The valid values for

n

are

18

and

45

Only

n = 18

and

n = 45

satisfy the condition that their greatest common divisor with

100

is a prime number (

2

and

5

, respectively).

Calculate the sum of the possible values of

n

18 + 45 = 63

Summing the identified valid values yields the final answer.

Key Concept

Determining possible values of an unknown integer using prime factorization constraints from least common multiple (LCM) and greatest common divisor (GCD) conditions.

Question

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Topics

More questions from this topic