Division Theorem [proof by induction]

[mattmns]

First let me say that this is not technically the Division Theorem that I will be proving. Our book calls it the Euclidean Algorithm, but this is clearly not true, it is closer to the Division Theorem, imo. Anyway, my book wants us to prove the following proposition.

Note: Here natural numbers will include 0. Also a positive number is a natural number that is not equal to 0.

Proposition. Let n be a natural number, and let q be a positive number. Then there exist natural numbers m, r such that 0 \leq r < q and n = mq + r

Proof: (Holding q fixed, and using induction on n)

Base Case (n=0)
If n = 0, then we can take m = 0 and r = 0, and we will have 0 \leq r < q since 0 \leq 0 < q and we will also have n = 0 = 0q + 0 = 0. So the proposition is true when n = 0.

Inductive Step
Assume that for some natural number n and fixed positive number q, that there exist natural numbers m, r such that 0 \leq r < q and n = mq + r. Then we want to show that the same properties are true for n + 1.

We have 0 \leq r < q and I will break this up into two cases.

Case 1: (0 \leq r < q - 1)
n = mq + r
=> n + 1 = mq + r + 1
but 0 \leq r < q - 1 so 0 + 1 \leq r + 1 < q thus we can say that 0 \leq r + 1 < q
and we have n + 1 = mq + (r + 1) as required.

Case 2: (r = q - 1)
again n = mq + r by our inductive hypothesis
so n + 1 = mq + r + 1 = mq + (q - 1) + 1 = mq + q = (m + 1)q = (m + 1)q + 0

m+1 is a natural number, and our remainder is 0, and 0 \leq 0 < q as required.

Thus by induction we have proved this proposition. QED.

----------------

Is this proof sufficient? I think it is, but there are much more things involved here than in most of the other proof by inductions I have done, so I just want to make sure I did not screw anything up. Also, any ideas about other ways to prove this proposition using induction?

Thanks!edit... To be a little more specific about what I am worried about in the proof. In my proof I am using 0 \leq r < q since I believe I can because it is true by our inductive hypothesis, this is correct and OK to do right?

 

[e(ho0n3]

I'm certainly convinced by your proof.

 

[StatusX]

First, it isn't important, but you might have the roles of q and m switched. Usually q would be the quotient and r would be the remainder when dividing m by n, and the condition would be 0<=r<m. But that just amounts to relabelling variables, and doesn't affect your proof.

Second, as far as naming, the proces of picking a quotient and remainder for two given elements is generally called the "division algorithm." It can be asked whether an arbitrary ring (an algebraic structure with multiplication and addition, such as the integers) has a division algorithm. The integers do, and this fact may well be called the "division theorem", although I personally haven't heard that term. Finally, if a ring does have a division algorithm, then it immediately follows that it has a Euclidean algorithm (and so also unique factorization), and the ring is called a "Euclidean domain."

And, yes, your proof looks correct.