Difference between revisions of "Division Algorithm"
(LaTeX,, stub) |
Darkmage2009 (talk | contribs) |
||
Line 1: | Line 1: | ||
− | For any | + | For any integer <math>a</math> and positive integer <math>b</math>, there exist unique integers <math>q</math> and <math>r</math> such that <math>a = qb + r</math> and <math>0 \leq r < b</math>. |
+ | |||
+ | |||
+ | == Proof == | ||
+ | Existence: Let <math>S=\{a-nb\mid n\in \mathbb{Z}\}.</math> The intersection of the sets <math>S</math> and <math>\mathbb{N}</math> is non-empty and has a positive element (take <math>n=-|a|</math>). By the [[Well Ordering Principle]] , it contains a least element. Let <math>r</math> equal the value of the least element and let <math>q</math> equal the respective value of <math>n</math>. Therefore, <math>r=a-qb\Rightarrow a=qb+r</math>. Now we prove that <math>0\leq r<b</math> by contradiction. Let <math>r\geq b</math>. Then <math>r=a-qb\Rightarrow r-b=a-(q+1)b</math>. However, this leads to a contradiction (<math>r</math> is supposed to be the smallest positive value that can be expressed in the form <math>a-nb</math>, but <math>r-b</math> is smaller, positive, and can also be expressed in this manner). Therefore, <math>0\leq r<b</math>. | ||
+ | |||
+ | Uniqueness: Let <math>a=qb+r=q'b+r'</math>. Then <math>qb+r=q'b+r'\Rightarrow (r-r')=b(q'-q)</math>. Then <math>|r-r'|</math> is a multiple of <math>b</math>. However, since <math>0\leq r<b</math> and <math>0\leq r<b</math>, then <math>0\leq |r-r'|<b</math>. The only multiple of <math>b</math> that <math>|r-r'|</math> can equal is <math>0</math>. Therefore, <math>|r-r'|=0\Rightarrow r=r'</math>. Since <math>b\not= 0</math>, <math>|q'-q|=0\Rightarrow q=q'</math>. | ||
+ | |||
+ | |||
+ | == Divisibility == | ||
+ | If <math>a=qb+r</math> and <math>r=0</math>, then we say <math>b\mid a</math> or "<math>b</math> divides <math>a</math>". Note that every integer divides <math>0</math>. | ||
{{stub}} | {{stub}} |
Latest revision as of 02:25, 22 June 2009
For any integer and positive integer
, there exist unique integers
and
such that
and
.
Proof
Existence: Let The intersection of the sets
and
is non-empty and has a positive element (take
). By the Well Ordering Principle , it contains a least element. Let
equal the value of the least element and let
equal the respective value of
. Therefore,
. Now we prove that
by contradiction. Let
. Then
. However, this leads to a contradiction (
is supposed to be the smallest positive value that can be expressed in the form
, but
is smaller, positive, and can also be expressed in this manner). Therefore,
.
Uniqueness: Let . Then
. Then
is a multiple of
. However, since
and
, then
. The only multiple of
that
can equal is
. Therefore,
. Since
,
.
Divisibility
If and
, then we say
or "
divides
". Note that every integer divides
.
This article is a stub. Help us out by expanding it.