Арифметическая прогрессия из взаимно простых

[Xenia1996]

Пусть $n$ - натуральное число и пусть все натуральные числа, меньшие $n$ и взаимно простые с ним, образуют арифметическую прогрессию.
Какое наибольшее количество попарно различных простых делителей может иметь $n$?

[Хорхе]

(Оффтоп)

$2$ ($n=6$ удовлетворяет). Пусть $p_k$ -- $k$-е простое число. Также пусть $p_l$ -- наименьшее простое число, на которое не делится $n$. Нехитрыми рассуждениями получаем, что $n<p_l^2$, откуда $p_1p_2\dots p_{l-1}<p_l^2$. С помощью теоремы Чебышева получаем $p_1\dots p_{l-2} < 8$, откуда $l\le 4$. То есть $n < 49$, значит, остается лишь два варианта для трех или более простых делителей: $30$ и $42$, которые вручную проверяем.

[Xenia1996]

Хорхе в сообщении #431454 писал(а):

(Оффтоп)

$2$ ($n=6$ удовлетворяет). Пусть $p_k$ -- $k$-е простое число. Также пусть $p_l$ -- наименьшее простое число, на которое не делится $n$. Нехитрыми рассуждениями получаем, что $n<p_l^2$, откуда $p_1p_2\dots p_{l-1}<p_l^2$. С помощью теоремы Чебышева получаем $p_1\dots p_{l-2} < 8$, откуда $l\le 4$. То есть $n < 49$, значит, остается лишь два варианта для трех или более простых делителей: $30$ и $42$, которые вручную проверяем.

Я решила, не прибегая к помощи теоремы Чебышева. Предлагаю подумать ещё некоторое время. Потом я напишу решение (решается-то буквально в три строчки, и на школьном уровне! Я бы даже сказала, на уровне младших классов!).

Кстати, что за теорема Чебышева? Я в Сети две нашла, одну из тервера, другую из анализа.

[Хорхе]

Постулат Бертрана иначе называется.

[Xenia1996]

Докажем, что любое натуральное $n>6$, удовлетворяющее условию задачи является либо простым числом, либо степенью двойки с натуральным показателем.

Если $n$ нечётно, то 1 и 2 взаимно просты с $n$, следовательно $n$ - простое.

Если $n$ делится на 4, то $\frac{n}{2}+1$ и $\frac{n}{2}-1$ взаимно просты с $n$, значит, все нечёные, меньшие $n$ взаимно просты с $n$, следовательно $n$ - степень двойки.

Если $n$ делится на 2, но не на 4, то $\frac{n}{2}+2$ и $\frac{n}{2}+4$ взаимно просты с $n$, значит, $n$ - опять степень двойки, однако дано, что $n>6$, следовательно не может делиться на 2 и не делиться на 4.

Если я не ошиблась в решении, оно проще постулата Бертрана.

[TOTAL]

Хорхе в сообщении #431454 писал(а):

Пусть $p_k$ -- $k$-е простое число. Также пусть $p_l$ -- наименьшее простое число, на которое не делится $n$. Нехитрыми рассуждениями получаем, что $n<p_l^2$, откуда $p_1p_2\dots p_{l-1}<p_l^2$.

$n=2 \cdot 3 \cdot 5 \cdot 7 =210$
$p_l=11$
$210>11^2$

Также из $n<p_l^2$ не следует $p_1p_2\dots p_{l-1}<p_l^2$
(ведь возможно $n=p_1^{t_1}p_2^{t_2}\dots p_{l-1}^{t_{l-1}}$)

-- Вт апр 05, 2011 15:25:52 --

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

Если $n$ делится на 4, то $\frac{n}{2}+1$ и $\frac{n}{2}-1$ взаимно просты с $n$, значит, все нечёные, меньшие $n$ взаимно просты с $n$, следовательно $n$ - степень двойки.

$n=24$ делится на $4,$ но нечётное $3$ не взаимно просто с $n$

[Xenia1996]

TOTAL в сообщении #431481 писал(а):

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

Если $n$ делится на 4, то $\frac{n}{2}+1$ и $\frac{n}{2}-1$ взаимно просты с $n$, значит, все нечёные, меньшие $n$ взаимно просты с $n$, следовательно $n$ - степень двойки.

$n=24$ делится на $4,$ но нечётное $3$ не взаимно просто с $n$

