Приписывание по единице слева и справа

[Ktina]

Берём натуральное число (в десятичной записи) и приписываем к нему слева и справа по единице. Например, 2016 -> 120161.
С полученным числом проделываем то же самое, и так далее.
Доказать, что рано или поздно получится составное число, не кратное трём.

[DeBill]

Отнимем от Вашего числа число из одних единичек: $2016 - 1111 = 0905$, и возьмем его простой делитель $p$ (не 5 и не 2).
Хорошо известно, что есть числа из единичек, кратные $p$ (ибо чисел таких - много, а остатков от деления - мало). Можно считать, что единичек очень много, и - четное кол-во (т.к., их моно размножать...). Вот и получилось число непростое (например, $905=181\cdot 5$, а $10^{180} - 1$ делится на 181, так что на девяностом шаге будет число, кратное 181).
Но что делать, если все делители - двойки и пятерки?

-- 18.04.2016, 01:04 --

Ой, оно кратно 3....
arseniiv
Ай, какой я неаккуратный: да, не кратно оно 3, ибо делимость на 181 получится не на 90-м шаге, а на 88-м: ведь уже в начале есть 4 единички.
А признаки: на 11, 7 и 13 ниче не дает, а все прочее - лучше уж сразу ферма (или Эйлера) применять...

[arseniiv]

То, что получится не кратное трём, можно видеть из признака делимости на три, который на самом деле способ вычисления остатка от деления на три. Осталось показать, что это может совпасть с составностью. А точно никакие другие распространённые признаки делимости (я их не помню ) не помогут?

[Ktina]

arseniiv в сообщении #1116186 писал(а):

А точно никакие другие распространённые признаки делимости (я их не помню ) не помогут?

Точно

[Shadow]

Для строгости: Припишем к нашему числу слева и справо нужное число единичек, чтобы получить число $n$ - взаимнопростое с 10 и $n\equiv 2 \pmod 3$
Из второго условия следучет, что $n$ имеет хотя бы один простой делитель $p \equiv 2 \pmod 3$
Припишем к числу $n$ слева и справо по $p-1$ единичек - получим число, сравнимо с 1 по модулю 3 и делящееся на $p$

[Ktina]

Shadow
Спасибо!

[Shadow]

Не за что, Ktina - я перемудрил
Достаточно получить число, неделящееся на 3. Которое либо составное и задача решена, либо простое...

[Ktina]

Shadow
А если простое?

-- 19.04.2016, 14:47 --

То как дальше?

[Shadow]

Ktina в сообщении #1116610 писал(а):

А если простое?

А если получилось простое $p$ - отличное от $2,3,5$ - приписываем слева и справa $p-1$ единиц. Полученное число будет делится на $p$
И по модулю 3 будет $(p-1)+p+(p-1)=3p-2 \equiv 1 \pmod 3$

[Ktina]

Shadow
Спасибо!