divisibility proof

Quote:

Originally Posted by JediBlob

I am really having trouble answering this question that i've been set

Prove that 2^(3^n) + 1 is divisible by 3^(n+1)

i have tried a few numbers and it definately is true, however i have no idea how to prove it, any help would be greatly appreciated

Use induction.

Put $a(n)=2^{3^n}+1$ , and $b(n)=3^{n+1}$

Then $a(1)=9$ and $b(1)=9$ so the base case holds.

Now suppose $a(k)=b(k)$ for some $k\ge 1$ , then:

$a(k+1)=2^{3^{n+1}}+1=(2^{3^n})^3+1$

............ $= (2^{3^n}+1)[(2^{3^n})^2-2^{3^n}+1]$

The first of the terms is divisible by $b(k)$ by assumption, and as a odd power of two is congurent to $-1$ modulo $3$ and its square is congruent to $1$ modulo $3$ the second factor is divisible by $3$ and so we have $a(k+1)$ is divisible by $3 b(k)=b(k+1)$ .

Which allows us to conclude by mathematical induction that $a(n)$ is divisible by $b(n)$ for any $n\ge 1$

.