If m and n are positive integers such that 3^m \cdot 5^n is a factor of 15!, what is the m… — GMAT

If $m$ and $n$ are positive integers such that $3^m \cdot 5^n$ is a factor of $15!$ , what is the maximum possible value of $m + n$ ?

To find the maximum power of a prime

p

dividing

n!

, we sum

\lfloor n/p^k \rfloor

for all

k \ge 1

. For

p = 3

m = \lfloor 15/3 \rfloor + \lfloor 15/9 \rfloor = 5 + 1 = 6

. For

p = 5

n = \lfloor 15/5 \rfloor = 3

. Thus, the maximum value of

m + n

6 + 3 = 9

Find the maximum exponent

m

of the prime factor 3 in

15!

using Legendre's formula.

m = \lfloor \frac{15}{3} \rfloor + \lfloor \frac{15}{3^2} \rfloor = 5 + 1 = 6

The prime factor 3 appears in multiples of 3 (3, 6, 9, 12, 15) and contributes an extra factor in 9 (

3^2

Find the maximum exponent

n

of the prime factor 5 in

15!

using Legendre's formula.

n = \lfloor \frac{15}{5} \rfloor = 3

The prime factor 5 appears in multiples of 5 (5, 10, 15).

Sum the maximum possible integer values of

m

and

n

m + n = 6 + 3 = 9

The maximum possible value of

m+n

is the sum of the maximum individual prime exponents.

Counting Prime Factors in a Factorial (Legendre's Formula)

List out the prime factorizations of all numbers from 1 to 15: 3 contributing numbers are 3, 6 (

2 \cdot 3

), 9 (

3^2

), 12 (

2^2 \cdot 3

), 15 (

3 \cdot 5

). Total factors of 3 =

1 + 1 + 2 + 1 + 1 = 6

. 5 contributing numbers are 5, 10 (

2 \cdot 5

), 15 (

3 \cdot 5

). Total factors of 5 =

1 + 1 + 1 = 3

. Sum

6 + 3 = 9

Estimated Time:1m 30s

Question