Олимпиада имени Леонарда Эйлера2013-2014 учебный год, I тур регионального этапа

Взяли четыре натуральных числа. Для каждой пары этих чисел выписали их наибольший общий делитель. Получились шесть чисел: $1, 2, 3, 4, 5, N$, где $N > 5$. Какое наименьшее значение может принимать число $N$? ( О. Дмитриев )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. 14.
Решение. Число $N$ может равняться 14, как показывает, например, четвёрка чисел 4, 15, 70, 84. Осталось показать, что $N \geq 14$.
Лемма. Среди попарных НОД четырёх чисел не может быть ровно двух чисел, делящихся на некоторое натуральное $k$.
Доказательство. Если среди исходных четырёх чисел есть не больше двух чисел, делящихся на $k$, то среди попарных НОД на $k$ делится не более одного. Если же три из исходных чисел делятся на $k$, то все три их попарных НОД делятся на $k$. Применяя лемму к $k = 2$, получаем, что число $N$ чётно. Применяя её же к $k = 3$, $k = 4$ и $k = 5$, получаем, что $N$ не делится на 3, 4 и 5. Значит, $N$ не может равняться 6, 8, 10 и 12.