Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Divisor and Remained Proof

  1. Aug 25, 2005 #1
    I got this question, I guess I am supposed to use induction to prove this, but I am not seeing it.

    The question is: Show for all n >= 1, that [tex]10^n[/tex] leaves remainder 1 after dividing by 9.

    So I said that there is an integer m, such that [tex]10^n = 9m + 1[/tex]

    I also see that m has to be 1, or 11, or 111, or 1111, ..... but I am unsure of where to go from there and if that is even useful.

    So how I am supposed to use induction here? I would think that I would want m in terms of n, but I am not seeing it. Any ideas would be great, thanks!
     
  2. jcsd
  3. Aug 25, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    10^{n+1} = what times 10^n?
     
  4. Aug 25, 2005 #3
    10

    So multiple by 10 on both sides, but then what am I proving?

    that 10^{n+1} = 10(9m + 1) ?

    I guess I am thinking that there needs to be an 'n' on both sides or that I need to prove that m is an integer. Am I wrong? Or could I say that 'm' is a certain value for a certain value of n?
     
  5. Aug 25, 2005 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Couldn't be HOMEWORK, could it? I mean, obviously, you would have posted it under the "homework" section, wouldn't you!


    Hmm, how to prove that dividing a power of 10:10n, divided by nine, leaves a remaider of 1. Am I the only one who suspects a "proof by induction on n" is lurking here?

    10/9= 1 plus a remainder of 1. That was pretty easy!

    Now, suppose 10n divided by 9 leaves a remainder of n. What can we say about 10n+1? Thefirst thing that occurs to me is that 10n+1= 10*10n! Dividing that by 9 gives 10/9*(10n)(10/9). What is the remainder of that?
     
  6. Aug 25, 2005 #5
    Sorry, you are right, I should have posted this in the HW section.

    I am, however, baffled as to what you said.

    10^n divided by 9 leaves a remainder of n? I thought the remainder was always 1. Ok supposing that it leaves a remainder of n. 10^{n+1} = 10*10^n, ok yes. Dividing that by 9 gives: 10/9*(10^n)(10/9). Ok how did you get this? Unless this is in some special format, or I am missing something, I would think that dividing by 9 would give: (10/9)(10^n). Am I missing something here? Thanks.
     
  7. Aug 25, 2005 #6

    Curious3141

    User Avatar
    Homework Helper

    Have you considered binomial theorem ?

    [tex]10^n = {(1 + 9)}^n = 1 + \Sigma_{k=1}^{k=n}{(^nC_k)9^k} = 1 + 9m[/tex] where m is an integer.
     
  8. Aug 25, 2005 #7

    Curious3141

    User Avatar
    Homework Helper

    Of course, it's also trivially easy to prove by induction. In this case the inductive step would go something like :

    Assum 10^k (for some k) leaves remainder 1 when divided by 9, that is :

    [tex]10^k = 9m + 1[/tex] for integral m.

    Then

    [tex]10^{k + 1} = 10.10^k = (9 + 1).(9m + 1) = 9(10m + 1) + 1[/tex]

    and I'm sure you can see the rest.
     
  9. Aug 26, 2005 #8

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Assume 1 remains after dividing 10n by 9, so that 10n = 9m + 1 for some natural m. Then:

    10n+1 = 10(10n) = 10(9m + 1) = 90m + 10 = 90m + (9 + 1) = (90m + 9) + 1 = 9(10m + 1) + 1

    as required. I went a little overkill there with the associativity of addition, but maybe it's helpful to see where the numbers are coming from.
     
  10. Aug 26, 2005 #9

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    I'd go for something more along the lines of the summation of 9*10^0 + 9*10^21+ ... + 9*10 ^ (n-1) + 1 = 10 ^ n, all of the terms in the summation have a remainder of 0 when divided by 9, except for 1. hmmm...
     
  11. Aug 26, 2005 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    yes, but the OP required a proof by induction. The best proof is undoubtedyl that 10=9+1 and use the binomial theorem, but that isn't a proof by induction.
     
  12. Aug 26, 2005 #11

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    I don't think the OP required a proof by induction, he said he guessed that that's what was needed to do the proof.
     
  13. Aug 26, 2005 #12
    I looked in my analysis book which has a somewhat similar proof, by induction, and now I see what you guys were saying :smile:

    Thanks to all that responded.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Divisor and Remained Proof
  1. Integral Divisors (Replies: 2)

  2. Greatest common divisor (Replies: 11)

Loading...