Let M be a positive odd integer that is divisible by 45 but not by 27. If M has exactly 36… — GMAT

Let $M$ be a positive odd integer that is divisible by $45$ but not by $27$ . If $M$ has exactly $36$ positive divisors, what is the maximum possible number of distinct prime factors of $M$ ?

A
3
4Answer
C
5
D
6
E
7

Answer

The number of positive divisors of an integer with prime factorization

p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}

is given by

(e_1+1)(e_2+1)\dots(e_k+1)

. Because

M

is divisible by

45 = 3^2 \times 5

but not by

27 = 3^3

, the prime factor

3

must have an exponent of exactly

2

, which contributes a multiplier of

(2+1) = 3

to the total divisor count. Dividing the total

36

divisors by

3

leaves a product of

12

for the remaining terms

(e_i+1)

. To maximize the number of distinct prime factors, we write

12

as a product of as many integers greater than

1

as possible, which is

3 \times 2 \times 2

(3 factors). Adding the prime factor

3

gives a maximum of

1 + 3 = 4

distinct prime factors.

Step-by-Step Solution

Determine the prime factorization constraints from the given conditions.

M = 3^2 \cdot 5^a \cdot p_1^{b_1} \cdot p_2^{b_2} \cdots p_r^{b_r}

, where

a \ge 1

b_i \ge 1

, and

p_i

are distinct odd primes other than

3

and

5

Since

M

is odd,

2

is not a prime factor. Since

M

is divisible by

45 = 3^2 \times 5

but not by

27 = 3^3

, the exponent of

3

must be exactly

2

, and the exponent of

5

is at least

1

Set up the formula for the number of positive divisors.

f(M) = (2 + 1)(a + 1)(b_1 + 1)(b_2 + 1) \cdots (b_r + 1) = 36

, which simplifies to

(a + 1)(b_1 + 1)(b_2 + 1) \cdots (b_r + 1) = 12

The number of divisors of a number

n = q_1^{e_1} q_2^{e_2} \cdots q_k^{e_k}

(e_1 + 1)(e_2 + 1) \cdots (e_k + 1)

Maximize the number of terms in the product yielding

12

The maximum number of factors greater than

1

whose product is

12

3

, since

12 = 3 \times 2 \times 2

Each factor greater than

1

(a+1)(b_1+1)\dots(b_r+1)

corresponds to a distinct prime factor of

M

(other than

3

Calculate the maximum total number of distinct prime factors of

M

Total distinct prime factors =

1 \text{ (for 3)} + 3 \text{ (from the factorization of 12)} = 4

The prime factors are

3

5

p_1

, and

p_2

, giving

4

distinct prime factors in total.

Key Concept

Divisor Count Formula and Prime Factorization Constraints

Estimated Time:2m 0s

Question

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Topics

More questions from this topic