Results 1 to 2 of 2

Thread: divisibility proof

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    1

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2006
    Posts
    244
    Quote Originally Posted by JediBlob View Post
    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$

    .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility proof
    Posted in the Algebra Forum
    Replies: 7
    Last Post: Jun 10th 2010, 10:47 AM
  2. divisibility proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jan 24th 2010, 08:45 AM
  3. Divisibility Proof
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: Mar 16th 2009, 06:11 PM
  4. Proof of divisibility
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 13th 2008, 01:53 PM
  5. divisibility proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 2nd 2007, 10:39 AM

Search Tags


/mathhelpforum @mathhelpforum