« first day (209 days earlier)      last day (158 days later) » 

Feeds
Feeds
7:38 AM
 
 
9 hours later…
Wolgwang
Wolgwang
4:28 PM
Prove Euclid's Division Lemma
Euclid Division Lemma- For any given integers $a$ and $b$, there exist unique integers $q$ and $r$ satisfying $a=bq+r$
Proof:
Let $S$ be a set
$$S=\{a-bk\mid k\in \mathbb Z\}$$
Let there be another set $S_p$ such that $S_p\subset S$ and $\forall x\in S_p(x>0)$
By well-ordering principle, it contains a least element. Let it be $r=a-bq$.
 
Wolgwang
Wolgwang
4:44 PM
Let $r>b$
then $r-b=a-b(q+1)$ is positive and is an element of $S_p$ as $a-b(q+1)=a-bk$ where $k=q+1$
$$r-b<r$$
This implies $r-b$ is the least element of $S_p$ which is a contradiction so $r<b$
$\implies 0\leq r <b$
Proving uniqueness of $q,r$
Assuming $r,q$ are not unique and $r',q'$ can also satisfy $a=bQ+R$
$a=bq'+r'\quad 0\leq r'<b'\\a=bq+r\quad 0\leq r<b$
$b(q'-q)=r-r'$
WLOG $r>r'$
$0\geq -r'>b'$
Adding inequalities $b'<r-r'<b$
$b'<b(q'-q)<b$
$q'-q$ must be zero.
$q=q'$ and $r=r'$
 
Wolgwang
Wolgwang
5:24 PM
room topic changed to The Turingers: Number theory for beginners...maybe. [elementary-number-theory]
 

« first day (209 days earlier)      last day (158 days later) »