Prove the division theorem.

Question

I need the proof of the division theorem for positive integers using induction.

Answer 1

The induction hypothesis says: k = bq + r for positive integers, q,b,and r AND 0 <= r < b

Prove: k+1 = bQ + R for integers Q and R, possibly different from q and r, and 0 <= R < b

Proof:

k = bq + r and 0 <= r < b is GIVEN by induction hypothesis

k+1 = bq + r + 1 <---- adds 1 to both sides; please label this equation ALPHA

Since 0 <= r < b is given, then 0 <=r <= b-1 MUST follow, since they are all integers.

In that case, 0 <= (r+1) < b and the statement still holds for the same choice of q, but

with valid remainder r+1.

Note that If by chance, r = b-1, then r+1 = b and the equation ALPHA becomes:

k+1 = bq + b = b(q+1) + 0

so the statement hold with remainder zero, which is valid.

In this case, k+1 divides EVENLY by b with quotient q+1 and remainder 0.

Ex. 43/5 = 8 r 3

44/5 =8 r 4

45/5 = 9 r 0

If the statement holds for k, then it holds for k+1, and the inductive proof is complete.