Задача 79506
|
|
 |
Условие
Доказать, что из любых 27 различных натуральных чисел, меньших 100, можно выбрать два числа, не являющихся взаимно простыми.
Решение
Рассмотрим произвольный набор из 27 различных натуральных чисел, меньших 100. Для каждого числа из набора отметим либо один из его простых делителей (если это число не равно единице), либо единицу (если это число равно единице). Так как простых чисел, меньших ста, всего 25, то какое-то число мы отметили дважды. Этим числом не могла быть единица, поскольку единицу мы отмечали только для единицы. Следовательно, в наборе есть два числа с общим простым делителем, то есть два числа, не являющихся взаимно простыми.
