Results 1 to 14 of 14

Math Help - Divisibility 12

  1. #1
    Sea
    Sea is offline
    Junior Member Sea's Avatar
    Joined
    Dec 2008
    From
    Turkey
    Posts
    50

    Divisibility 12

    Show that:

    n\in \mathbb{Z^{+}},


    a) 3|4^{n}-1

    b) 11|3^{n+3}-4^{4n+2}

    c) 7|3^{2n+1}+2^{n+2}

    d) 11|12^{n}+10

    e) 17|3.5^{2n-1}+2^{3n-2}

    f) 8|5n+2.3^{n-1}+1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    Hi

    I did not read them all but most of them at least can be proved by induction
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Sea
    Sea is offline
    Junior Member Sea's Avatar
    Joined
    Dec 2008
    From
    Turkey
    Posts
    50
    Quote Originally Posted by running-gag View Post
    Hi

    I did not read them all but most of them at least can be proved by induction

    Thanks...but I cannot see the proves......



    Can you help me?.......
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,749
    Thanks
    650
    Hello, Sea!

    Here's one of them ... a non-inductive proof.


    Show that: . (d)\;\;11 \,|\,12^n + 10

    We have: . 12^n + 10

    . . . =\;(11+1)^n + (11-1)

    . . . = \;\bigg[11^n \;+\; {n\choose n-1}11^{n-1} + {n\choose n-2}11^{n-2} + \hdots  {n\choose 2}11^2 + {n\choose1}11\;+\;1\bigg] \;+\; \bigg[11 \;-\; 1\bigg]

    . . . = \;11^n \;+\; {n\choose n-1}11^{n-1} + {n\choose n-2}11^{n-2} + \hdots  {n\choose 2}11^2 + {n\choose1}11 + 11

    . . . = \;\underbrace{11\,\bigg[11^{n-1} \;+\; {n\choose n-1}11^{n-2} + {n\choose n-2}11^{n-3} + \hdots  {n\choose 2}11 + {n\choose1} + 1\bigg]}_{\text{a multiple of 11}}


    Therefore: . 11\text{ divides }12^n + 10

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Sea
    Sea is offline
    Junior Member Sea's Avatar
    Joined
    Dec 2008
    From
    Turkey
    Posts
    50
    Binomial theorem......similar...a lot of question...a lot of binomial theorem......very difficult...

    But,

    Thanks a million......
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,749
    Thanks
    650
    Hello, Sea!

    I tried problem (e) by Induction.
    . . It took more work than I anticipated . . .


    e)\;\;17\,|\,3\cdot5^{2n-1}+2^{3n-2}
    We have . S(n)\!:\;\;3\cdot5^{2n-1} + 2^{3n-2}\,\text{ is a multiple of 17.}


    Verify S(1)\!:\;\;3\cdot5^1 + 2^1 \:=\:17 . . . . True!


    Assume S(k)\!:\;\;3\cdot5^{2k-1} + 2^{3k-2} \:=\:17a\:\text{ for some integer }a


    Add . \left[72\cdot5^{2k-1} + 7\cdot2^{3k-2}\right] to both sides:

    . . \underbrace{3\cdot5^{2k-1} \:{\color{blue}+ \:72\cdot5^{2k-1}}} + \underbrace{2^{3k-2} \:{\color{blue}+ \:7\cdot2^{3k-2}}} \;=\;17a \:{\color{blue}+ \:72\cdot5^{2k-1} + 7\cdot2^{3k-2}}

    . . 3(1 + 24)\cdot5^{2k-1} + (1 + 7)\cdot2^{3k-2} \;=\; 17a + \overbrace{51\cdot5^{2k-1} + 21\cdot5^{2k-1}} + 7\cdot2^{3k-2}

    . . . . . . . . 3\cdot5^2\cdot5^{2k-1} + 2^3\cdot2^{3k-2} \;=\;17a + 51\cdot5^{2k-1} + 7\underbrace{\left(3\cdot5^{2k-1} + 2^{3k-2}\right)}_{\text{This is }17a}

    . . . . . . . . . . . . 3\cdot5^{2k+1} + 2^{3k+1} \;=\;17a + 51\cdot5^{2k-1} + 7(17a)

    . . . . . . . . . . . . \underbrace{3\cdot5^{2k+1} + 2^{3k+1}}_{\text{This is }S(k+1)}\;=\; \underbrace{17\left(a + 3\cdot5^{2k-1} + 7a\right)}_{\text{This is a multiple of 17}}


    The inductive proof is compete.

    Follow Math Help Forum on Facebook and Google+

  7. #7
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,
    Quote Originally Posted by Sea View Post
    Show that:

    n\in \mathbb{Z^{+}},


    a) 3|4^{n}-1
    \sum_{k=0}^{n-1} 4^k=\frac{4^n-1}{4-1}=\frac{4^n-1}{3}
    The LHS is an integer, hence the RHS has to be integer.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    If you've studied congruences, it would be much easier ^^'
    Quote Originally Posted by Sea View Post
    b) 11|3^{n+3}-4^{4n+2}
    There exists k such that :
    3^{n+3}-4^{4n+2}=11k, that is to say :
    4^{4n+2}=-11k+3^{n+3} (inductive hypothesis - you'll have to check for n=0)

    The purpose is to prove that there exists an integer m such that :
    3^{(n+1)+3}-4^{4(n+1)+2}=11m


    --->

    \begin{aligned}<br />
4^{4(n+1)+2}<br />
&=4^{4n+2+4} \\<br />
&=4^4 \cdot 4^{4n+2} \\<br />
&=4^4 \cdot \left(11k+3^{n+3}\right) \\<br />
&=\underbrace{4^4 \cdot 11k}_{=11k'}+4^4 \cdot 3^{n+3} \\<br />
&=11k'+256 \cdot 3^{n+3} \end{aligned}

    Note that 256=253+3=11 \cdot 23+3

    \begin{aligned}<br />
4^{4(n+1)+2}<br />
&=\underbrace{11k'+11 \cdot (253 \cdot 3^{n+3})}_{=11k''}+3 \cdot 3^{n+3} \\<br />
&=11k''+3^{n+4} \end{aligned}

    And you're done.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Sea
    Sea is offline
    Junior Member Sea's Avatar
    Joined
    Dec 2008
    From
    Turkey
    Posts
    50
    Quote Originally Posted by Sea View Post
    Show that:

    n\in \mathbb{Z^{+}},


    c) 7|3^{2n+1}+2^{n+2}

    We must show  f(n) = 3^{(2n+1)} + 2^{(n+2)} = 0 (mod 7)

     f(n) = 3 \times 9^n + 4 \times 2^n = 0 (mod 7)

    We can write f(n) in the form

     f(n) = 3 \times (7 + 2)^n + 4 \times 2^n

     3[7^n + C(n,1)7^{(n-1)}.2 + .... + 2^n] + 4 \times  2^n

     3 \times M(7) + 3 \times 2^n + 4 \times 2^n

    where M(7) means 'is a multiple of 7'

    The first term = 0 (mod 7) so now we are reduced to finding

     3 \times 2^n + 4 \times 2^n

    This can be written  2^n[3 + 4] = 2^n \times 7 = 0 (mod 7)

    and this completes the proof. We have shown

     3^{(2n+1)} + 2^{(n+2)} = 0 (mod 7)

    i.e., the expression on the left is a multiple of 7


    and


    Thanks Anthony......
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Gaaaaah T.T so you know congruences !


    a) 3|4^{n}-1
    4=1 (\bmod 3)
    So \begin{aligned} 4^n-1<br />
&=1^n-1 (\bmod 3) \\<br />
&=0 (\bmod 3) \end{aligned}

    b) 11|3^{n+3}-4^{4n+2}
    \begin{aligned}<br />
