avewright/proofwiki-math huggingface dataset:
Theorem: Set of Integers Bounded Below by Integer has Smallest Element

Let $\Z$ be the set of integers.
Let $\le$ be the ordering on the integers.
Let $\O \subset S \subseteq \Z$ such that $S$ is bounded below in $\struct {\Z, \le}$.
Then $S$ has a smallest element.

Proof:
We have that $S$ is bounded below in $\Z$.
So:
: $\exists m \in \Z: \forall s \in S: m \le s$
Hence:
: $\forall s \in S: 0 \le s - m$
Thus:
:$T = \set {s - m: s \in S} \subseteq \N$
The Well-Ordering Principle gives that $T$ has a smallest element, which we can call $b_T \in T$.
Hence:
:$\paren {\forall s \in S: b_T \le s - m} \land \paren {\exists b_S \in S: b_T = b_S - m}$
So:
{{begin-eqn}}
{{eqn | o = 
      | r = s \in S: b_S - m \le s - m
      | c = 
}}
{{eqn | o = \leadsto
      | r = \forall s \in S: b_S \le s
      | c = Cancellability of elements of $\Z$
}}
{{eqn | o = \leadsto
      | r = b_S \in S \land \paren {\forall s \in S: b_S \le s}
      | c = {{Defof|Smallest Element}}
}}
{{end-eqn}}
So $b_S$ is the smallest element of $S$.
{{Qed}}
Theorem: Set of Integers Bounded Above by Integer has Greatest Element

Let $\Z$ be the set of integers.
Let $\le$ be the ordering on the integers.
Let $\O \subset S \subseteq \Z$ such that $S$ is bounded above in $\struct {\Z, \le}$.
Then $S$ has a greatest element.

Proof:
$S$ is bounded above, so $\exists M \in \Z: \forall s \in S: s \le M$.
Hence $\forall s \in S: 0 \le M - s$.
Thus the set $T = \set {M - s: s \in S} \subseteq \N$.
The Well-Ordering Principle gives that $T$ has a smallest element, which we can call $b_T \in T$.
Hence:
:$\paren {\forall s \in S: b_T \le M - s} \land \paren {\exists g_S \in S: b_T = M - g_S}$
So:
{{begin-eqn}}
{{eqn | o = 
      | r = \forall s \in S: M - g_S \le M - s
      | c = 
}}
{{eqn | o = \leadsto
      | r = \forall s \in S: -g_S \le -s
      | c = Cancellability of elements of $\Z$
}}
{{eqn | o = \leadsto
      | r = \forall s \in S: g_S \ge s
      | c = 
}}
{{eqn | o = \leadsto
      | r = g_S \in S \land \paren {\forall s \in S: g_S \ge s}
      | c = which is how the greatest element is defined.
}}
{{end-eqn}}
So $g_S$ is the greatest element of $S$.
{{qed}}
Theorem: Set of Integers Bounded Above by Integer has Greatest Element

Let $\Z$ be the set of integers.
Let $\le$ be the ordering on the integers.
Let $\O \subset S \subseteq \Z$ such that $S$ is bounded above in $\struct {\Z, \le}$.
Then $S$ has a greatest element.

