Division and Bezout Theorem

Mathematics

Division Algorithm

Let $a,b$ be integers with $b>0$.Then there exist unique integers $q$ and $r$,s.t $a=qb+r$,where $0 \le r<b$.

Proof:
Let $r$ be the smallest non-negative integer in set {$a-qb$}

If $r \ge b$,then $r = r'+b$,$r'$ is in {$a-qb$}.

$\because b>0$ $\therefore r'<r$
It conflicts with our hypothesis.
So $0 \le r < b$.That is,exist integers $q$ and $r$ that satisfy $a=qb+r$ where $0 \le r<b$

If there exist $q'$ and $r'$ s.t $a=q'b+r'$
Then we have $r'-r=(q'-q)b$
$\because 0 \le r <b,0 \le r' <b$
$\therefore -b <r'-r<b$
$\therefore -1<q-q'<1$

Because $q-q'$ is an integer,therefore,$q-q'$ must be zero.

$\therefore r=r',q=q'$
$\therefore$There exist unique integers $q$ and $r$ that satisfy $a=qb+r$($0 \le r <b$)

Q.E.D.

Bezout Theorem

There exists integers $x$ and $y$ s.t $ax+by=gcd(a,b)$

Proof:
Let $c$ be the smallest non-negative integer in set {$ax+by$}
Let $d = gcd(a,b)$

Let $c\prime =ax\prime+by\prime$,$c\prime - kc=a(x\prime-kx)+b(y\prime-ky)$.For $\forall k$ that satisfy $c\prime-kc > 0$,$c'-kc \in${$ax+by$}.

When $c\prime-kc=c$,$c\prime=(k+1)c$.
So $c$ can divide every element in{$ax+by$}.
So $c$ must a commom factor of $a$ and $b$.$c \le d$
$\because d|a,d|b$
$\therefore d|ax+by$
$\therefore d|c$
$\therefore d \le c$
$\because c \le d$
$\therefore c=d$

Therefore,exists $ax+by=c=gcd(a,b)$

Q.E.D.