Доказать, что число 1986^n-1 не делится на 1000^n-1

[grizzly]

nnosipov

(Оффтоп)

Насчёт "наполовину" -- это шутка, конечно. Про то, что для каждого второго $n$ неделимость $3^n-1$ на $2^n-1$ по-детски очевидна.
Но нужно было в оффтоп, сорри.

[nnosipov]

grizzly

(Оффтоп)

А, вот про какую половину идёт речь. Дело в том, что эта задача (про делимость $3^n-1$ на $2^n-1$), вся целиком, формально детская, ибо предлагалась детям на каком-то московском отборочном мероприятии где-то в середине 2000-х годов. Но до меня далеко не сразу дошло, в чём там фокус, когда я попытался эту детскую задачу решить.

[timber]

ИСН в сообщении #952121 писал(а):

ИСН в сообщении #951791 писал(а):

начинать следует, как всегда в таких случаях, с рассмотрения по малым модулям.

-- менее минуты назад --

Туманно как-то вышло; вон с двойкой попробовали и всё ОК. Ну ладно, а Вы всё же попробуйте ещё с каким-нибудь малым...

Ну, допустим, видно, что число $1000^n-1$ делится на 3 и 9. Наверное, надо показать, что число $1986^n-1$ не будет кратно этим числам?

[ИСН]

Ваш вопрос подобен вопросу о направлении от человека, который уже занёс одну ногу для шага и находится в неустойчивом равновесии. Странный момент для вопроса, ну да ему виднее. Можно ответить, а можно подождать, пока он потеряет равновесие и опустит ногу, таким образом сделав шаг, и обнаружив (может быть) на этом месте что-то, что сделает сам вопрос излишним.

[grizzly]

timber в сообщении #952505 писал(а):

Наверное, надо показать, что число $1986^n-1$ не будет кратно этим числам?

Неужели у Вас такая скорость набора, что задать этот вопрос для Вас быстрее, чем его решить? Рискну предположить, что задать Вы хотя бы попробовали, а решить -- нет. Но вот Вам мой совет: старайтесь всегда действовать в обратном порядке.

[timber]

Я к тому, что если идти этим путем и доказывать, что степень какого-то числа за вычетом единицы не кратна 3 или 9, то полная запись такого доказательства будет не лучше, чем приведенное выше мной. Но, заявляется, что есть гораздо более простой способ.

[ИСН]

Вы предъявите её наконец, эту полную запись, а тогда и сравним, что короче.

[timber]

Так как $1000^n-1=99...9$ кратно 3, то в случае, если $(1986^n-1)\vdots(1000^n-1)$, число $1986^n-1$ должно быть также кратно 3. Покажем, что это не так для всех $n$.
1) Проверим это при $n=1$. 1985 не кратно 3.
2) Пусть $ 1986^k-1$ не кратно 3 для $k=n$. Докажем справедливость этого утверждения для $n=k+1$. ... В итоге, получаем $1986(1986^k-1)+1985$, которое не кратно 3.

[nnosipov]

Верно :) Но Вы действительно не ищите лёгких путей. $1986^n-1$ не кратно $3$, так как $1986^n$ делится на $3$. Разве не очевидно?

[timber]

nnosipov в сообщении #952594 писал(а):

Верно :) Но Вы действительно не ищите лёгких путей. $1986^n-1$ не кратно $3$, так как $1986^n$ делится на $3$. Разве не очевидно?

Иди знай. Очевидно то, что очевидно доказывается.

[ИСН]

Ну так а это разве не очевидно доказывается? 1986 делится на 3, значит, любая его степень - тоже, значит, на единицу меньшее число - уж точно нет.

[nnosipov]

ИСН в сообщении #952617 писал(а):

1986 делится на 3

Здесь можно сослаться на признак делимости на $3$, который знают очень многие школьники, и этим признаком можно пользоваться не доказывая его (как теоремой Пифагора).