3^{n+3}-4^{4n+2}<br />
&= {\color{red}27} \cdot 3^n-{\color{red}16} \cdot ({\color{red}4^4})^n \\<br />
&=5 \cdot 3^n-5 \cdot 3^n (\bmod 11) \\<br />
&=0 (\bmod 11) \end{aligned}

    c) 7|3^{2n+1}+2^{n+2}
    \begin{aligned}<br />
3^{2n+1}+2^{n+2}<br />
&=3 \cdot ({\color{red}3^2})^n+{\color{red}4} \cdot 2^n \\<br />
&=3 \cdot 2^n-3 \cdot 2^n (\bmod 7) \\<br />
&=0 (\bmod 7)<br />
\end{aligned}

    d) 11|12^{n}+10
    \begin{aligned}<br />
{\color{red}12}^n+{\color{red}10}<br />
&=1^n+(-1) (\bmod 11) \\<br />
&=0 (\bmod 11)<br />
\end{aligned}



    (the red parts are changed into an equivalent modulo ..)
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Sea
    Sea is offline
    Junior Member Sea's Avatar
    Joined
    Dec 2008
    From
    Turkey
    Posts
    50
    I know congruences......

    I understand

    and...

    Thanks a million......
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Sea
    Sea is offline
    Junior Member Sea's Avatar
    Joined
    Dec 2008
    From
    Turkey
    Posts
    50
    And


    Quote Originally Posted by Sea View Post
    Show that:

    n\in \mathbb{Z^{+}},

    f) 8|5n+2.3^{n-1}+1

    This is false...

    Because;

    n=2 \Rightarrow 5n+2.3^{n-1}+1=5\times 2+2\times3^{2-1}+1=10+6+1=17


    But 8 \nmid 17
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Sea
    Sea is offline
    Junior Member Sea's Avatar
    Joined
    Dec 2008
    From
    Turkey
    Posts
    50
    f) 5n + 2 x 3^{(n-1)} + 1
    This is false

    and

    I think...

    8|5^n + 2 x 3^{(n-1)} + 1
    This is true...



    f(n) = 5^n + 2 x 3^{(n-1)} + 1

    Now if n=2 we get 25 + 2 x 3 + 1 = 32 = M(8)

    and if n=3 we get 125 + 2 x 9 + 1 = 144 = M(8)

    and so we must prove f(n) = 5^n + 2 x 3^{(n-1)} + 1 = 0 (mod 8)

    It will be more convenient to use f(n+1) but this does not alter the proof

     f(n+1) = 5^{(n+1)} + 2 x 3^n + 1

    = 5 x 5^n + 2 x 3^n + 1

     = 5 x (8 - 3)^n + 2 x 3^n + 1

     = 5 x [8^n + M(8) +- 3^n] + 2 x 3^n + 1

     = 5 x [8^n + M(8)] +- 5 x 3^n + 2 x 3^n + 1


    We can ignore the first term as it will be divisible by 8 and look at

     5 x 3^n + 2 x 3^n + 1     if n is even .......(1)

    and -5 x 3^n + 2 x 3^n + 1 if n is odd .......(2)

    For (1) we have 3^n[5 + 2] + 1  and putting n = 2m to make it even


      =  7 x 3^2m + 1

    =  7 x 9^m + 1

    =  7 x (8 + 1)^m + 1

    =  7 x (8^m + M(8) + 1) + 1

    =  7 x (8^m + M(8)] + 7 + 1


    = M(8) + 8 = 0 (mod 8) so OK if n is even

    For (2) we have n odd and write it 2m+1 so we have

    =  3^{(2m+1)}.[-5 + 2] + 1

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

    =  -3^{(2m+2)}+ 1

    =   -9^{(m+1)}  + 1

    =  -(8+1)^{(m+1)} + 1

    =  -[8^{(m+1)} + M(8) + 1] + 1

      =  -[8^{(m+1)} + M(8)] - 1 + 1


    =  -[8^{(m+1)} + M(8)]    =  0 (mod 8)  so OK if n is odd




    and so for n either even or odd we have shown

    5^n + 2 x 3^{(n-1)} + 1 = 0 (mod 8)



    and



    Thanks Anthony......
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    5^n=(8-3)^n\equiv(-3)^n\pmod{8}\equiv\begin{cases}-3\pmod{8}\ \mbox{if $n$ is odd}\\<br />
1\pmod{8}\ \mbox{if $n$ is even}\end{cases}

    2\times3^{n-1}=2\times(4-1)^{n-1}\equiv2\times(-1)^{n-1}\pmod{8}

    Hence, if n is odd, 5^n+2\times3^{n-1}+1\equiv-3+2+1=0\pmod{8} and if n is even, 5^n+2\times3^{n-1}+1\equiv1-2+1=0\pmod{8}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 20th 2008, 02:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 04:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 01:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 03:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum