What is the division algorithm?

[Daniellec08]

10q +r, where 0<=r<=9?

So, I am struggling through my proofs class and I'm sure this problem is pretty easy, but I am just not seeing how I should begin. My first thought was induction since that was the last section but I think not.

Question: Show that ay integer can be written in the form 10q +r, where 0<=r<=9.

It's in the section with divide-and-conquer and bootstrap case analysis.

I think I might have to prove this for each case, 0 to 9 but there are no examples of how to do this in the book.

Thanks

 

[JThompson]

You could definitely use induction on this. In your inductive step, use two cases-
Suppose that there exist integers q and r, 0<=r<=9, so that n=10q+r.
If 0<=r<=8, then n+1=...
If r=9, then n+1=...

 

[Mark44]

I think that I would approach it this way: Any integer in base-10 form can be written as a linear combination of powers of 10:
$$a_n\cdot 10^n + a_{n - 1}\cdot 10^{n - 1} + ... + a_1 \cdot 10 + a_0$$

where 0 <= a_is <= 0, i = 0, ..., n
Factor 10 out of all but the last term and you're almost done.

 

[vela]

It's in the section with divide-and-conquer and bootstrap case analysis.

What are divide-and-conquer and bootstrap case analysis? This problem is a special case of the division algorithm, so I'm thinking it may have to do with whatever divide-and-conquer means.

In one proof, you look at the set of numbers of the form a-10n, where n is an integer, and choose the least non-negative element. (You have to show that you can do that.) Call that r. Then r=a-10q for some integer q, so a=10q+r. You just then have to prove that r is between 0 and 9. If you assume r<0 or r>9, you can show it leads to a contradiction.