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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Do you mean $2^{3^{(m+1)}}+1$ in the last step – Kirthi Raman Mar 14 '12 at 1:50

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|cite|improve this answer

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|cite|improve this answer

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|cite|improve this answer

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|cite|improve this answer

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|cite|improve this answer

Your Answer


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.