Division Algorithm

[twisted_logic89]

Ok, so the division algorithm states that if a,b are natural numbers (and b doesnt equal 0), there exists unique q,r such that a=bq + r
From this, to explain why every natural number is of the form 3k, 3k+1, 3k+2......
choose an a and b. A= any number (or 'n'), b=3, and r=0,1,2 so: 2= 3(0)+2

n=3k+r
3k+0 ---> 3 (when k=1)
3k+1 ---> 4 (when k=2)
3k+2 ---> 5 (when k=3)

do you think this adequately explains why every natural number is of the form 3k, 3k+1, 3k+2? Do you think there is anything I could do to improve upon this answer?

 

[daon]

I will do something specific for this case and show you why it works.

Let n be a natural number. I want to show the uniqueness of the quotient and remainder when the divisor is 3 for any natural number n.

Assume n = 3p+a and n=3q+b with 0<=a,b<3. Goal is to show a=b, and p=q.

Setting 3p+a and 3q+b equal and moving some things around, we have: 3(p-q) = b-a.

Therefore b-a is a multiple of 3.

There are only 9 possibilities for b and a...

a=0, b=0 works
a=0, b=1
a=0, b=2
a=1, b=0
a=1, b=1 works
a=1, b=2
a=2, b=0
a=2, b=1
a=2, b=2 works

Therefore a=b.

If a=b, then 3(p-q)=0, and therefore p=q.

To show every natural number is of the form 3k, 3k+1, 3k+2... use induction.

Cleary, 0 1 and 2 can be shown they are of one of these forms.

Assume up to a fixed n, we can show it is one of these forms.

I'll do one of the cases: let n=3k+2.
Then n+1 = 3k+2+1 = 3(k+1) is now one of these forms.

Now do the other 2.