1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving (10^m)-1 is divisible by 9

  1. Jul 23, 2012 #1
    Re: How many zeroes are at the end of (45^8)(88^5)

    Wow... didn't think of that, I used the google calculator and now I feel like a dumbass -.-. Thanks guys, feel better now. Here's another one I'm having a little difficulty with, and I don't feel like spamming these forums.

    Basically the part I'm having difficulty with is a portion of a larger proof. In this section of the aforementioned proof I have to show that (10 ^ m) - 1, for any given integer m, will be divisible by 9. I can easily solve it from example, but I want to be able to show that it will be true for any arbitrarily chosen m.. I guess it's a question of phrasing. Using the definition of divisibility I get..

    9 k = (10 ^ m) - 1 , and I should show that k must be an integer. Some help with this one would be nice
     
  2. jcsd
  3. Jul 23, 2012 #2

    Curious3141

    User Avatar
    Homework Helper

    Re: How many zeroes are at the end of (45^8)(88^5)

    Next time, please start a new thread for a new problem - don't worry about spam!

    The easiest way to do this is to use modular arithmetic. Are you familiar with that? Start with [itex]10 \equiv 1 \pmod 9[/itex].

    If you don't know how to work with that, the elementary way of showing this is to simply consider what happens when you subtract one from a number with 1 followed by nothing but zeroes. Then use the divisibility rule for 9.

    A final way to do it is to use Remainder Theorem to figure out the remainder when the polynomial [itex]x^m - 1[/itex] is divided by [itex]x-1[/itex], then substitute a suitable value for x to prove your case.
     
  4. Jul 23, 2012 #3
    Re: How many zeroes are at the end of (45^8)(88^5)

    Yeah I'm just getting to it now actually, but problem I mentioned is prior to the discussion of mod and div in the book. I suppose it expects me to just spell out what happens when one is subtracted from any number 10 ^ m could produce, but I thought there would be a general more axiomatic truth that I could use.. I guess that's what mod is, I'll read on, thanks for the heads up.
     
  5. Jul 23, 2012 #4

    Curious3141

    User Avatar
    Homework Helper

    Re: How many zeroes are at the end of (45^8)(88^5)

    I hope you took note of my final edit - one more way to do it that you might be more familiar with.
     
  6. Jul 25, 2012 #5

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    One more way is to remember that, for example, [itex]999 = 9 \times 10^2 + 9 \times 10^1 + 9 \times 10^0= 9(10^2 + \times 10^1 \times 10^0)[/itex], so if you can get [itex]10^m - 1[/itex] in this form, you will have shown that it is divisible by 9.

    To that, just use [itex]10^m-1 = 10^m -10 + 9 = 10(10^{m-1}-1) + 9 \times 10^0[/itex] iteratively until the exponent becomes m-m=0.
     
  7. Jul 25, 2012 #6

    Mentallic

    User Avatar
    Homework Helper

    Re: How many zeroes are at the end of (45^8)(88^5)

    Well it's not true for just any integer m, m=-1 gives us a fraction :tongue:

    So we want to prove this is true for all integers [itex]m\geq 0[/itex]. Induction is a relatively simple way of proving this.
     
  8. Jul 26, 2012 #7
    Consider using the binomial theorem with 10m = (1+9)m
     
  9. Jul 26, 2012 #8
    Hint for mathematical induction:
    [tex]
    10^{m + 1} = 10 \, 10^{m} = 10 (9 k_m + 1) = 90 k_m + 10 = 9 (10 k_m + 1) + 1
    [/tex]
     
  10. Jul 28, 2012 #9

    AGNuke

    User Avatar
    Gold Member

    I'll bet Binomial theorem is useful for proving divisibility with n if the desired form can be expressed in the form (nk ± 1), just expand and manipulate to get answer.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proving (10^m)-1 is divisible by 9
  1. Grade 9/10 Algebra. (Replies: 8)

  2. MAA Problem 9/22/10 (Replies: 0)

  3. Prove Divisibility (Replies: 7)

Loading...