Maths Olympiad Prep

Library / /52 of 80

Number theory Difficulty 5.1 AIME, harder Prove it North Macedonia

How many numbers divisible by 30200830^{2008} are not divisible by 20200720^{2007}?

Solution

Since 302008=22008320085200830^{2008} = 2^{2008} \cdot 3^{2008} \cdot 5^{2008} and 202007=240145200720^{2007} = 2^{4014} \cdot 5^{2007}, all the numbers divisible by 30200830^{2008} and not divisible by 20200720^{2007} are:

1) 2k3l5m2^{k} \cdot 3^{l} \cdot 5^{m}, l=1,2,,2008l = 1, 2, \ldots, 2008, k,m=0,1,2,,2008k, m = 0, 1, 2, \ldots, 2008 or 2008200922008 \cdot 2009^{2} numbers,

2) 2k5m2^{k} \cdot 5^{m}, m=2008m = 2008, k=0,1,2,,2008k = 0, 1, 2, \ldots, 2008 or 12009=20091 \cdot 2009 = 2009 numbers.

Finally, there are 200820092+20092008 \cdot 2009^{2} + 2009 numbers divisible by 30200830^{2008} and not divisible by 20200720^{2007}.

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.