2001 AMC 10 Problem 12

P11-15~3 minPrint

Divisibility & Factors Number Properties Use the answer choices (mod checks, size, form) to eliminate or select Test small/specific values or special cases to find or verify the answer

Suppose that $n$ is the product of three consecutive integers and that $n$ is divisible by $7$ . Which of the following is not necessarily a divisor of $n$ ?

Show solution without answering

Key insight

Three numbers in a row always include an even number and a multiple of 3, so the product is a multiple of 42, but not always of 4.

Solution

"Not necessarily a divisor" means we want the choice that fails for at least one allowed $n$ . So first find what is always true, then find an example that breaks the remaining choice.

What is always true.

Among any three numbers in a row, at least one is even. (Look at $5, 6, 7$ or $13, 14, 15$ .) So $n$ is always a multiple of $2$ .
Among any three numbers in a row, exactly one is a multiple of $3$ , because multiples of $3$ come every third number. So $n$ is always a multiple of $3$ .
We are told $n$ is a multiple of $7$ .
A number that is a multiple of $2$ , $3$ and $7$ is a multiple of $2 \times 3 \times 7 = 42$ . So $6$ , $14$ , $21$ and $42$ always divide $n$ . That rules out (A), (B), (C) and (E).

An example where $28$ fails.

$28 = 4 \times 7$ , so $28$ needs a factor of $4$ . Try the smallest case: $n = 5 \times 6 \times 7 = 210$ .
It is a multiple of $7$ . But $210 \div 28 = 7.5$ , not a whole number. The only even number here is $6$ , which has just one factor of $2$ .

So $28$ is not always a divisor.

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

Why this works

To show something is "not necessarily" true, one example is enough. To show the other choices are always true, use what every run of consecutive numbers must contain: an even number, a multiple of $3$ , and so on. A factor of $4$ is only guaranteed when there are two even numbers, which three in a row do not always give.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Any three consecutive integers include a multiple of $3$ and at least one even number, so their product is a multiple of $6$ . We are told $7$ divides $n$ as well, and $\gcd(6, 7) = 1$ , so $42$ divides $n$ . That guarantees choices (A), (B), (C) and (E), all of which divide $42$ .

Only (D) is left, and it is genuinely not forced: $n = 5 \cdot 6 \cdot 7 = 210$ is divisible by $7$ but $210 = 28 \cdot 7 + 14$ , so $28$ does not divide it. The product has only one factor of $2$ here because $6$ is the only even number among $5, 6, 7$ .

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

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Introduction to Number Theory, Chapter 5: Divisor Problems (§5.2, §5.3)
Introduction to Algebra, Chapter 20: Special Functions (§20.3)
Introduction to Number Theory, Chapter 13: Divisibility Rules (§13.2)