Задача 34920

Темы:    [ НОД и НОК. Взаимная простота ] [ Принцип крайнего (прочее) ] [ Простые числа и их свойства ] [ Доказательство от противного ]

Сложность: 3+ Классы: 7,8,9

Условие

Дано n попарно взаимно простых чисел, больших 1 и меньших  (2n – 1)².  Докажите, что среди них обязательно есть простое число.

Подсказка

Предположите противное и рассмотрите наименьшие простые делители данных чисел.

Решение

Пусть a₁, a₂, ..., a_n – попарно взаимно простые составные числа. Обозначим через p_i наименьший простой делитель числа a_i. Тогда  a_i = p_iq_i,  причём  p_i ≤ q_i.  Поскольку  a_i < (2n – 1)²,  то  p_i < 2n – 1.  Кроме того, числа p₁, p₂, ..., p_n различны, так как числа a₁, a₂, ..., a_n попарно взаимно просты. Однако существует не более  n – 1  простых чисел, больших 1 и меньших  2n – 1:  все такие числа содержатся среди чисел 2, 3, 5, 7, ...,  2n – 3.  Противоречие.

Источники и прецеденты использования

web-сайт

задача