# divisibility proof

• Jan 20th 2009, 02:24 PM
JediBlob
divisibility proof
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
• Jan 20th 2009, 10:27 PM
Constatine11
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 \$\displaystyle a(n)=2^{3^n}+1\$, and \$\displaystyle b(n)=3^{n+1}\$

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

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

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

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

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

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

.