Proof:
Since $S$ is bounded above, $\exists M \in \Z: \forall s \in S: s \le M$.
Hence we can define the set $S' = \set {-s: s \in S}$.
$S'$ is bounded below by $-M$.
So from Set of Integers Bounded Below by Integer has Smallest Element, $S'$ has a smallest element, $-g_S$, say, where $\forall s \in S: -g_S \le -s$.
Therefore $g_S \in S$ (by definition of $S'$) and $\forall s \in S: s \le g_S$.
So $g_S$ is the greatest element of $S$.
{{qed}}
Theorem: Principle of Least Counterexample

Let $\map P n$ be a condition on $n \in \set {x \in \Z: x \ge m \in \Z}$.
Suppose that:
:$\neg \paren {\forall n \ge m: \map P n}$
(That is, not all $n \ge m$ satisfy $\map P n$.)
Then there exists a '''least counterexample''', that is a smallest integral value of $n$ for which $\neg \map P n$.

Proof:
Let $S = \set {n \in \Z: n \ge m \in \Z: \neg \map P n}$.
That is, $S$ is the set of all elements of $\Z$ not less than $m$ for which the condition is false.
Since:
:$\neg \paren {\forall n \ge m: \map P n}$
it follows that:
:$S \ne \O$
Also, $S \subseteq \Z$ and is bounded below (by $m$).
Therefore $S$ has a smallest element, which proves the result.
Theorem: Absolute Value is Bounded Below by Zero

Let $x \in \R$ be a real number.
Then the absolute value $\size x$ of $x$ is bounded below by $0$.

Proof:
Let $x \ge 0$.
Then $\size x = x \ge 0$.
Let $x < 0$.
Then $\size x = -x > 0$.
The result follows.
{{qed}}
Theorem: Division Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size b$

Proof:
From the equation $0_F = 0_F \circ d + 0_F$, the theorem is true for the trivial case $f = 0_F$.
So, if there is a counterexample to be found, it will have a degree.
{{AimForCont}} there exists at least one counterexample.
By a version of the Well-Ordering Principle, we can assign a number $m$ to the lowest degree possessed by any counterexample.
So, let $f$ denote a counterexample which has that minimum degree $m$.
If $m < n$, the equation $f = 0_F \circ d + f$ would show that $f$ was not a counterexample.
Therefore $m \ge n$.
Suppose $d \divides f$ in $F \sqbrk X$.
Then:
:$\exists q \in F \sqbrk X: f = q \circ d + 0_F$
and $f$ would not be a counterexample.
So $d \nmid f$ in $F \sqbrk X$.
So, suppose that:
{{begin-eqn}}
{{eqn | l = f
      | r = \sum_{k \mathop = 0}^m {a_k \circ X^k}
}}
{{eqn | l = d
      | r = \sum_{k \mathop = 0}^n {b_k \circ X^k}
}}
{{eqn | l = m
      | o = \ge
      | r = n
}}
{{end-eqn}}
We can create the polynomial $\paren {a_m \circ b_n^{-1} \circ X^{m - n} } \circ d$ which has the same degree and leading coefficient as $f$.
Thus $f_1 = f - \paren {a_m \circ b_n^{-1} \circ X^{m - n} } \circ d$ is a polynomial of degree less than $m$.
Since $d \nmid f$, $f_1$ is a non-zero polynomial.
There is no counterexample of degree less than $m$.
Therefore:
:$f_1 = q_1 \circ d + r$
for some $q_1, r \in F \sqbrk X$, where either:
:$r = 0_F$
or:
:$r$ is non-zero with degree strictly less than $n$.
Hence:
{{begin-eqn}}
{{eqn | l = f
      | r = f_1 + \paren {a_m \circ b_n^{-1} \circ X^{m - n} } \circ d
      | c = 
}}
{{eqn | r = \paren {q_1 + a_m \circ b_n^{-1} \circ X^{m - n} } \circ d + r
      | c = 
}}
{{end-eqn}}
Thus $f$ is not a counterexample.
From this contradiction follows the result.
{{qed}}
Theorem: Division Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size b$

Proof:
Suppose $\map \deg f < \map \deg d$.
Then we take $\map q X = 0$ and $\map r X = \map f X$ and the result holds.
Otherwise, $\map \deg f \ge \map \deg d$.
Let:
:$\map f X = a_0 + a_1 X + a_2 x^2 + \cdots + a_m X^m$
:$\map d X = b_0 + b_1 X + b_2 x^2 + \cdots + b_n X^n$
We can subtract from $f$ a suitable multiple of $d$ so as to eliminate the highest term in $f$:
:$\map f X - \map d X \cdot \dfrac {a_m} {b_n} x^{m - n} = \map p X$
where $\map p X$ is some polynomial whose degree is less than that of $f$.
If $\map p X$ still has degree higher than that of $d$, we do the same thing again.
Eventually we reach:
:$\map f X - \map d X \cdot \paren {\dfrac {a_m} {b_n} x^{m - n} + \dotsb} = \map r X$
where either $r = 0_F$ or $r$ has degree that is less than $n$.
This approach can be formalised using the Principle of Complete Induction.
{{qed}}
Theorem: Division Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size b$

Proof:
Proof by induction:
For all $n \in \N_{> 0}$, let $\map P n$ be the proposition:
:$\forall f \in F \sqbrk X: \exists q, r \in F \sqbrk X: f = q \circ d + r$ provided that $\map \deg f < n$
=== Basis for the Induction ===
$\map P 0$ is the statement that $q$ and $r$ exist when $f = 0$.
This is shown trivially to be true by taking $q = r = 0$.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 0$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:$\forall f \in F \sqbrk X: \exists q, r \in F \sqbrk X: f = q \circ d + r$ provided that $\map \deg f < k$
Then we need to show:
:$\forall f \in F \sqbrk X: \exists q, r \in F \sqbrk X: f = q \circ d + r$ provided that $\map \deg f < k + 1$
=== Induction Step ===
This is our induction step:
Let $f$ be such that $\map \deg f = n$.
Let:
:$f = a_0 + a_1 \circ x + a_2 \circ x^2 + \cdots + a_n \circ x^n$ where $a_n \ne 0$
Let:
:$d = b_0 + b_1 \circ x + b_2 \circ x^2 + \cdots + b_j \circ x^j$ where $b_j \ne 0$
If $n < l$ then take $q = 0, r = f$.
If $n \ge l$, consider:
:$c := f - a_n b_j^{-1} x^{n - j} d$
This has been carefully arranged so that the coefficient of $x^n$ in $c$ is zero.
Thus $\map \deg c < n$.
Therefore, by the induction hypothesis:
:$c = d q_0 + r$
where $\map \deg r < \map \deg d$.
Therefore:
{{begin-eqn}}
{{eqn | l = f
      | r = d \paren {q_0 + a_n b_j^{-1} x^{n - j} } + r
      | c = 
}}
{{eqn | r = d q + r
      | c = where $\map \deg r < \map \deg d$ and $q = q_0 + a_n b_j^{-1} x^{n - j}$
}}
{{end-eqn}}
Thus the existence of $q$ and $r$ have been established.
As for uniqueness, assume:
:$d q + r = d q' + r'$
with $\map \deg r < \map \deg d, \map \deg {r'} < \map \deg d$
Then:
:$d \paren {q - q'} = r' - r$
By Degree of Sum of Polynomials:
:$\map \deg {r' - r} \le \max \set {\map \deg {r'}, \map \deg r} < \map \deg d$
and by Degree of Product of Polynomials over Integral Domain:
:$\map \deg {d \paren {q - q'} } = \map \deg d + \map \deg {q - q'}$
That is:
:$\map \deg d < \map \deg d + \map \deg {q - q'}$
and the only way for that to happen is for:
:$\map \deg {q - q'} = -\infty$
that is, for $q - q'$ to be the null polynomial.
That is, $q - q' = 0_F$ and by a similar argument $r' - r = 0_F$, demonstrating the uniqueness of $q$ and $r$.
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall f \in F \sqbrk X: \exists q, r \in F \sqbrk X: f = q \circ d + r$ such that either:
::$(1): \quad r = 0_F$
:or:
::$(2): \quad r \ne 0_F$ and $r$ has degree that is less than $n$.
{{qed}}
Theorem: Division Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size b$

Proof:
From Division Theorem: Positive Divisor: Positive Dividend: Existence:
:$\forall a, b \in \Z, a \ge 0, b > 0: \exists q, r \in \Z: a = q b + r, 0 \le r < b$
That is, the result holds for positive $a$.
{{qed|lemma}}
It remains to be shown that the statement holds for $a < 0$.
From Division Theorem: Positive Divisor: Positive Dividend:
:$\exists \tilde q, \tilde r \in \Z: \size a = \tilde q b + \tilde r, 0 \le \tilde r < b$
where $\size a$ denotes the absolute value of $a$: by definition $\size a \ge 0$.
As $a < 0$ it follows by definition of absolute value that $\size a = -a$.
This gives:
{{begin-eqn}}
{{eqn | l = a
      | r = -\size a
      | c = 
}}
{{eqn | r = -\paren {\tilde q b + \tilde r}
      | c = 
}}
{{eqn | r = b \paren {-\tilde q} + \paren {-\tilde r}
      | c = 
}}
{{end-eqn}}
Let $\tilde r = 0$.
Then:
:$q = -\tilde q, r = \tilde r = 0$
which gives:
:$a = q b + r, 0 \le r < b$
as required.
Otherwise:
:$0 < \tilde r < b \implies 0 < b - \tilde r < b$
which suggests a rearrangement of the expression for $a$ above:
{{begin-eqn}}
{{eqn | l = a
      | r = b \paren {-\tilde q} + \paren {-\tilde r}
      | c = 
}}
{{eqn | r = b \paren {-\tilde q} - b + b - \tilde r
      | c = 
}}
{{eqn | r = b \paren {-1 - \tilde q} + \paren {b - \tilde r}
      | c = 
}}
{{end-eqn}}
Taking:
:$q = \paren {-1 - \tilde q}$
and:
:$r = \paren {b - \tilde r}$
the required result follows.
Uniqueness of $q$ and $r$ follow from the Uniqueness of $\tilde q$ and $\tilde r$.
{{qed}}
Theorem: Division Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size b$

Proof:
Let:
: $q = \floor {\dfrac a b}, t = \dfrac a b - \floor {\dfrac a b}$
where $\floor {\, \cdot \,}$ denotes the floor function.
Thus $q \in \Z$ and $t \in \hointr 0 1$.
So:
:$\dfrac a b = q + t$
and so:
:$(1): \quad a = q b + r$
where $r = t d$.
Since $a, q, b \in \Z$, it follows from $(1)$ that:
:$r = a - q b$
and so $r \in \Z$ also.
Since $0 \le t < 1$ and $b > 0$, it follows that:
:$0 \le t b < b$
that is:
:$0 \le r < b$
{{qed}}
Theorem: Division Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size b$

Proof:
Let there exist $q \in Z$ such that $a - b q = 0$.
Then $a = b q$ as required, with $r = 0$.
Otherwise, let $S$ be defined as the set of all positive integers of the form $a - z b$ where $z$ is an integer:
:$S = \set {x \in \Z_{\ge 0}: \exists z \in \Z: x = a - z b}$
Setting $z = 0$ it is seen that $a \in S$, so $S \ne \O$.
From Set of Integers Bounded Below by Integer has Smallest Element, $S$ has a smallest element.
Let $r$ be the smallest element of $S$.
Let $r = a - b q$.
As there does not exist $q \in Z$ such that $a - b q = 0$:
:$r > 0$
Suppose $r = b$.
Then $a = b \paren {q + 1}$ and it has already been declared that there does not exist such a $q + 1 \in Z$.
Suppose $r > b$.
Then $x = a - b \paren {q + 1} \in S$ such that $x < r$, which contradicts the assumption that $r$ is the smallest element of $S$.
Hence the result.
{{qed}}
Theorem: Division Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size b$

Proof:
Let $a, b \in \Z$ such that $a \ge 0$ and $b > 0$ be given.
Let $S$ be defined as the set of all positive integers of the form $a - z b$ where $z$ is an integer:
:$S = \set {x \in \Z_{\ge 0}: \exists z \in \Z: x = a - z b}$
By setting $z = 0$ we have that $a \in S$.
Thus $S \ne \O$.
We have that $S$ is bounded below by $0$.
From Set of Integers Bounded Below by Integer has Smallest Element it follows that $S$ has a smallest element $r$.
Thus:
:$\exists q \in \Z: a - q b = r$
and so:
:$a = q b + r$
So we have proved the existence of $q$ and $r$ such that $a = q b + r$.
It remains to be shown that $0 \le r < b$.
We have that $r \in S$ which is bounded below by $0$.
Therefore $0 \le r$.
{{AimForCont}} $b \le r$.
So:
{{begin-eqn}}
{{eqn | l = b
      | o = \le
      | r = r
      | c = 
}}
{{eqn | o = <
      | r = r + b
      | c = as $b > 0$
}}
{{eqn | ll= \leadsto
      | l = 0
      | o = \le
      | r = r - b
      | c = 
}}
{{eqn | o = <
      | r = r
      | c = subtracting $b$ throughout
}}
{{end-eqn}}
But then:
{{begin-eqn}}
{{eqn | l = a
      | r = q b + r
      | c = from above
}}
{{eqn | ll= \leadsto
      | l = r - b
      | r = \paren {a - q b} - b
      | c = 
}}
{{eqn | r = a - b \paren {q + 1}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = r - b
      | o = \in
      | r = S
      | c = as $r - b$ is of the correct form
}}
{{end-eqn}}
But $r - b < r$ contradicts the choice of $r$ as the least element of $S$.
Hence $r < b$ as required.
Thus the existence of $q$ and $r$ satisfying $a = q b + r, 0 \le r < b$ has been demonstrated.
{{qed}}
Theorem: Division Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size b$

Proof:
Let $a = 0$.
It is immediately apparent that $q = r = 0$ is the only possible solution with $0 \le r < b$.
{{qed|lemma}}
Let $a > 0$ and $b = 1$.
Then from the condition $0 \le r < b$ it follows that $r = 0$ and hence $q = a$.
{{qed|lemma}}
Let $a > 0$ and $b > 1$.
By the Basis Representation Theorem, $a$ has a unique representation to the base $b$:
{{begin-eqn}}
{{eqn | l = a
      | r = \sum_{k \mathop = 0}^s r_k b^k
      | c = 
}}
{{eqn | r = b \sum_{k \mathop = 0}^{s - 1} r_k b^{k - 1} + r_0
      | c = 
}}
{{eqn | r = b q + r
      | c = where $0 \le r = r_0 < b$
}}
{{end-eqn}}
{{qed}}
Theorem: Division Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size 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 \closedint 0 {a + 1}$, let $r_k = b k$.
(Note that here, as elsewhere in this proof, $\closedint 0 {a + 1}$ denotes an integer interval.)
Then $\sequence {r_k}_{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 \closedint 1 {\map b {a + 1} }$
So from Strictly Increasing Sequence induces Partition there exists $q \in \closedint 0 a$ such that:
:$a + 1 \in \closedint {r_q + 1} {r_{q + 1} }$
Let $r = a - b q$.
Then $a = b q + r$.
We have:
{{begin-eqn}}
{{eqn | l = b q + 1
      | r = r_q + 1
      | c = 
}}
{{eqn | o = \le
      | r = a + 1
      | c = 
}}
{{eqn | o = \le
      | r = r_{q + 1}
      | c = 
}}
{{eqn | r = b q + b
      | c = 
}}
{{end-eqn}}
and so:
{{begin-eqn}}
{{eqn | l = 0
      | o = \le
      | r = r
      | c = 
}}
{{eqn | r = \paren {a + 1} - \paren {b q + 1}
      | c = 
}}
{{eqn | o = \le
      | r = \paren {b q + b} - \paren {b q + 1}
      | c = 
}}
{{eqn | r = b - 1
      | c = 
}}
{{eqn | o = <
      | r = b
      | c = 
}}
{{end-eqn}}
Hence the result.
{{qed}}
Theorem: Division Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size b$

Proof:
Suppose $q_1, r_1$ and $q_2, r_2$ are two pairs of $q, r$ that satisfy $a = q b + r, 0 \le r < b$.
That is:
{{begin-eqn}}
{{eqn | l = a
      | r = q_1 b + r_1, 0 \le r_1 < b
      | c = 
}}
{{eqn | l = a
      | r = q_2 b + r_2, 0 \le r_2 < b
      | c = 
}}
{{end-eqn}}
This gives:
:$0 = b \paren {q_1 - q_2} + \paren {r_1 - r_2}$
{{AimForCont}} that $q_1 \ne q_2$.
{{WLOG}}, suppose that $q_1 > q_2$.
Then:
{{begin-eqn}}
{{eqn | l = q_1 - q_2
      | o = \ge
      | r = 1
      | c = 
}}
{{eqn | ll= \leadsto
      | l = r_2 - r_1
      | r = b \paren {q_1 - q_2}
      | c = 
}}
{{eqn | o = \ge
      | r = b \times 1
      | c = as $b > 0$
}}
{{eqn | r = b
      | c = 
}}
{{eqn | ll= \leadsto
      | l = r_2
      | o = \ge
      | r = r_1 + b
      | c = 
}}
{{eqn | o = \ge
      | r = b
      | c = 
}}
{{end-eqn}}
This contradicts the assumption that $r_2 < b$.
A similar contradiction follows from the assumption that $q_1 < q_2$.
Therefore $q_1 = q_2$ and so $r_1 = r_2$.
Thus it follows that $q$ and $r$ are unique.
{{qed}}
Theorem: Division Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size b$

Proof:
It is given by Division Theorem: Positive Divisor: Positive Dividend: Existence that such $q$ and $r$ exist.
Let $a = 0$.
It is immediately apparent that $q = r = 0$ is the only possible solution with $0 \le r < b$.
{{qed|lemma}}
Let $a > 0$ and $b = 1$.
Then from the condition $0 \le r < b$ it follows that $r = 0$.
Hence $r = 0, q = a$ is the only possible solution.
{{qed|lemma}}
Let $a > 0$ and $b > 1$.
By the Basis Representation Theorem, $a$ has a unique representation to the base $b$:
{{begin-eqn}}
{{eqn | l = a
      | r = \sum_{k \mathop = 0}^s r_k b^k
      | c = 
}}
{{eqn | r = b \sum_{k \mathop = 0}^{s - 1} r_k b^{k - 1} + r_0
      | c = 
}}
{{eqn | r = b q + r
      | c = where $0 \le r = r_0 < b$
}}
{{end-eqn}}
Suppose a second pair $q', r'$ were to exist.
Then there would be a representation for $q'$ to the base $b$:
:$\displaystyle q' = \sum_{k \mathop = 0}^t u_k b^k$
so that:
{{begin-eqn}}
{{eqn | l = a
      | r = b q' + r'
      | c = $0 \le r < b$
}}
{{eqn | r = \sum_{k \mathop = 0}^t u_k b^{k + 1} + r'
      | c = 
}}
{{end-eqn}}
But there already exists a representation of $a$ to the base $b$:
:$\displaystyle a = \sum_{k \mathop = 0}^s r_k b^k$
By the Basis Representation Theorem, such a representation is unique.
So:
{{begin-eqn}}
{{eqn | l = t
      | r = s - 1
}}
{{eqn | l = u_k
      | r = r_{k + 1}
}}
{{eqn | l = r'
      | r = a_0
}}
{{eqn | r = r
}}
{{end-eqn}}
and hence $q' = q$.
{{qed}}
Theorem: Division Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size b$

Proof:
It is given by Division Theorem: Positive Divisor: Existence that such $q$ and $r$ exist.
{{:Division Theorem/Positive Divisor/Positive Dividend/Uniqueness/Proof 1}}
Theorem: Division Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size b$

Proof:
It is given by Division Theorem: Positive Divisor: Existence that such $q$ and $r$ exist.
Let $a = q b + r$ where $q, r \in \Z$ and $0 \le r < b$.
Thus:
:$\dfrac a b = q + \dfrac r b$
and:
:$0 \le \dfrac r b \le \dfrac {b - 1} b < 1$
So:
:$q = \floor {\dfrac a b}$
and so:
:$r = a - b \floor {\dfrac a b}$
Thus, given $a$ and $b$, the numbers $q$ and $r$ are unique determined.
{{qed}}
Theorem: Division Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size b$

Proof:
It is given by Division Theorem: Positive Divisor: Existence that such $q$ and $r$ exist.
Suppose that:
:$a = b q_1 + r_1 = b q_2 + r_2$
where both $0 \le r_1 < b$ and $0 \le r_2 < b$.
{{WLOG}}, suppose $r_1 \ge r_2$.
Then:
:$r_1 - r_2 = b \paren {q_2 - q_1}$
That is:
:$b \divides \paren {r_2 - r_1}$
where $\divides$ denotes divisibility.
But:
:$r_1 - r_2 < b$
while from Absolute Value of Integer is not less than Divisors: Corollary:
:$r_1 - r_2 \ge b$
unless from Integer Divides Zero $r_1 - r_2 = 0$.
So $r_1 = r_2$ and it follows directly that $q_1 = q_2$.
{{qed}}
Theorem: Division Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \size b$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \size b$

Proof:
From Division Theorem: Positive Divisor:
:$\forall a, b \in \Z, b > 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < b$
That is, the result holds for positive $b$.
{{qed|lemma}}
It remains to show that the result also holds for negative values of $b$.
Let $b < 0$.
Consider:
:$\size b = -b > 0$
where $\size b$ denotes the absolute value of $b$: by definition $\size b > 0$.
From Division Theorem: Positive Divisor, we have the existence of $\tilde q, \tilde r \in \Z$ such that:
:$a = \tilde q \size b + \tilde r, 0 \le \tilde r < \size b$
Since $\size b = -b$:
:$a = \tilde q \paren {-b} + \paren {\tilde r} = \paren {-\tilde q} b + \tilde r$
Taking:
:$q = -\tilde q, r = \tilde r$
the existence has been proved of integers $q$ and $r$ that satisfy the requirements.
The proof that they are unique is the same as that for the proof for positive $b$, but with $\size b$ replacing $b$.
{{qed}}