Question

If \( 2^n \) divides \( 16! \) and \( 2^{n+1} \) does not divide \( 16! \), then \( n = \)

• A. \( 14 \)
• B. \( 15 \)
• C. \( 16 \)
• D. \( 17 \)

Hint:

Legendre's formula is a powerful tool for finding the exponent of a prime \( p \) in the factorization of \( n! \). It involves summing the floor values of \( n \) divided by successive powers of \( p \). The sum is finite because eventually \( p^i \) will be greater than \( n \), making the floor value zero.

Answer 1

The Correct Option is B

We need to find the highest power of 2 that divides \( 16! \).
We can use Legendre's formula for this: The exponent of a prime \( p \) in the prime factorization of \( n! \) is given by: $$ E_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots $$ In our case, \( n = 16 \) and \( p = 2 \).
$$ E_2(16!) = \left\lfloor \frac{16}{2} \right\rfloor + \left\lfloor \frac{16}{2^2} \right\rfloor + \left\lfloor \frac{16}{2^3} \right\rfloor + \left\lfloor \frac{16}{2^4} \right\rfloor + \left\lfloor \frac{16}{2^5} \right\rfloor + \cdots $$ $$ E_2(16!) = \left\lfloor \frac{16}{2} \right\rfloor + \left\lfloor \frac{16}{4} \right\rfloor + \left\lfloor \frac{16}{8} \right\rfloor + \left\lfloor \frac{16}{16} \right\rfloor + \left\lfloor \frac{16}{32} \right\rfloor + \cdots $$ $$ E_2(16!) = \lfloor 8 \rfloor + \lfloor 4 \rfloor + \lfloor 2 \rfloor + \lfloor 1 \rfloor + \lfloor 0.
5 \rfloor + \cdots $$ $$ E_2(16!) = 8 + 4 + 2 + 1 + 0 + \cdots = 15 $$ So, the highest power of 2 that divides \( 16! \) is \( 2^{15} \).
We are given that \( 2^n \) divides \( 16! \) and \( 2^{n+1} \) does not divide \( 16! \).
This means that \( n \) is the exponent of the highest power of 2 that divides \( 16! \).
Therefore, \( n = 15 \).