Results 1 to 14 of 14

Thread: Divisibility 12

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

    Divisibility 12

    Show that:

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


    a) $\displaystyle 3|4^{n}-1$

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

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

    d) $\displaystyle 11|12^{n}+10$

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

    f) $\displaystyle 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
    54
    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
    12,028
    Thanks
    848
    Hello, Sea!

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


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

    We have: .$\displaystyle 12^n + 10$

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

    . . . $\displaystyle = \;\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]$

    . . . $\displaystyle = \;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$

    . . . $\displaystyle = \;\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: .$\displaystyle 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
    54
    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
    12,028
    Thanks
    848
    Hello, Sea!

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


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


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


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


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

    . . $\displaystyle \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}}$

    . . $\displaystyle 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} $

    . . . . . . . .$\displaystyle 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} $

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

    . . . . . . . . . . . . $\displaystyle \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:

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


    a) $\displaystyle 3|4^{n}-1$
    $\displaystyle \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) $\displaystyle 11|3^{n+3}-4^{4n+2}$
    There exists k such that :
    $\displaystyle 3^{n+3}-4^{4n+2}=11k$, that is to say :
    $\displaystyle 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 :
    $\displaystyle 3^{(n+1)+3}-4^{4(n+1)+2}=11m$


    --->

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

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

    $\displaystyle \begin{aligned}
    4^{4(n+1)+2}
    &=\underbrace{11k'+11 \cdot (253 \cdot 3^{n+3})}_{=11k''}+3 \cdot 3^{n+3} \\
    &=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
    54
    Quote Originally Posted by Sea View Post
    Show that:

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


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

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

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

    We can write f(n) in the form

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

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

    $\displaystyle 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

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

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

    and this completes the proof. We have shown

    $\displaystyle 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) $\displaystyle 3|4^{n}-1$
    $\displaystyle 4=1 (\bmod 3)$
    So $\displaystyle \begin{aligned} 4^n-1
    &=1^n-1 (\bmod 3) \\
    &=0 (\bmod 3) \end{aligned}$

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

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

    d) $\displaystyle 11|12^{n}+10$
    $\displaystyle \begin{aligned}
    {\color{red}12}^n+{\color{red}10}
    &=1^n+(-1) (\bmod 11) \\
    &=0 (\bmod 11)
    \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
    54
    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
    54
    And


    Quote Originally Posted by Sea View Post
    Show that:

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

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

    This is false...

    Because;

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


    But $\displaystyle 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
    54
    f)$\displaystyle 5n + 2 x 3^{(n-1)} + 1 $
    This is false

    and

    I think...

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



    $\displaystyle 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 $\displaystyle 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

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

    $\displaystyle = 5 x 5^n + 2 x 3^n + 1 $

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

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

    $\displaystyle = 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

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

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

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


    $\displaystyle = 7 x 3^2m + 1 $

    $\displaystyle = 7 x 9^m + 1 $

    $\displaystyle = 7 x (8 + 1)^m + 1 $

    $\displaystyle = 7 x (8^m + M(8) + 1) + 1 $

    $\displaystyle = 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

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

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

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

    $\displaystyle = -9^{(m+1)} + 1 $

    $\displaystyle = -(8+1)^{(m+1)} + 1 $

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

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


    $\displaystyle = -[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

    $\displaystyle 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
    $\displaystyle 5^n=(8-3)^n\equiv(-3)^n\pmod{8}\equiv\begin{cases}-3\pmod{8}\ \mbox{if $n$ is odd}\\
    1\pmod{8}\ \mbox{if $n$ is even}\end{cases}$

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

    Hence, if $\displaystyle n$ is odd, $\displaystyle 5^n+2\times3^{n-1}+1\equiv-3+2+1=0\pmod{8}$ and if $\displaystyle n$ is even, $\displaystyle 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: Dec 20th 2008, 02:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 19th 2008, 04:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 19th 2008, 01:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Dec 19th 2008, 03:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum