Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Division Theorem [proof by induction]

  1. Aug 30, 2006 #1
    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 [itex]0 \leq r < q[/itex] and [itex]n = mq + r[/itex]

    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 [itex]0 \leq r < q[/itex] since [itex]0 \leq 0 < q[/itex] and we will also have [itex]n = 0 = 0q + 0 = 0[/itex]. 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 [itex]0 \leq r < q[/itex] and [itex]n = mq + r[/itex]. Then we want to show that the same properties are true for n + 1.

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

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

    Case 2: ([itex]r = q - 1[/itex])
    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 [itex]0 \leq 0 < q[/itex] 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?


    edit... To be a little more specific about what I am worried about in the proof. In my proof I am using [itex]0 \leq r < q[/itex] since I believe I can because it is true by our inductive hypothesis, this is correct and OK to do right?
    Last edited: Aug 30, 2006
  2. jcsd
  3. Aug 30, 2006 #2
    I'm certainly convinced by your proof.
  4. Aug 31, 2006 #3


    User Avatar
    Homework Helper

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook