# Division Theorem [proof by induction]

by mattmns
Tags: division, induction, proof, theorem
 P: 1,123 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?