Def/Division with remainder

From SlugmathWiki

Definition
Proof

Definition of Division of integers with remainder: Suppose that $a,b \in \NN$ , and $b \neq 0$. Then, there exist natural numbers $q,r$, such that:

$a = qb + r$, and
$0 \leq r < b$.

The natural number $r$ is called the remainder, and the natural number $q$ is called the quotient, when $a$ is divided by $b$. Finding such numbers $q$ and $r$ is called (elementary) division with remainder.

A slight variation involves dividing integers with remainder. Suppose that $a,b \in \ZZ$ , and $b \neq 0$. Then, there exist integers $q,r$, such that:

$a = qb + r$, and
$0 \leq \vert r \vert < \vert b \vert$.

Observe that we no longer require $r$ to be positive (though we could, if we wanted to). If the above two statements hold, the natural number $r$ is called a remainder, and the integer $q$ is called a quotient, when $a$ is divided by $b$. Finding such numbers $q$ and $r$ is again called (elementary) division with remainder.

The idea of division with remainder can be generalized to integral domains through the definition of a Euclidean valuation.

Logical Connections

This definition logically relies on the following definitions and statements: Def/Natural number, Def/Integer, State/Every nonempty subset of N has a smallest element

The following statements and definitions logically rely on the material of this page: Def/Euclidean algorithm

To visualize the logical connections between this definition and other items of mathematical knowledge, you can visit any of the following clusters, and click the "Visualize" tab: Clust/Basic number theory

Suppose that $a,b \in \NN$, and $b \neq 0$.

Let $R$ be the set of natural numbers $r$, which satisfy the following property:

There exists $q \in \NN$, such that $a = qb + r$.

First, observe that $a = 0b + a$, and hence $a \in R$. Therefore, $R$ is nonempty. It follows that $R$ has a smallest element. Let $r$ be the smallest element of $R$. Then $a = qb + r$ (since $r \in R$), and $0 \leq r$ (since $r \in \NN$. It remains to prove that $r < b$.

	Suppose that $r \geq b$. Let $r' = r - b$. Then, since $r \geq b$, $r' = r-b \geq 0$. Furthermore, observe that: $$a = qb + r = (q-1+1)b + r = (q+1)b - b + r = (q+1)b + r'.$$ Since $q \in \NN$, $q + 1 \in \NN$. Hence, we find that $r' \in R$. But also $r' = r-b < r$.
	This contradicts the minimality of $r$ in $R$.

Hence $0 \leq r < b$, and $a = qb + r$.

Now, we can generalize to the case when $a,b \in \ZZ$, as follows:

Suppose that $a,b \in \ZZ$, and $b \neq 0$.

We consider two cases, based on the sign of $a$:

$a \geq 0$

When $a \geq 0$, $a \in \NN$. We consider two cases, based on the sign of $b$.

$b > 0$

If $b > 0$, then $a,b \in \NN$, and the result has been proven already.

$b < 0$.

If $b < 0$, then $-b > 0$. Hence $a$ and $-b$ are natural numbers. It follows that there exists $q, r \in \NN$, such that:

$a = q(-b) + r$.
$0 \leq r < -b$.

It follows that:

$a = (-q) b + r$.
$0 \leq \vert r \vert < \vert b \vert$.

Hence we may divide $a$ by $b$ to obtain a quotient $q$ and remainder $r$ for all nonzero $b \in \ZZ$.

$a < 0$

If $a < 0$, then $-a > 0$. We consider two cases again, based on the sign of $b$.

$b < 0$

If $b < 0$, then $-b > 0$. It follows that $-a, -b \in \NN$. Hence there exist $q,r \in \NN$, such that:

$-a = q(-b) + r$.
$0 \leq r < -b$.

It follows that:

$a = (-q) b + (-r)$.
$0 \leq \vert -r \vert < \vert b \vert.

$b > 0$

If $b > 0$, then $-a, b \in \NN$. Hence there exist $q,r \in \NN$, such that:

$-a = q(b) + r$.
$0 \leq r < b$.

It follows that:

$a = (-q) b + (-r)$.
$0 \leq \vert -r \vert < \vert b \vert.

Hence we may divide $a$ by $b$ to obtain a quotient $q$ and remainder $r$ for all nonzero $b \in \ZZ$.

Hence we may divide $a$ by $b$ to obtain a quotient $q$ and remainder $r$ for all $a \in \ZZ$ and nonzero $b \in \ZZ$.

Def/Division with remainder

From SlugmathWiki

Logical Connections

Views

Personal tools

Navigation

Mathematics

Pegagogy

Search

Toolbox