Question

Докажите, что $3^{2 {n} } -1$
a) Делится на $2^{n+2}$
b) не делится на $2^{n+3}$

Answer 1

Докажем утверждение по индукции. База индукции — при $k=1$ число $3^2-1=8$ делится на $2^{1+2}=8$, но не делится на $2^{1+3}=16$.

Теперь, зная, что при $k=n$ утверждение верно, покажем, что при $k=n+1$ оно также верно. Мы знаем, что число $3^{2^n}-1$ делится на $2^{n+2}$ и не делится на $2^{n+3}$. 

Рассмотрим число $(3^{2^n}-1)^2=3^{2^{n+1}}-2*3^{2^n}+1$. Ясно, что оно делится на $2^{2n+4}$. Прибавим к нему выражение $2*(3^{2^n}-1)$: $(3^{2^{n+1}}-2*3^{2^n}+1)+2*(3^{2^n}-1)=3^{2^{n+1}}-1$.

Нетрудно видеть, что полученное число делится на $2^{n+3}$, но не делится на $2^{n+4}$. Первое слагаемое делится на $2^{2n+6}$, а потому и на $2^{n+4}$, а второе делится на $2*2^{n+2}=2^{n+3}$, но не делится на $2*2^{n+3}=2^{n+4}$. Таким образом, индукционный переход завершен.