Натуральные числа \(a, b, c\) таковы, что \(1 \leqslant a < b < c \leqslant 3000.\) Найдите наибольшее возможное значение величины

\[\text{НОД}(a,b) + \text{НОД}(b,c) + \text{НОД}(c,a).\]

Решение

Заметим, что НОД\((a, b)\) = НОД\((a, b - a) \leqslant b - a\), так как НОД двух натуральных чисел не превосходит каждое из них. Аналогично получаем, что НОД\((b, c) \leqslant c - b\), а также НОД\((c, a) \leqslant a\).
Складывая эти три неравенства, получаем
\[\text{НОД}(a, b) + \text{НОД}(b, c) + \text{НОД}(c, a) \le (b − a) + (c − b) + a = c \leqslant 3000.\]

В качестве примера на \(3000\) можно предъявить, например, \(a = 1000, b = 2000, c = 3000.\)
В этом случае \(\text{НОД}(a, b) + \text{НОД}(b, c) +\) \(\text{НОД}(c, a) = 1000 + 1000 + 1000 = 3000.\)

Ответ: 3000.