PDA

View Full Version : Well ordering property



Papergel
05-23-2007, 10:35 PM
I need help on this proof:

Let b denote a fixed positive integer. Prove the following statement by induction: For every integer n>= 0, there exists nonnegative integers q and r such that

n = qb + r , 0 <= r < b .

Thank you

daon
05-24-2007, 12:50 AM
The base case is easy, just take q,r=0.

Assume its true for all integers up to a fixed n. Then write n=qb+r for non negative integers q,r and 0 <= r < b.

Then n+1 = qb + (r + 1). Since between any two consecutive natural numbers there are no others, we get that r<b implies r+1 <= b. So either r+1=b or r+1 < b.

The rest should be cake.

korean
09-09-2007, 01:48 AM
its been a while but that looks like the division algorithm theorm to me. look it up in your textbook or search it on the web. other than that i cant really help you much its been too long since i did something like that.