В условии задачи написано, что все числа, меньшие $n$ и взаимно простые с ним, образуют арифметическую прогрессию.
Поэтому, если $n$ делится на 4, то $\frac{n}{2}+1$ и $\frac{n}{2}-1$ взаимно просты с $n$, значит, все нечёные, меньшие $n$ взаимно просты с $n$ (потому что все натуральные числа, меньшие $n$ и взаимно простые с ним, образуют арифметическую прогрессию!), следовательно $n$ - степень двойки.

[Sonic86]

Для числа $n$ доля ему взаимно простых равна $\frac{\varphi (n)}{n} = \prod\limits_{j=1}^s \left( 1- \frac{1}{p}\right)$, а плотность арифметической прогрессии $\frac{1}{k}$, откуда $s=1, p_1=2$. Ну то же самое почти, что и у Xenia1996.

[Null]

Sonic86, можете по подробнее, что-то у меня ваш способ вызывает сомнения.

[Sonic86]

Null писал(а):

Sonic86, можете по подробнее, что-то у меня ваш способ вызывает сомнения.

Если Вы сомневаетесь в том, что плотность прогрессии на отрезке $[1;n]$ равна $\frac{1}{k}$ (это лишь ее среднее значение при переменном начальном члене (хотя можно рассмотреть границы сверху и снизу...)), то можно рассмотреть отрезок $[1;kn]$ или даже взять предел при $n \to \infty$. Там плотность прогрессии строго равна $\frac{1}{k}$.
Или не это нужно пояснить?

[Null]

Взаимно простые на отрезке $[1;kn]$ не обязаны образовывать арифметическую прогрессию, например n=6 или n - простое.

[Sonic86]

Null писал(а):

Взаимно простые на отрезке $[1;kn]$ не обязаны образовывать арифметическую прогрессию, например n=6 или n - простое.

Ага, понял. Я неограниченную прогрессию рассматривал Тогда доказательство следует как-то усложнить...

[Хорхе]

TOTAL в сообщении #431481 писал(а):

Хорхе в сообщении #431454 писал(а):

Пусть $p_k$ -- $k$-е простое число. Также пусть $p_l$ -- наименьшее простое число, на которое не делится $n$. Нехитрыми рассуждениями получаем, что $n<p_l^2$, откуда $p_1p_2\dots p_{l-1}<p_l^2$.

$n=2 \cdot 3 \cdot 5 \cdot 7 =210$
$p_l=11$
$210>11^2$

Также из $n<p_l^2$ не следует $p_1p_2\dots p_{l-1}<p_l^2$
(ведь возможно $n=p_1^{t_1}p_2^{t_2}\dots p_{l-1}^{t_{l-1}}$)

Там в первом я использовал, что $1,p_l, 2p_l -1,\dots,p_l^2$ взаимно просты с $n$ (если они меньше $n$). Но какое-то из них должно делиться на делитель $n$ (тут тоже используется постулат Бертрана, вероятно, можно и без него), противоречие.

А второе я вообще не понял. Если $n$ делится на $p_1,\dots,p_{l-1}$, то $n\ge p_1\cdots p_l$, что не так?

[TOTAL]

Хорхе в сообщении #431732 писал(а):

TOTAL в сообщении #431481 писал(а):

Хорхе в сообщении #431454 писал(а):

Пусть $p_k$ -- $k$-е простое число. Также пусть $p_l$ -- наименьшее простое число, на которое не делится $n$. Нехитрыми рассуждениями получаем, что $n<p_l^2$, откуда $p_1p_2\dots p_{l-1}<p_l^2$.

$n=2 \cdot 3 \cdot 5 \cdot 7 =210$
$p_l=11$
$210>11^2$

Также из $n<p_l^2$ не следует $p_1p_2\dots p_{l-1}<p_l^2$
(ведь возможно $n=p_1^{t_1}p_2^{t_2}\dots p_{l-1}^{t_{l-1}}$)

Там в первом я использовал, что $1,p_l, 2p_l -1,\dots,p_l^2$ взаимно просты с $n$ (если они меньше $n$). Но какое-то из них должно делиться на делитель $n$ (тут тоже используется постулат Бертрана, вероятно, можно и без него), противоречие.

А второе я вообще не понял. Если $n$ делится на $p_1,\dots,p_{l-1}$, то $n\ge p_1\cdots p_l$, что не так?

нехитрыми рассуждениями докажите, что $210<11^2$

[Хорхе]

TOTAL, пожалуйста, прочтите внимательно мое предыдущее сообщение. Я там написал, что в своих нехитрых рассуждениях я таки пользовался тем, что взаимно простые с $n$ числа образуют арифметическую прогрессию.