2003 AMC 10B Problem 18

This question has two halves: show that $15$ always divides the product, then show that nothing bigger in the choices always does.

Part 1: $15$ always divides.

1. When $n$ is even, $n+1, n+3, n+5, n+7, n+9$ are five odd numbers in a row.
2. Look at odd numbers and mark the multiples of $3$: $1, \underline{3}, 5, 7, \underline{9}, 11, 13, \underline{15}, \ldots$. Every third odd number is a multiple of $3$ (they are $6$ apart, and $6$ is three steps of $2$). So any three odd numbers in a row contain a multiple of $3$, and five in a row certainly do.
3. The same with $5$: the odd multiples of $5$ are $5, 15, 25, \ldots$, which are $10$ apart, and $10$ is five steps of $2$. So any five odd numbers in a row contain exactly one multiple of $5$.
4. The product therefore has a factor $3$ and a factor $5$ (from different or the same number), so $15$ always divides it.

Part 2: $165$ does not always divide.

1. The only larger choice is $165 = 3 \cdot 5 \cdot 11$. To rule it out, find one even $n$ where no factor is a multiple of $11$.
2. Try $n = 12$: the factors are $13, 15, 17, 19, 21$. None is a multiple of $11$, so $11$, and hence $165$, does not divide this product.
3. Watch out: $n = 2$ gives $3 \cdot 5 \cdot 7 \cdot 9 \cdot 11$ and $n = 4$ gives $5 \cdot 7 \cdot 9 \cdot 11 \cdot 13$, which both contain $11$. That is why testing only small $n$ is dangerous.

The answer is $\boxed{\textbf{(D)}\ 15}$.

When you step through numbers by $2$, the multiples of an odd number $k$ come up exactly once every $k$ steps. So a run of five odd numbers must hit a multiple of $3$ and of $5$, but it can skip $7$ or $11$. For "divides for every $n$" questions, prove the divisor always works, then find one example that breaks any bigger candidate.