Любое ли число можно получить?

[Pythagoras]

Доброго времени суток! Задача такая.
------------------
Есть число 1. К имеющемуся числу можно применять следующие операции:
А) Умножить на любое натуральное число от 2 до 100 (включительно) и прибавить к произведению 1.
Б) Разделить число на его наименьший отличный от 1 делитель.

Любое ли натуральное число можно получить такими операциями?
------------------

Я пытался доказать, что $100! + 2$ нельзя получить. Это число нельзя получить операцией А, но можно получить операцией Б. Поэтому ничего не понятно.

Потом пытался доказать, что любое можно. Можно получить любое число вида $2^n - 1$. Любое нечётное число делит какое-то число такого вида. Но тут тоже не ясно.

Буду признателен за помощь!

[Ende]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы)

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Ende]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: темы, в которых нужно что-то объяснить или подсказать в пределах учебных курсов, создаются в этом разделе.

[Rak so dna]

Pythagoras в сообщении #1614968 писал(а):

Есть число 1. К имеющемуся числу можно применять следующие операции:
А) Умножить на любое натуральное число от 2 до 100 (включительно) и прибавить к произведению 1.
Б) Разделить число на его наименьший отличный от 1 делитель.

Любое ли натуральное число можно получить такими операциями?

Не заметил сразу, что задачу переместили в другой раздел...
Рассмотрите какое-нибудь число, делящееся на все числа от $1$ до $100$.

[Pythagoras]

Rak so dna в сообщении #1614984 писал(а):

Рассмотрите какое-нибудь число, делящееся на все числа от $1$ до $100$.

Спасибо, понятно! Всё было так легко

[Dendr]

Интересно, какое наименьшее нельзя получить? Верхняя граница, как уже ясно из вышесказанного, это произведение всех простых, меньших $100$, то есть $c=2\cdot3\cdot...\cdot97\approx3,2\cdot10^{211}$. А есть ли меньше?

Обозначим наименьшее число $a\le c$. Наименьший простой делитель $p$ числа $a-1$ должен быть больше ста: $p>100$, в противном случае $a$ получается из $\frac{a-1}{p}<a$, а по гипотезе такое число может быть получено. Собственно, для $c$ это выполняется. Но тогда $a-1$ - нечетно, то есть $a$ - четно.

Это число не может быть получено операцией Б, то есть из числа $qa$, где $q$ - наименьший делитель числа $qa$. Но в силу четности, это двойка. Значит, мы не сможем получить число $2a$, и вообще $2^na$ для любого $n$. В противном случае мы бы получили и $a$.
Рассмотрим число $2a-1$. Мы знаем, что $a-1$ не делится на $3$.

Пусть оно равно $3k+1$, тогда $a=3k+2, 2a-1=6k+3$, то есть $2a$ получается из $2k+1<3k+2=a$ операцией А. Однако число $2k+1$ мы можем получить по нашей гипотезе ($a$ - наименьшее невозможное).
Если же оно равно $3k-1$, тогда $a=3k$, $2a-1=6k-1$, и противоречий нет. Уже получаем, что $a$ кратно $6$.

$a-1$ не делится на 5, то есть имеет место одно из значений: $a=5k, 5k+2, 5k+3, 5k+4$. Но лучше использовать делимость на 6 и записать $30k, 30k+12, 30k+18, 30k+24$
$2a-1, 4a-1$ не могут делиться на 5, так что исключим третий и четвертый случаи и сосредоточимся на втором. $8a=240k+96$, и это число может быть получено из $48k+19$, а оно, в свою очередь, из $16k+6<a$, которое точно может быть получено в силу нашей гипотезы. Таким образом, $a$ должно делиться на $30$.

Кажется, что так мы может дойти и до $c$, как минимального. Но с семеркой эти рассуждения уже не работают, соответственно, обобщать не так-то просто, как кажется.