Доказать делимость и неделимость числа

@NEvOl · Регистрация: 13.08.2012

Author24 — интернет-сервис помощи студентам

Задачка:
доказать что число $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^n}-1$ делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n+2}$ и не делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n+3}$ .

Доказываю делимость:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?P(n)$ - число $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^n}-1$ делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n+2}$
при $https://www.cyberforum.ru/cgi-bin/latex.cgi?n=1$ имеем $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^n}-1=8$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n+2}=8$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(1)$ -истинно.
предположим что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\forall k \leq n$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(k)$ -истинно, докажем истинность для $https://www.cyberforum.ru/cgi-bin/latex.cgi?n=k+1$ :
$https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^{k+1}}-1=3^{2^{k}2}-1=(3^{2^k}-1)(3^{2^k}+1)$ число $https://www.cyberforum.ru/cgi-bin/latex.cgi?(3^{2^k}-1)$ делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{k+2}$ по предположению индукции. $https://www.cyberforum.ru/cgi-bin/latex.cgi?(3^{2^k}+1)$ делится на 2 т.к. нечетное число в любой степени будет нечетным и нечетное число + 1 дает четное, а четное число делится на 2, в итоге $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^{k+1}}-1$ делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{(k+1)+2}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(n)$ истинно для любого натурального аргумента.

Доказываю неделимость:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?P(n)$ - число $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^n}-1$ не делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n+3}$
при $https://www.cyberforum.ru/cgi-bin/latex.cgi?n=1$ имеем $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^n}-1=8$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n+3}=16$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(1)$ -истинно.
предположим что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\forall k \leq n$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(k)$ -истинно, докажем истинность для $https://www.cyberforum.ru/cgi-bin/latex.cgi?n=k+1$ :
$https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^{k+1}}-1=3^{2^{k}2}-1=(3^{2^k}-1)(3^{2^k}+1)$ число $https://www.cyberforum.ru/cgi-bin/latex.cgi?(3^{2^k}-1)$ делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{k+2}$ и не делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{k+3}$ , значит при делении числа $https://www.cyberforum.ru/cgi-bin/latex.cgi?(3^{2^k}-1)$ на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{k+3}$ будет остаток 1. $https://www.cyberforum.ru/cgi-bin/latex.cgi?(3^{2^k}+1)=(3^{2^k}-1)+2$ , при делении числа 2 на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{k+3}$ остаток будет 2 тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi?(3^{2^k}+1)=i(2^{k+3})+1+j(2^{k+3})+2=(2^{k+3})(i+j)+3$ и значит $https://www.cyberforum.ru/cgi-bin/latex.cgi?(3^{2^k}+1)$ не делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{k+3}$ , тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^{k+1}}-1$ не делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{(k+1)+3}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(n)$ истинно для любого натурального аргумента.

Проверьте пожалуйста, верно ли я решаю, может как-то проще можно решить ?

@kabenyuk · 27.02.2017, 18:08

Сообщение от NEvOl

будет остаток 1.

Первая часть очень похожа на правду. Вторая - абсолютно не верно. У вас и делитель, и делимое - оба четны. Как может быть в остатке 1? Вообще индукция второй части не может быть проведена в таком виде. Вы сначала докажите, что 3^х+1=2 (mod4) при любом четном х, затем используйте это, последовательно разлагая многоэтажную степень тройки на несколько множителей.

@NEvOl 20 / 19 / 1 Регистрация: 13.08.2012 Сообщений: 779
		1
	Доказать делимость и неделимость числа 26.02.2017, 20:41. Показов 1095. Ответов 1 Метки нет (Все метки) Задачка: доказать что число $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^n}-1$ делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n+2}$ и не делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n+3}$ . Доказываю делимость: $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(n)$ - число $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^n}-1$ делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n+2}$ при $https://www.cyberforum.ru/cgi-bin/latex.cgi?n=1$ имеем $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^n}-1=8$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n+2}=8$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(1)$ -истинно. предположим что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\forall k \leq n$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(k)$ -истинно, докажем истинность для $https://www.cyberforum.ru/cgi-bin/latex.cgi?n=k+1$ : $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^{k+1}}-1=3^{2^{k}2}-1=(3^{2^k}-1)(3^{2^k}+1)$ число $https://www.cyberforum.ru/cgi-bin/latex.cgi?(3^{2^k}-1)$ делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{k+2}$ по предположению индукции. $https://www.cyberforum.ru/cgi-bin/latex.cgi?(3^{2^k}+1)$ делится на 2 т.к. нечетное число в любой степени будет нечетным и нечетное число + 1 дает четное, а четное число делится на 2, в итоге $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^{k+1}}-1$ делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{(k+1)+2}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(n)$ истинно для любого натурального аргумента. Доказываю неделимость: $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(n)$ - число $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^n}-1$ не делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n+3}$ при $https://www.cyberforum.ru/cgi-bin/latex.cgi?n=1$ имеем $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^n}-1=8$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n+3}=16$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(1)$ -истинно. предположим что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\forall k \leq n$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(k)$ -истинно, докажем истинность для $https://www.cyberforum.ru/cgi-bin/latex.cgi?n=k+1$ : $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^{k+1}}-1=3^{2^{k}2}-1=(3^{2^k}-1)(3^{2^k}+1)$ число $https://www.cyberforum.ru/cgi-bin/latex.cgi?(3^{2^k}-1)$ делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{k+2}$ и не делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{k+3}$ , значит при делении числа $https://www.cyberforum.ru/cgi-bin/latex.cgi?(3^{2^k}-1)$ на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{k+3}$ будет остаток 1. $https://www.cyberforum.ru/cgi-bin/latex.cgi?(3^{2^k}+1)=(3^{2^k}-1)+2$ , при делении числа 2 на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{k+3}$ остаток будет 2 тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi?(3^{2^k}+1)=i(2^{k+3})+1+j(2^{k+3})+2=(2^{k+3})(i+j)+3$ и значит $https://www.cyberforum.ru/cgi-bin/latex.cgi?(3^{2^k}+1)$ не делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{k+3}$ , тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^{2^{k+1}}-1$ не делится на $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{(k+1)+3}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(n)$ истинно для любого натурального аргумента. Проверьте пожалуйста, верно ли я решаю, может как-то проще можно решить ? 0

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	27.02.2017, 18:08	2
	Сообщение от NEvOl будет остаток 1. Первая часть очень похожа на правду. Вторая - абсолютно не верно. У вас и делитель, и делимое - оба четны. Как может быть в остатке 1? Вообще индукция второй части не может быть проведена в таком виде. Вы сначала докажите, что 3^х+1=2 (mod4) при любом четном х, затем используйте это, последовательно разлагая многоэтажную степень тройки на несколько множителей. 1