Division Theorem/Positive Divisor/Positive Dividend/Existence/Proof 3

From ProofWiki
Jump to navigation Jump to search

Theorem

For every pair of integers $a, b$ where $a \ge 0$ and $b > 0$, there exist integers $q, r$ such that $a = q b + r$ and $0 \le r < b$:

$\forall a, b \in \Z, a \ge 0, b > 0: \exists q, r \in \Z: a = q b + r, 0 \le r < b$


Proof

Let $a, b \in \Z$ such that $a \ge 0$ and $b > 0$ be given.

When $a = 0$, the integers $q = r = 0$ satisfy the conditions of the theorem.


Let $a > 0$.

For each $k \in \left[{0 \,.\,.\, a + 1}\right]$, let $r_k = b k$.

(Note that here, as elsewhere in this proof, $\left[{0 \,.\,.\, a + 1}\right]$ denotes an integer interval.)

Then $\left \langle{r_k}\right \rangle_{0 \mathop \le k \mathop \le a + 1}$ is a strictly increasing sequence of positive integers.

It is also the case that:

$a + 1 \in \left[{1 \,.\,.\, b \left({a + 1}\right)}\right]$

So from Strictly Increasing Sequence induces Partition there exists $q \in \left[{0 \,.\,.\, a}\right]$ such that:

$a + 1 \in \left[{r_q + 1 \,.\,.\, r_{q + 1}}\right]$

Let $r = a - b q$.

Then $a = b q + r$.

We have:

\(\displaystyle b q + 1\) \(=\) \(\displaystyle r_q + 1\)
\(\displaystyle \) \(\le\) \(\displaystyle a + 1\)
\(\displaystyle \) \(\le\) \(\displaystyle r_{q + 1}\)
\(\displaystyle \) \(=\) \(\displaystyle b q + b\)

and so:

\(\displaystyle 0\) \(\le\) \(\displaystyle r\)
\(\displaystyle \) \(=\) \(\displaystyle \left({a + 1}\right) - \left({b q + 1}\right)\)
\(\displaystyle \) \(\le\) \(\displaystyle \left({b q + b}\right) - \left({b q + 1}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle b - 1\)
\(\displaystyle \) \(<\) \(\displaystyle b\)

Hence the result.

$\blacksquare$


Sources