# Divisor and Remained Proof

## 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 $$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
Homework Helper
10^{n+1} = what times 10^n?

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
Homework Helper
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 $$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: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?

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
Homework Helper
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
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 :

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

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

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

AKG