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.

When $n$ is even, $n+1, n+3, n+5, n+7, n+9$ are five consecutive odd integers.

Why $15$ always divides. Consecutive odd numbers step through residues mod $3$ in the cycle $1, 0, 2, 1, 0, 2, \dots$ (each step adds $2$), so any three in a row contain a multiple of $3$. Likewise, adding $2$ repeatedly cycles through all residues mod $5$ in five steps, so five consecutive odds contain a multiple of $5$. Hence $3 \cdot 5 = 15$ divides the product for every even $n$.

Why nothing larger among the choices. The only larger choice is $165 = 3 \cdot 5 \cdot 11$, so we need one even $n$ for which $11$ fails. Take $n = 12$: the factors are $13, 15, 17, 19, 21$, none divisible by $11$. (Also $n = 4$ gives $5 \cdot 7 \cdot 9 \cdot 11 \cdot 13$ and $n = 2$ gives $3 \cdot 5 \cdot 7 \cdot 9 \cdot 11$, both divisible by $165$, which is exactly why $165$ is offered as a trap.)

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