Divisor and Remained Proof

  • Thread starter mattmns
  • Start date
  • Tags
    Proof
In summary, the question is to show that for all n >= 1, 10^n leaves a remainder of 1 after dividing by 9. The suggested approach is to use induction, with the base case of 10^k = 9m + 1 and the inductive step of showing that 10^(k+1) = 9(10m+1) + 1. Another approach mentioned is using the binomial theorem, which states that 10^n = (1+9)^n = 1 + \Sigma_{k=1}^{k=n}{(^nC_k)9^k}.
  • #1
1,128
6
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!
 
Mathematics news on Phys.org
  • #2
10^{n+1} = what times 10^n?
 
  • #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?
 
  • #4
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
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
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
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
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
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
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
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
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.
 

1. What is a divisor?

A divisor is a number that divides evenly into another number, resulting in a whole number as the quotient. For example, 3 is a divisor of 12 because 12 ÷ 3 = 4.

2. What is the remainder in a divisor and remainder proof?

The remainder is the amount left over after the dividend (number being divided) is divided by the divisor. It is the part of the dividend that is not evenly divisible by the divisor.

3. How do you write a divisor and remainder proof?

To write a divisor and remainder proof, you must start by stating the division problem in the form of dividend = divisor × quotient + remainder. Then, you can solve for the quotient and remainder using algebraic manipulation or long division.

4. Why is it important to use a divisor and remainder proof?

Using a divisor and remainder proof allows you to accurately show the relationship between a dividend, divisor, quotient, and remainder. It is a helpful tool in understanding division and can also be used in more complex mathematical concepts.

5. Can you use a divisor and remainder proof for fractions?

Yes, you can use a divisor and remainder proof for fractions. In this case, the divisor would be the denominator of the fraction and the remainder would be the numerator. However, the quotient may not always be a whole number and could result in a fraction or decimal.

Suggested for: Divisor and Remained Proof

Replies
1
Views
136
Replies
12
Views
1K
Replies
7
Views
763
Replies
11
Views
966
Replies
3
Views
1K
Replies
10
Views
179
Replies
8
Views
1K
Replies
13
Views
1K
Back
Top