Results 1 to 2 of 2

Math Help - 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 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

    .
    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: June 10th 2010, 10:47 AM
  2. divisibility proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 24th 2010, 08:45 AM
  3. Divisibility Proof
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: March 16th 2009, 06:11 PM
  4. Proof of divisibility
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 13th 2008, 01:53 PM
  5. divisibility proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 2nd 2007, 10:39 AM

Search Tags


/mathhelpforum @mathhelpforum