Proving 10^n Leaves a Remainder of 1 After Dividing by 9 Using Induction

[mattmns]

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 10^n leaves remainder 1 after dividing by 9.

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

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!

 

[matt grime]

10^{n+1} = what times 10^n?

 

[mattmns]

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?

 

[HallsofIvy]

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 10^n leaves remainder 1 after dividing by 9.

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

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:10ⁿ, 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 10ⁿ divided by 9 leaves a remainder of n. What can we say about 10ⁿ⁺¹? Thefirst thing that occurs to me is that 10ⁿ⁺¹= 10*10ⁿ! Dividing that by 9 gives 10/9*(10ⁿ)(10/9). What is the remainder of that?

 

[mattmns]

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.

 

[Curious3141]

Have you considered binomial theorem ?

10^n = {(1 + 9)}^n = 1 + \Sigma_{k=1}^{k=n}{(^nC_k)9^k} = 1 + 9m where m is an integer.

 

[Curious3141]

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 :

10^k = 9m + 1 for integral m.

Then

10^{k + 1} = 10.10^k = (9 + 1).(9m + 1) = 9(10m + 1) + 1

and I'm sure you can see the rest.

 

[AKG]

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

10ⁿ⁺¹ = 10(10ⁿ) = 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.

 

[Alkatran]

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...

 

[matt grime]

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.

 

[AKG]

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.

 

[mattmns]

I looked in my analysis book which has a somewhat similar proof, by induction, and now I see what you guys were saying

Thanks to all that responded.