Maths Olympiad Prep

Library / /15 of 19

Number theory Difficulty 5.3 AIME, harder Prove it United States

Problem:
A large integer is divisible by all the integers between 11 and 3030 inclusive, except for two consecutive integers. Determine those two consecutive integers.

Solution

Solution:
The two numbers must be 1616 and 1717.

First, note that if a number nn is not a power of a prime, then it has two smaller factors aa and bb that are relatively prime and multiply to nn. Thus, nn is the least common multiple of aa and bb. Then, any multiple of both aa and bb must also be a multiple of nn, so any multiple of all the numbers less than nn would have to be a multiple of nn (since two of the numbers less than nn are aa and bb). Thus, for there to be some number that is a multiple of all the numbers less than nn but not nn itself, nn must be a prime power. Therefore, both consecutive numbers are prime powers.

Note also that if nn is at most 1515, then 2n302n \leq 30. Thus, if we chose one of the consecutive numbers to be n15n \leq 15, the big number would have to be a multiple of 2n2n, and therefore also of nn. Thus, this cannot happen, so both numbers must be more than 1515. The only pair of consecutive numbers from 1616 to 3030 that are both prime powers is 1616 and 1717, so this must be the answer.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.