Помогите с доказательством (является ли составным число)

[SteelRend]

Нужно доказать, что $4^n - 1$ при $n > 1$ является составным числом. Вот как это сделал я.
Число $4^n$ может оканчиваться либо на $4$, либо на $6$.
Если оно оканчивается на $6$, то $4^n - 1$ оканчивается на $5$, значит $4^n - 1$ делится на 5, значит оно является составным.
Если оно оканчивается на $4$, то $4^n - 1$ оканчивается на $3$, а это значит, что...????
Метод математической индукции. $4^n - 1$ при $n = 2$ это $4^2 - 1 = 15 = 3 \cdot 5$ - составное. База индукции выполняется.
Предполагаем, что $4^i - 1$ при $2 \leq i \leq n$ составное.
$4^{n+1} - 1 = 4 \cdot 4^n - 1 = 4 \cdot (4^n - 1 + 1) - 1 = 4 \cdot (4^n - 1) + 4 - 1 = 4 \cdot (4^n - 1)+3$
Поскольку $4^n$ оканчивается на $4$, то $4^n - 1$ оканчивается на $3$. Значит $4 \cdot (4^n - 1)$ оканчивается на $2$. Значит $4 \cdot (4^n - 1)+3$ оканчивается на $5$. Значит $4 \cdot (4^n - 1)+3$ делится на $5$. Значит $4 \cdot (4^n - 1)+3 = 4^{n+1} - 1$ является составным.

Проблема в том (при условии что я нигде не ошибся), что применение мат. индукции здесь кажется излишним, ведь я в действительности никак (по крайней мере, явно) не использовал предположение шага индукции, т.е. что $4^i - 1$ при $2 \leq i \leq n$ составное.

[Otta]

А каковы ограничения на используемые средства? Известное разложение для $a^n-b^n$ запрещалось использовать?

[SteelRend]

Otta
Эту задачу я взял из "Простые и составные числа" А. Шеня, про ограничения там ничего сказано не было. За подсказку спасибо, оказывается всё намного проще.

[grizzly]

SteelRend в сообщении #1322240 писал(а):

Предполагаем, что $4^i - 1$ при $2 \leq i \leq n$ составное.
$4^{n+1} - 1 = 4 \cdot 4^n - 1 = 4 \cdot (4^n - 1 + 1) - 1 = 4 \cdot (4^n - 1) + 4 - 1 = 4 \cdot (4^n - 1)+3$

Так вот здесь уже проведено почти всё доказательство по индукции. Достаточно было только сделать верное предположение индукции: делимость на 3.

[Booker48]

Если "известное разложение" использовать всё же запрещено, то можно заметить, что $4^n-1$ в двоичной записи состоит ровно из $2n$ единиц.
Но $\underbrace{1...1}_{2n}=\underbrace{1...1}_{n}\cdot 1\underbrace{0...0}_{n-1}1$.

[SteelRend]

grizzly
Вы правы, и в то, что $4^n-1$ должно делиться на $3$, мне тоже хотелось поверить, поскольку тогда на $3$ будет делиться $4 \cdot (4^n - 1)+3$ и утверждение будет доказано. Но я как-то не додумался это в индукции предположить. Любопытный приём, когда ты интуитивно понимаешь, что некоторое утверждение справедливо, и для того чтобы это строго доказать, нужно сделать удобное предположение, которое согласуется с твоей догадкой.

[Otta]

grizzly в сообщении #1322246 писал(а):

Достаточно было только сделать верное предположение индукции: делимость на 3.

Да, а вместо этого фигурировало

SteelRend в сообщении #1322240 писал(а):

Поскольку $4^n$ оканчивается на $4$

- что странно, поскольку выше было замечено, что это верно не для всех $n$.

[SteelRend]

Otta
Блин Этого я не заметил А нельзя ли это исправить, сказав, что там не все $n$, а только те, при которых, $4^n$ оканчивается на $4$ (тогда я показываю что при этом допущении $4^{n+1} - 1$ составное, а те $4^{n+1} - 1$, где $4^n$ не оканчивается на $4$ мы не рассматриваем?)? Или тогда воспользоваться мат. индукцией уже не выйдет?

[Otta]

SteelRend в сообщении #1322254 писал(а):

сказав, что там не все $n$, а только те, при которых, $4^n$ оканчивается на $4$

Ну то есть через одно. То есть $n$ у Вас нечетное, а смотрите Вы, что произойдет при четном $n+1$. Но это Вы в самом начале написали - при четном показателе все число заканчивается на 5. И для этого индукция ни к чему, и вот таким образом устроенное рассуждение, конечно, ею не является.

Хотите смотреть только нечетные (где и проблема) - устраивайте индукцию по нечетным. Однако, что Вы будете доказывать? Делимость на 3? Так это лучше сделать в общем случае, правильно построив рассуждение. И не понадобится смотреть отдельно числа разной четности.