Показать, что число составное.

[bayah]

Проверьте пожалуйста доказательство.

Требуется показать, что $2^k+1$ является составным, если $k$ имеет нечетный делитель.
----------------------------------------------------------------------------------------------------------

Так как, по условию, $k$ имеет нечетный делитель, то запишем в виде $k = (2n+1)p$, где $n, p \in \mathbb{N}$
Докажем требуемое утверждение по индукции.
База индукции: при $n = 1$ получим $2^{(2\cdot 1 + 1)p} + 1 = 2^{3p} + 1$

Индуктивное предположение:
$2^{(2n+1)p} + 1 = lm$, где $l,m \in \mathbb {N}$

Переход:
$2^{(2(n+1)+1)p}+1 = 2^{2np + 3p}+1 = 2^{(2n+1)p}2^{2p} + 1$

Подставим $lm-1$ вместо $2^{(2n+1)p}$, получим:
$(lm-1)2^{2p} +1 = 2^{2p}lm - 2^{2p}+1$

Так как $l,m$ - любые, то это выражение будет составным, если есть общие множители у $2^{3p} + 1$ и $2^{2p}-1$
$2^{2p}-1 = (2^p+1)(2^p-1)$

Разделим $2^{3p} + 1$ на $(2^p+1)$ и получим:
$\dfrac{2^{3p} + 1}{(2^p+1)} = 2^{2p} - 2^p +1$

Значит и $2^{2p}lm - 2^{2p}+1$ делится на $2^p+1$, то есть является составным, что и требовалось доказать.

[VAL]

Индукция тут не нужна. (Поэтому в Ваше доказательство я не вникал.)
Можно напрямую воспользоваться известной (и очевидной) формулой разложения $a^n+b^n$ для нечетных $n$.

[victor.l]

Если k=1 то не составное.

[bayah]

victor.l в сообщении #1170623 писал(а):

Если k=1 то не составное.

Ну да, но это типа не в счет. Поэтому я записал $k = (2n+1)p$.

VAL в сообщении #1170370 писал(а):

Индукция тут не нужна. (Поэтому в Ваше доказательство я не вникал.)
Можно напрямую воспользоваться известной (и очевидной) формулой разложения $(a+b)^n$ для нечетных $n$.

Таак... А как эта формула помогает, что-то я не пойму?


А по-поводу своего решения, что-то я уже сам не пойму, что оно доказывает, но похоже не то что нужно). Я почему, то считал, что $l, m$ могут быть любыми, но это ведь не так. Так что $2^{2p}lm$ может не иметь общего делителя с $2^{2p}-1$. Поэтому вопрос открытый, как вообще правильно показать верность вышеуказанного утверждения.

[VAL]

bayah в сообщении #1170635 писал(а):

VAL в сообщении #1170370 писал(а):

Можно напрямую воспользоваться известной (и очевидной) формулой разложения $a^n+b^n$ для нечетных $n$.

Таак... А как эта формула помогает, что-то я не пойму?

Напрямую помогает.
Например, что $2^{76}+1$ - составное сразу следует из этой формулы. Достаточно лишь правильно выбрать $a, n$ и $b$.

[victor.l]

Формул ускоренного умножения в курсе.

[bayah]

VAL в сообщении #1170637 писал(а):

Напрямую помогает.
Например, что $2^{76}+1$ - составное сразу следует из этой формулы. Достаточно лишь правильно выбрать $a, n$ и $b$.

А почему такие числа всегда можно найти? Это очевидно?

[VAL]

bayah в сообщении #1170649 писал(а):

VAL в сообщении #1170637 писал(а):

Напрямую помогает.
Например, что $2^{76}+1$ - составное сразу следует из этой формулы. Достаточно лишь правильно выбрать $a, n$ и $b$.

А почему такие числа всегда можно найти? Это очевидно?

Вы для приведенного примера укажите, что взять за $a$, что за $b$, а что за $n$. А там, глядишь, и с общим случаем разберемся.

[sa233091]

Кажется, достаточно разложить сумму нечетных степеней в произведение, что является тривиальной задачей. Хотя, возможно, я чего-либо недопонимаю.

[VAL]

У меня позавчера-вчера случился (в принципе, вполне объяснимый и, надеюсь, временный) приступ повышенной рассеянности
И формулу я имел в виду одну, но набрал, оказывается, другую. Сейчас поправил.

[bayah]

VAL в сообщении #1170684 писал(а):

У меня позавчера-вчера случился (в принципе, вполне объяснимый и, надеюсь, временный) приступ повышенной рассеянности
И формулу я имел в виду одну, но набрал, оказывается, другую. Сейчас поправил.

Аа... ну тогда $k$ всегда можно представить в виде $k=(2n+1)p$, и дальше просто из формулы следует требуемое.
То есть если $k$ нечетное, то сразу формула применима, если четное - то делим на $2$ пока не получится нечетный множитель. А $b = 1$.
Спасибо)
А откуда выводится эта формула разложения $a^n + b^n$ ?

[gris]

Попробуйте формулу суммы геометрической прогрессии для выражения $a^{n-1}-a^{n-2}b+...\pm b^{n-1}$

[bayah]

gris в сообщении #1170753 писал(а):

Попробуйте формулу суммы геометрической прогрессии для выражения $a^{n-1}-a^{n-2}b+...\pm b^{n-1}$

Точно, спасибо)

А все таки, можно как-то по индукции провести такое доказательство?

[Shadow]

bayah в сообщении #1170757 писал(а):

А все таки, можно как-то по индукции провести такое доказательство?

Конечно, докажите, что если $a^n+1$ делится на $a+1$, то и $a^{n+2}+1$ тоже делится на $a+1$
Или в общем случае - $a^n+b^n$

[bayah]

Shadow в сообщении #1170773 писал(а):

Конечно, докажите, что если $a^n+1$ делится на $a+1$, то и $a^{n+2}+1$ тоже делится на $a+1$
Или в общем случае - $a^n+b^n$

Если мы предполагаем, что $a^n+1$ делится на $a+1$, то да, а как мы угадаем знаем, на что следует делить, наугад? Можно как-то из общих соображений, просто из предположения, что $a^n+1$ делится на что-то нацело?