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