Задача
Учитель записал Пете в тетрадь четыре различных натуральных числа. Для каждой пары этих чисел Петя нашёл их наибольший общий делитель. У него получились шесть чисел: 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.
Ответ
Чтобы оставлять комментарии, войдите или зарегистрируйтесь