Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Division Algorithm"

(LaTeX,, stub)
 
Line 1: Line 1:
−
For any positive integer <math>a</math> and integer <math>b</math>, there exist unique integers <math>q</math> and <math>r</math> such that <math>b = qa + r</math> and <math>0 \le r < a</math>, with <math>r = 0</math> iff <math>a \mid b</math>.
+
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 $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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Division_Algorithm&oldid=32170"