Consider $2$ positive integers $a,b$ such that $a+2b=2020$. (a) Determine the largest possible value of the greatest common divisor of $a$ and $b$. (b) Determine the smallest possible value of the least common multiple of $a$ and $b$.
Problem
Source: The South African Mathematical Olympiad Third Round 2023 P3
Tags: number theory, greatest common divisor, least common multiple
lpieleanu
30.07.2023 10:15
Let $$d=\gcd(a,b), a=dk, b=dh.$$
Substituting yields $$dk+2dh = 2020 \rightarrow k+2h = \frac{2020}{d}.$$Also, note that $$k,h\geq1 \rightarrow d \leq \frac{2020}{3}.$$Since $k,h \in \mathbb{Z},$ $d$ must be a factor of $2020,$ so the largest possible $d$ is $$\frac{2020}{4} = \boxed{505}.$$This is achieved by $a=1010,b=505.$ $\square$
Elliot_7002
31.07.2023 15:50
Soln for part b) clearly a must divide b or b must divide a case 1: a | b a + 2ka = 2020 a(2k+1) = 2020 a = 2020/2k+1 101 and 5 and 505 are the odd divisors of 2020 2k+1 = 5 gives k = 2 and a = 404 a = 404 2k a = 1616 and this is lowest value attained in this case case 2: b | a kb +2b = 2020 b = 2020/k+2 b = 101 k = 18 which gives kb = 1818 which is the lowest in this case which gives total minimum of 1616```
Nicio9
24.07.2024 23:11
Elliot_7002 wrote: case 1: a | b a + 2ka = 2020 a(2k+1) = 2020 a = 2020/2k+1 101 and 5 and 505 are the odd divisors of 2020 2k+1 = 5 gives k = 2 and a = 404 a = 404 2k a = 1616 and this is lowest value attained in this case You made a mistake at the end of case 1. if $k=2$ and $a=404$, then: $b=ak=404 \cdot 2 = 808$ $lcm(a,b)=lcm(404,808) = 808$ Thus, the answer is actually 808.