Maths Olympiad Prep

Library / /5 of 15

Number theory Difficulty 4.6 AIME Find the answer Philippines

Problem:
Let NN be the smallest positive integer divisible by 2020, 1818, and 20182018. How many positive integers are both less than and relatively prime to NN?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
First, find N=lcm(20,18,2018)N = \operatorname{lcm}(20, 18, 2018).

Prime factorizations:
20=22×520 = 2^2 \times 5
18=2×3218 = 2 \times 3^2
2018=2×10092018 = 2 \times 1009

So,
N=lcm(22×5,2×32,2×1009)N = \operatorname{lcm}(2^2 \times 5, 2 \times 3^2, 2 \times 1009)

Take the highest power of each prime:
- 222^2 (from 2020)
- 323^2 (from 1818)
- 55 (from 2020)
- 10091009 (from 20182018)

Thus,
N=22×32×5×1009N = 2^2 \times 3^2 \times 5 \times 1009

Now, the number of positive integers less than NN and relatively prime to NN is φ(N)\varphi(N), where φ\varphi is Euler's totient function.

N=22×32×5×1009N = 2^2 \times 3^2 \times 5 \times 1009

So,
φ(N)=N(112)(113)(115)(111009)\varphi(N) = N \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) \left(1 - \frac{1}{5}\right) \left(1 - \frac{1}{1009}\right)

Calculate step by step:

N=4×9×5×1009=36×5×1009=180×1009=181620N = 4 \times 9 \times 5 \times 1009 = 36 \times 5 \times 1009 = 180 \times 1009 = 181620

Now,
φ(N)=181620×12×23×45×10081009\varphi(N) = 181620 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5} \times \frac{1008}{1009}

Calculate each step:

181620×12=90810181620 \times \frac{1}{2} = 90810
90810×23=6054090810 \times \frac{2}{3} = 60540
60540×45=4843260540 \times \frac{4}{5} = 48432
48432×1008100948432 \times \frac{1008}{1009}

Now, 48432×1008=4883105648432 \times 1008 = 48831056

Divide by 10091009:
488310561009=48408\frac{48831056}{1009} = 48408

So, the answer is 4840848408.

Final Answer:

48408\boxed{48408}

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.