Maths Olympiad Prep

Library / /223 of 241

, 2021

Number theory Difficulty 3.7 AMC 10/12 Find the answer Canada

How many four-digit positive integers are divisible by both 12 and 20, but are not divisible by 16?

Pick one

Solution

An integer is divisible by both 12 and 20 exactly when it is divisible by the least common multiple of 12 and 20.

The first few positive multiples of 20 are 20, 40, 60. Since 60 is divisible by 12 and neither 20 nor 40 is divisible by 12, then 60 is the least common multiple of 12 and 20.

Since 6016=96060 \cdot 16 = 960 and 6017=102060 \cdot 17 = 1020, the smallest four-digit multiple of 60 is 601760 \cdot 17.

Since 60166=996060 \cdot 166 = 9960 and 60167=1002060 \cdot 167 = 10\,020, the largest four-digit multiple of 60 is 6016660 \cdot 166.

This means that there are 16617+1=150166 - 17 + 1 = 150 four-digit multiples of 60.

Now, we need to remove the multiples of 60 that are also multiples of 16.

Since the least common multiple of 60 and 16 is 240, we need to remove the four-digit multiples of 240.

Since 2404=960240 \cdot 4 = 960 and 2405=1200240 \cdot 5 = 1200, the smallest four-digit multiple of 240 is 2405240 \cdot 5.

Since 24041=9840240 \cdot 41 = 9840 and 24042=10080240 \cdot 42 = 10\,080, the largest four-digit multiple of 240 is 24041240 \cdot 41.

This means that there are 415+1=3741 - 5 + 1 = 37 four-digit multiples of 240.

Finally, this means that the number of four-digit integers that are multiples of 12 and 20 but are not multiples of 16 is 15037=113150 - 37 = 113.

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

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.