Difference between revisions of "Division Algorithm"

Latest revision as of 01:25, 22 June 2009

For any integer $a$ and positive integer $b$ , there exist unique integers $q$ and $r$ such that $a = qb + r$ and $0 \leq r < b$ .

Proof

Existence: Let $S=\{a-nb\mid n\in \mathbb{Z}\}.$ The intersection of the sets $S$ and $\mathbb{N}$ is non-empty and has a positive element (take $n=-|a|$ ). By the Well Ordering Principle , it contains a least element. Let $r$ equal the value of the least element and let $q$ equal the respective value of $n$ . Therefore, $r=a-qb\Rightarrow a=qb+r$ . Now we prove that $0\leq r<b$ by contradiction. Let $r\geq b$ . Then $r=a-qb\Rightarrow r-b=a-(q+1)b$ . However, this leads to a contradiction ( $r$ is supposed to be the smallest positive value that can be expressed in the form $a-nb$ , but $r-b$ is smaller, positive, and can also be expressed in this manner). Therefore, $0\leq r<b$ .

Uniqueness: Let $a=qb+r=q'b+r'$ . Then $qb+r=q'b+r'\Rightarrow (r-r')=b(q'-q)$ . Then $|r-r'|$ is a multiple of $b$ . However, since $0\leq r<b$ and $0\leq r<b$ , then $0\leq |r-r'|<b$ . The only multiple of $b$ that $|r-r'|$ can equal is $0$ . Therefore, $|r-r'|=0\Rightarrow r=r'$ . Since $b\not= 0$ , $|q'-q|=0\Rightarrow q=q'$ .

Divisibility

If $a=qb+r$ and $r=0$ , then we say $b\mid a$ or " $b$ divides $a$ ". Note that every integer divides $0$ .

This article is a stub. Help us out by expanding it.

@@ Line 1: / Line 1: @@
-For any positive integer a and integer b, there exist unique integers q and r such that b = qa + r and 0 <= r < a, with r = 0 iff a | b.
+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}}

Page

Toolbox

Search

Difference between revisions of "Division Algorithm"

Latest revision as of 01:25, 22 June 2009

Proof

Divisibility