Results 1 to 8 of 8

Math Help - divisible by 9

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    28

    divisible by 9

    Prove that 2^(2n) - 3n - 1 is divisible by 9 for all n in N. (Hint: 2^(2n) = (3+1)^n)

    Please help. Thank you in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor red_dog's Avatar
    Joined
    Jun 2007
    From
    Medgidia, Romania
    Posts
    1,252
    Thanks
    5
    First of all we have that

    4^n-1=(4-1)(4^{n-1}+4^{n-2}+\ldots+4+1)=3(4^{n-1}+4^{n-2}+\ldots+4+1)=3a

    Now

    2^{2n}-3n-1=(4^n-1)-3n=3(4^{n-1}+4^{n-2}+\ldots+4+1)-3n=

    =3(4^{n-1}+4^{n-2}+\ldots+4+1-n)=

    =3[(4^{n-1}-1)+(4^{n-2}-1)+\ldots+(4-1)]=

    =3(3a_1+3a_2+\ldots+3a_{n-1}+3)=9(a_1+a_2+\ldots+a_{n-1}+1)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by john_n82 View Post
    Prove that 2^(2n) - 3n - 1 is divisible by 9 for all n in N. (Hint: 2^(2n) = (3+1)^n)

    Please help. Thank you in advance.
    proof by induction

    n=1
    2^2-3(1)-1=0 and 0 is divisable by 9

    assume n=k

    2^{2k}-3k-1 is divisable by 9

    Show k+1

    2^{2(k+1)}-3(k+1)-1=2^{2k+2}-3k-4=4\cdot 2^k-3k-4

    Now we want to use the induction hypothesis so we will fix up the equation so we can

    4\cdot(2^k-3k-1)-4\cdot (-3k)-4\cdot(-1)-3k-4=4\cdot(2^k-3k-1)+9k

    so the first term is divisable by 9 by the induction hypothesis and 9k is obviously divisable by 9 so we are done.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Feb 2009
    Posts
    28
    red_dog and TheEmptySet,

    thank you for your super help.

    JN
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2009
    Posts
    4

    Re: Divisibility question...

    Quote Originally Posted by john_n82 View Post
    Prove that 2^(2n) - 3n - 1 is divisible by 9 for all n in N. (Hint: 2^(2n) = (3+1)^n)

    Please help. Thank you in advance.
    I believe that this proof could be approached a couple of different ways. Below I use modular arithmatic and the idea of congruency for the proof.

     <br />
\text{THM}:\text{ }9\left| 2^{2n}-3n-1 \text{for} \forall n\in \mathbb{N}\right.<br />

    PF: \text{Let} n\in \mathbb{N}. Then n must be congruent to one of the following
    0 , 1, 2, 3, 4, 5, 6, 7, 8 (mod 9).

     <br />
\text{If} n \equiv 0 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(0)}-3(0)-1 = 0 \equiv 0 (\text{mod} 9)<br />
     <br />
\text{If} n \equiv 1 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(1)}-3(1)-1 = 0 \equiv 0 (\text{mod} 9)<br />
     <br />
\text{If} n \equiv 2 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(2)}-3(2)-1 = 9 \equiv 0 (\text{mod} 9) <br />
     <br />
\text{If} n \equiv 3 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(3)}-3(3)-1 = 54 \equiv 0 (\text{mod} 9) <br />
     <br />
\text{If} n \equiv 4 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(4)}-3(4)-1 = 243 \equiv 0 (\text{mod} 9) <br />
     <br />
\text{If} n \equiv 5 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(5)}-3(5)-1 = 1008 \equiv 0 (\text{mod} 9) <br />
     <br />
\text{If} n \equiv 6 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(6)}-3(6)-1 = 4077 \equiv 0 (\text{mod} 9) <br />
     <br />
\text{If} n \equiv 7 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(7)}-3(7)-1 = 16362 \equiv 0 (\text{mod} 9) <br />
     <br />
