Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I attempted this by induction: Here is what I did

For $k=1, 2^{3^{1}}+1 = 2^{3}+1 = 9 = 3^{2}$ is divisible by $3^{1}$ , so the result is true for $k=1$

Now I assume the result to be true for $k=m$,

$2^{3^{m}}+1$ is divisible by $3^m$. To show the result to be true for $k=(m+1)$,

$2^{3^{m+1}}+1 = 2^{3^m} \times 2^3+1$ and I was stuck here.

share|improve this question
1  
Do you mean $2^{3^{(m+1)}}+1$ in the last step –  Kirthi Raman Mar 14 '12 at 1:50
add comment

5 Answers

Hint $\rm\displaystyle\ \ 3\ \bigg|\ \frac{f(n+1)}{f(n)}\ \Rightarrow\ 3^k\ \bigg|\ \frac{f(1)}{f(0)}\frac{f(2)}{f(1)}\frac{f(3)}{f(2)}\cdots\frac{f(k)}{f(k-1)}\: =\: \frac{f(k)}{f(0)},\ $ a prototypical telescopy.

share|improve this answer
add comment

The last step you did can be corrected as

$$2^{3^{m+1}}+1 = (2^{3^m})^3+1$$ because if you look at it this way

$$(2^{3^m})^3 = (2^{3^m}) \times (2^{3^m}) \times (2^{3^m}) = 2^{3 \times 3^m} = 2^{3^{m+1}}$$

Using the fact that the result is true for $k=m$

$$2^{3^{m}}+1 = x \times 3^{m} \implies 2^{3^{m}} = x3^{m}-1 \tag{B}$$

$$ \begin{align*} 2^{3^{m+1}} &= (2^{3^m})^3 \\ &= (x3^{m}-1)^3 \\ &= x^3 3^{3m}-x^2 3^{2m+1}+x3^{m+1}-1\\ \end{align*} $$

Which means

$$2^{3^{m+1}}+1 = x^3 3^{3m}-x^2 3^{2m+1}+x3^{m+1} \tag{A}$$

And clearly $(A)$ shows the right side is divisible by $3^{m+1}$ because each term is divisible by $3^{m+1}$

which means $2^{3^{m + 1}}+1 = y3^{m+1}$ for some $y$, or the result is true for $k=(m+1)$.

share|improve this answer
add comment

Note that $2^{3^{m+1}}+1 = \left(2^{3^m} \right)^3 + 1 = \left(2^{3^m} + 1 \right)\left(\left(2^{3^m} \right)^2 - 2^{3^m} + 1 \right)$. By induction hypothesis, $3^m$ divides $\left(2^{3^m} + 1 \right)$. All you need to show is that $3$ divides $\left(\left(2^{3^m} \right)^2 - 2^{3^m} + 1 \right)$.

Hint: $2^{3^m} \equiv -1 (\bmod 3)$.

In-fact, proceeding along the same lines as you have done you can show that $3^{k+1}$ divides $2^{3^k}+1$

share|improve this answer
add comment

We show, as was observed by Sivaram Ambikasaran, that $3^{n+1}$ divides $2^{3^n}+1$. For $\varphi(3^{n+1})=2\cdot 3^n$. By Euler's Theorem, $2^{2\cdot 3^n}\equiv 1\pmod{3^{n+1}}$. Thus $2^{3^n}\equiv \pm 1 \pmod{ 3^{n+1}}$. But $2^{3^n}\not\equiv 1 \pmod{3}$, so $2^{3^n}\equiv -1\pmod{3^{n+1}}$.

Remark: It is not hard to show that $2$ is a primitive root of $3^{e}$ for every positive integer $e$. As a consequence, $2^{3^n}+1$ is not divisible by any power of $3$ greater than $3^{n+1}$.

share|improve this answer
add comment

Let F(k)= $2^{p^k}+1$ where p is prime and k in a natural number. Let b be the highest power of p that divides F(k). So, $F(k)=p^bq$ where q is a natural number and (p,q)=1. $$2^{p^k}=p^bq-1$$ Then,F(k+1)=$ 2^{p^{k+1}}+1 = ({2^{p^k}})^p +1 = (p^bq-1)^p+1 = p^{b+1}(q-pC_2p^{b-1}q^2+...+p^{(bp-b-1)}q) $ which is divisible by $ p^{b+1}$ if b≥1, but is never divisible by $ p^{b+2}$ as (p,q)=1.

$$Now,\ if\ p|({2^{p^r}}+1)\ ,\ i.e.,\ p|((1+1)^{p^r}+1),\ i.e.,\ p|(3+∑p^rC_r)\ where\ 1≤r<p $$ So, p|3 as each of $p^rC_r$ is divisible by p, which implies p=3.

Now F(0)=3, F(1)=$2^3+1=9\ is\ divisible\ by\ 3^1,\ F(2)=2^{3^2}+1= 513\ is \ divisible\ by\ 3^2 .$ So, by mathematical induction, F(k)= $2^{3^k}+1$ is divisible by $3^k$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.