Results 1 to 6 of 6

Math Help - Prove 16^m + 10m -1 is always divisible by 25

  1. #1
    Newbie
    Joined
    Mar 2011
    Posts
    16

    Prove 16^m + 10m -1 is always divisible by 25

    How can I prove that 16^m + 10m -1 is always divisible by 25 when m is a whole number greater than zero.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    skeeter's Avatar
    Joined
    Jun 2008
    From
    North Texas
    Posts
    11,698
    Thanks
    454
    Quote Originally Posted by jeremy5561 View Post
    How can I prove that 16^m + 10m -1 is always divisible by 25 when m is a whole number greater than zero.
    sounds like a proof by induction ... show true for m = 1, assume true for m, prove true for (m+1)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,738
    Thanks
    645
    Hello, jeremy5561!

    skeeter is right . . . An inductive proof is in order.

    Even then, I had difficulty with the inductive step.
    Perhaps someone has a better method . . .


    \text{Prove that: }\,16^m + 10m -1 \,\text{ is divisible by 25 for any positive integer }m.

    \text{Verify }S(1)\!:\;16^1 + 10(1) - 1 \:=\:25\;\hdots\;\text{True!}

    \text{Assume }S(k)\!:\;16^k + 10k - 1 \:=\:25a\,\text{ for some integer }a.



    \text{Add }(15\!\cdot\!16^k + 10)\text{ to both sides:}

    . . 16^k + {\bf15\!\cdot\!16^k} + 10k + {\bf10} - 1 \;=\;25a + {\bf15\!\cdot\!16^k} + {\bf10}

    . . . (1 + 15)\!\cdot\!16^k + 10(k+1) - 1 \;=\;25a + 15\!\cdot\!16^k + 10

    . . . . . . . \underbrace{16^{k+1} + 10(k+1) - 1}_{\text{Left side of }S(k+1)} \;=\;25a + 15\!\cdot\!16^k + 10

    And we must show that 15\!\cdot\!16^k + 10 is a multiple of 25.
    . . That is, that 3\!\cdot\!16^k + 2 is a multiple of 5.


    3\!\cdot\!16^k + 2 \;=\;3(4^2)^k + 2

    . . . . . . . . =\;3(4)^{2k} + 2

    . . . . . . . . =\;3(5-1)^{2k} + 2

    . . . . . . . . =\;3\bigg[5^{2k} - {2k\choose2k-1}5^{2k-1} + \hdots + {2k\choose2}5^2 - {2k\choose1}5 + 1\bigg] + 2

    . . . . . . . . =\;3\bigg[5^{2k} - {2k\choose2k-1}5^{2k-1} + \hdots + {2k\choose2}5^2 - {2k\choose1}5\bigg] + 3 + 2

    . . . . . . . . =\;3\bigg[5^{2k} - {2k\choose2k-1}5^{2k-1} + \hdots + {2k\choose2}5^2 - {2k\choose1}5\bigg] + 5

    . . . . . . . . =\;5\,\bigg[3\bigg(5^{2k-1} - {2k\choose2k-1}5^{2k-2} + \hdots + {2k\choose2}5 - {2k\choose1}\bigg) + 1\bigg]

    . . \text{Q. E. D.}



    But there must be a better way!
    .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2011
    Posts
    16
    My teacher hinted towards the binomial theorem. Don't know if that will help. He didn't say much else.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jan 2011
    Posts
    71
    Maybe try writing it as
    (15+1)^m+10m-1
    and then expand using the binomial theorem.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2010
    Posts
    193
    If you know any modern algebra (modular arithmetic), you only really need check the cases m=0,1,2,3,4, since 16^5\equiv1\,(\mod\,25). You could generalize each of those cases to when m=5q+r,r=0,1,2,3,4.

    I wouldn't recommend this over the induction, if the induction didn't look so messy.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: May 7th 2010, 11:49 PM
  2. prove (a^n)-1 is divisible by a-1
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 13th 2008, 04:09 PM
  3. Prove n is divisible by 2^m
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 24th 2008, 03:54 AM
  4. prove that then n is divisible by 11
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 23rd 2008, 11:05 PM
  5. Prove n is divisible by 3
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 23rd 2008, 06:10 PM

Search Tags


/mathhelpforum @mathhelpforum