2014-06-07
Найти все натуральные числа $n >2$ не превосходящие числа 10000000 и обладающие следующим свойством: любое число $m$, взаимно простое с $n$ и удовлетворяющее неравенствам $1 < m < n$, является простым.
Решение:
Пусть число $n$ обладает требуемым в задаче свойством. Если оно не делится на 2, то $n \leq 2^{2}$ (иначе число $m=4$, взаимно простое с $n$ и меньшее его, было бы простым). Поэтому $n = 3$. Если $n$ делится на два, но не делится на 3, то по аналогичным соображениям $n \leq 3^{2}$, т. е. $n \in {4; 8}$. Если $n$ делится на 2 и 3, но не делится на 5, то $n \leq 5^{2}$ и $n \vdots 6$, т. е.
$n \in {6; 12; 18; 24}$.
Если же $n$ делится на 2, 3 и 5, но не делится на 7, то $n \leq 7^{2}$ и $n \vdots 30$, т. е. $n = 30$. Пусть для некоторого значения $k \geq 4$ число $n$ делится на каждое из чисел $p_{1},p_{2}, \cdots p_{k}$, но не делится на $p_{k+1}$, где $2=p_{1} < p_{2} < \cdots < p_{k} < p_{k+1}$ - последовательные простые числа. Тогда
$n \leq p^{2}_{k+1}$ и $n \vdots p_{1}p_{2} \cdots p_{k}$
Из оценки
$ p_{1}p_{2} \cdots p_{k} \leq n \leq 10 000 000$,
получаем, что $k \leq 8$. Наконец, замечаем, что при каждом значении $k=4, 5, 6, 7, 8$ справедливо неравенство
$ p_{1}p_{2} \cdots p_{k} > p^{2}_{k+1}$,
которое противоречит необходимому условию
$ p_{1}p_{2} \cdots p_{k} \leq n \leq p^{2}_{k+1}$.
Полученное противоречие показывает, что рассматриваемый случай невозможен. Таким образом, доказано, что все возможные значения $n$ принадлежат множеству
${3; 4; 6; 8; 12; 18; 24; 30}$.
Проверка показывает, что каждое число из этого множества обладает свойством, указанным в условии задачи.