Задача 35122

Темы:    [ Простые числа и их свойства ] [ Доказательство от противного ]

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

Условие

Докажите, что простых чисел, дающих остаток 2 при делении на 3, бесконечно много.

Подсказка

Если имеются простые числа p₁, p₂, ..., p_n, то все простые делители чисел  p₁p₂...p_n + 1  и  p₁p₂...p_n – 1  отличны от чисел p₁, p₂, ..., p_n.

Решение

Предположим, что напротив, найдётся лишь конечное число таких простых чисел, обозначим эти числа p₁, p₂, ... , p_n. Число  A = 3p₁p₂...p_n – 1  не делится на простые числа p₁, p₂, ..., p_n и даёт остаток 2 при делении на 3. Значит, среди его простых делителей должно быть число вида  3k + 2.  Противоречие.

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

web-сайт

задача