\text{If} n \equiv 8 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(8)}-3(8)-1 = 65511 \equiv 0 (\text{mod} 9) <br />

    In all cases, 2^{2n}-3n-1\equiv 0 (\text{mod} 9).\text{ }\text{Therefore} \text{ }2^{2n}-3n-1 \text{ }\text{is} \text{ }\text{divisible} \text{ }\text{by} \text{ }9\therefore


    --------------------------------
    Josh
    --------------------------------
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Feb 2009
    Posts
    28
    Quote Originally Posted by Invertible View Post
    I believe that this proof could be approached a couple of different ways. Below I use modular arithmatic and the idea of congruency for the proof.

     <br />
\text{THM}:\text{ }9\left| 2^{2n}-3n-1 \text{for} \forall n\in \mathbb{N}\right.<br />

    PF: \text{Let} n\in \mathbb{N}. Then n must be congruent to one of the following
    0 , 1, 2, 3, 4, 5, 6, 7, 8 (mod 9).

     <br />
\text{If} n \equiv 0 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(0)}-3(0)-1 = 0 \equiv 0 (\text{mod} 9)<br />
     <br />
\text{If} n \equiv 1 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(1)}-3(1)-1 = 0 \equiv 0 (\text{mod} 9)<br />
     <br />
\text{If} n \equiv 2 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(2)}-3(2)-1 = 9 \equiv 0 (\text{mod} 9) <br />
     <br />
\text{If} n \equiv 3 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(3)}-3(3)-1 = 54 \equiv 0 (\text{mod} 9) <br />
     <br />
\text{If} n \equiv 4 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(4)}-3(4)-1 = 243 \equiv 0 (\text{mod} 9) <br />
     <br />
\text{If} n \equiv 5 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(5)}-3(5)-1 = 1008 \equiv 0 (\text{mod} 9) <br />
     <br />
\text{If} n \equiv 6 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(6)}-3(6)-1 = 4077 \equiv 0 (\text{mod} 9) <br />
     <br />
\text{If} n \equiv 7 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(7)}-3(7)-1 = 16362 \equiv 0 (\text{mod} 9) <br />
     <br />
\text{If} n \equiv 8 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(8)}-3(8)-1 = 65511 \equiv 0 (\text{mod} 9) <br />

    In all cases, 2^{2n}-3n-1\equiv 0 (\text{mod} 9).\text{ }\text{Therefore} \text{ }2^{2n}-3n-1 \text{ }\text{is} \text{ }\text{divisible} \text{ }\text{by} \text{ }9\therefore


    --------------------------------
    Josh
    --------------------------------
    Josh, thank you for helping me. I think i could use this method to approach similar problems for small integers, right?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Feb 2009
    Posts
    4
    Quote Originally Posted by john_n82 View Post
    Josh, thank you for helping me. I think i could use this method to approach similar problems for small integers, right?
    Yes. To use congruency, you have to show that every possible remainder is equivelent to 0 (mod 9). The bigger the devisor, the more remainders you will have to test.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Quote Originally Posted by john_n82 View Post
    (Hint: 2^(2n) = (3+1)^n)
    Observe that all the terms in the binomial expansion of (3+1)^n are divisible by 9 except the first two. Hence

    2^{2n}=(3+1)^n\equiv3n+1\pmod9*

    \therefore\ 2^{2n}-3n-1\equiv0\pmod9*

    in other words, 2^{2n}-3n-1 is divisible by 9.


    *Another way of writing it out:

    2^{2n}\ =\ (3+1)^n\ =\ \underbrace{3^n+n\cdot3^{n-1}+\cdots+\binom{n}{2}3^2}_{\textrm{divisible by 9}}+3n+1

    \therefore\ 2^{2n}-3n-1\ =\ \underbrace{3^n+n\cdot3^{n-1}+\cdots+\binom{n}{2}3^2}_{\textrm{divisible by 9}}
    Last edited by JaneBennet; February 22nd 2009 at 07:53 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: February 20th 2013, 10:32 AM
  2. Divisible by 9
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: August 17th 2011, 03:48 AM
  3. Replies: 8
    Last Post: July 3rd 2011, 04:55 PM
  4. Replies: 1
    Last Post: May 8th 2010, 12:49 AM
  5. Replies: 5
    Last Post: January 1st 2010, 02:59 AM

Search Tags


/mathhelpforum @mathhelpforum