# Divisor and Remained Proof

1. Aug 25, 2005

### 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!

2. Aug 25, 2005

### matt grime

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

3. Aug 25, 2005

### 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?

4. Aug 25, 2005

### HallsofIvy

Staff Emeritus
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. Aug 25, 2005

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

6. Aug 25, 2005

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

7. Aug 25, 2005

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

8. Aug 26, 2005

### AKG

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. Aug 26, 2005

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

10. Aug 26, 2005

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

11. Aug 26, 2005

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

12. Aug 26, 2005

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