division’s algorithm


let us write for the sake of young mathematicians this important arithmetic fact:

PROPOSITION:

\forall a,b\in{\Bbb{Z}}\ \exists t,r\in{\Bbb{Z}}\ : a=bt+r,\quad 0\le r<|b|

PROOF:

Let a>b>0 be the case and we set

S_{ab}=\{a-bm\ge0\ |\ m\in{\Bbb{Z}}\}

then there exists

\exists r=\min S_{ab}.

If

r=0

then

a=bt.

For the rest of the argument we consider

r>0.

So

r=a-bt,\qquad \exists t\in{\Bbb{Z}}

and a=bt+r.

We are going to establish

0\le r< b.

Suppose

r\ge b

r-b\ge0

0\le r-b<r

0\le (a-bt)-b<r

if

0<a-b(t+1)<r

this contradicts the choice for   r

then

0\le r<b

Now for uniqueness:

suppose

a=bt+r,\qquad 0\le r<b

and

a=bt'+r',\qquad 0\le r'<b

r\ge r'

r-r'\ge 0

but

b(t'-t)=r-r' and

b(t-t')=-r'+r>-r>-b

are  integer multiples of b between

-b and b

then

b(t-t')=0

and

t'-t=0

since b\neq0.

So t=t' and r=r'

\Box

Leave a comment

Filed under math

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s