Число, взаимно простое с остальными

[Xenia1996]

Среди любых $n\in\mathbb N$ последовательных натуральных чисел найдётся хотя бы одно число $m$, взаимно простое с остальными $n-1$ числами.

При каких $n>1$ это верно, а при каких - нет?

[Sonic86]

Будем рассматривать числа $1,...,n$ - $n$ последовательных чисел. Для $n \geq n_0$ в силу постулата Бертрана среди $\frac{n}{2}$ и $n$ найдется хотя бы одно простое $p$. Очевидно, что оно взаимно просто с прочими числами $1,...,n$. $n_0$ вроде бы равно 6. Остальные $n<n_0$ можно перебором перебрать, вроде бы там для $n$ всех это верно.

[Xenia1996]

Sonic86 в сообщении #448097 писал(а):

Будем рассматривать числа $1,...,n$ - $n$ последовательных чисел. Для $n \geq n_0$ в силу постулата Бертрана среди $\frac{n}{2}$ и $n$ найдется хотя бы одно простое $p$. Очевидно, что оно взаимно просто с прочими числами $1,...,n$. $n_0$ вроде бы равно 6. Остальные $n<n_0$ можно перебором перебрать, вроде бы там для $n$ всех это верно.

В молоко дротик.
Эта задача враз не решается, нужно с ней долго работать по-норвежски.

[maxal]

Xenia1996 в сообщении #448090 писал(а):

Среди любых $n\in\mathbb N$ последовательных натуральных чисел найдётся хотя бы одно число $m$, взаимно простое с остальными $n-1$ числами.

При каких $n>1$ это верно, а при каких - нет?

Верно лишь при $n<17$ - см. post27408.html#p27408

[Sonic86]

Видимо неправильно понял формулировку: по последовательностям последовательных натуральных чисел стоит квантор всеобщности, а не существования...

[vorvalm]

Если принять $n=p$ , то $\phi(p)=p-1$
Среди вычетов ПСВ всегда есть простые числа.