Maths Olympiad Prep

Library / CEMC Cayley /450 of 470

CEMC Cayley, 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 60⋅16=96060 \cdot 16 = 960 and 60⋅17=102060 \cdot 17 = 1020, the smallest four-digit multiple of 60 is 60⋅1760 \cdot 17.

Since 60⋅166=996060 \cdot 166 = 9960 and 60⋅167=10 02060 \cdot 167 = 10\,020, the largest four-digit multiple of 60 is 60⋅16660 \cdot 166.

This means that there are 166−17+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 240⋅4=960240 \cdot 4 = 960 and 240⋅5=1200240 \cdot 5 = 1200, the smallest four-digit multiple of 240 is 240⋅5240 \cdot 5.

Since 240⋅41=9840240 \cdot 41 = 9840 and 240⋅42=10 080240 \cdot 42 = 10\,080, the largest four-digit multiple of 240 is 240⋅41240 \cdot 41.

This means that there are 41−5+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 150−37=113150 - 37 = 113.

Want a route through all this instead of an archive? The track puts 2,604 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.