Divisor and Remained Proof

  • Thread starter mattmns
  • Start date
  • #1
1,085
6

Main Question or Discussion Point

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!
 

Answers and Replies

  • #2
matt grime
Science Advisor
Homework Helper
9,395
3
10^{n+1} = what times 10^n?
 
  • #3
1,085
6
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?
 
  • #4
HallsofIvy
Science Advisor
Homework Helper
41,833
955
mattmns said:
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!
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?
 
  • #5
1,085
6
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.
 
  • #6
Curious3141
Homework Helper
2,843
87
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.
 
  • #7
Curious3141
Homework Helper
2,843
87
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.
 
  • #8
AKG
Science Advisor
Homework Helper
2,565
4
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.
 
  • #9
Alkatran
Science Advisor
Homework Helper
944
0
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...
 
  • #10
matt grime
Science Advisor
Homework Helper
9,395
3
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.
 
  • #11
AKG
Science Advisor
Homework Helper
2,565
4
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.
 
  • #12
1,085
6
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.
 

Related Threads on Divisor and Remained Proof

Replies
8
Views
2K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
11
Views
4K
Replies
2
Views
11K
  • Last Post
Replies
9
Views
21K
  • Last Post
Replies
6
Views
1K
Replies
4
Views
2K
Replies
2
Views
500
Top