nyuuzyou/wikis huggingface dataset:
Division Ring Norm is Continuous on Induced Metric Space

== Theorem ==
Let $\struct {R, \norm {\,\cdot\,}}$ be a normed division ring.
Let $d$ be the metric induced by the norm $\norm {\,\cdot\,}$.
The mapping $\norm {\,\cdot\,} : \struct {R, d} \to \R$ is continuous.
== Proof ==
Let $x_0 \in R$.
Let $\epsilon \in \R_{>0}$. 
Let $x \in R: \norm {x - x_0} < \epsilon$.
Then:
By the definition of metric induced by a norm and the definition of a continuous mapping, $\norm {\,\cdot\,}$ is continuous.
Category:Normed Division Rings
Category:Norm Theory
Division Ring has No Proper Zero Divisors

== Theorem ==
Let $\struct {R, +, \circ}$ be a division ring.
Then $\struct {R, +, \circ}$ has no proper zero divisors.
== Proof ==
Let $\struct {R, +, \circ}$ be a division ring whose zero is $0_R$ and whose unity is $1_R$.
By definition of division ring, every element $x$ of $R^* = R \setminus \set {0_R}$ has an element $y$ such that:
:$y \circ x = x \circ y = 1_R$
That is, by definition, every element of $R^*$ is a unit of $R$.
The result follows from Unit of Ring is not Zero Divisor.
== Sources ==
* : Chapter $\text {IV}$: Rings and Fields: $23$. The Field of Rational Numbers
Category:Division Rings
Division Ring is Vector Space over Prime Subfield

== Theorem ==
Let $\struct {K, +, \times}$ be a division ring.
Let $\struct {S, +, \times}$ be the prime subfield of $K$
Then $\struct {K, +, \times_S}_S$ is an $S$-vector space, where $\times_S$ is the restriction of $\times$ to $S \times K$.
== Proof ==
Because $K$ is a division ring, it satisfies the vector space axioms for addition, in particular it is an abelian group. The distribuitivty and associativity of multiplication follow from the rules for multiplciation in any ring. Also, any prime field contains the multiplicative identity.
== Sources ==
* : Chapter $\text {V}$: Vector Spaces: $\S 26$. Vector Spaces and Modules: Example $26.2$
Category:Division Rings
Category:Subfields
Category:Linear Algebra
Division Subring Test

== Theorem ==
Let $\struct {K, +, \circ}$ be a division ring, and let $L$ be a subset of $K$.
Then $\struct {L, +, \circ}$ is a division subring of $\struct {K, +, \circ}$ these all hold:
:$(1) \quad L^* \ne \O$
:$(2) \quad \forall x, y \in L: x + \paren {-y} \in L$
:$(3) \quad \forall x, y \in L: x \circ y \in L$
:$(4) \quad x \in L^* \implies x^{-1} \in L^*$
== Proof ==
=== Necessary Condition ===
Suppose $\struct {L, +, \circ}$ is a division subring of $\struct {K, +, \circ}$.
The conditions $(1)$ to $(3)$ hold by virtue of the Subring Test.
Then $(4)$ also holds by the definition of a division ring:
:$\forall x \in L^*: \exists ! x^{-1} \in L^*: x^{-1} \circ x = x \circ x^{-1} = 1_L$
=== Sufficient Condition ===
Suppose the conditions $(1)$ to $(4)$ hold.
By $(1)$ to $(3)$, it follows from Subring Test that $\struct {L, +, \circ}$ is a subring of $\struct {K, +, \circ}$.
By $(4)$, every element of $L^*$ has a product inverse.
Thus, from the Two-Step Subgroup Test, $\struct {L^*, \circ}$ is a group.
Therefore, $\struct {L, +, \circ}$ is a ring in which every element has a product inverse, which makes $\struct {L, +, \circ}$ a division ring.
Category:Subrings
Division Subring of Normed Division Ring

== Theorem ==
Let $\struct {R, \norm {\, \cdot \,} }$ be a normed division ring.
Let $S$ be a division subring of $R$.
Then:
:$\struct {S, \norm {\, \cdot \,}_S}$ is a normed division subring of $\struct {R, \norm {\, \cdot \,} }$
where $\norm {\, \cdot \,}_S$ is the norm $\norm {\,\cdot\,}$ restricted to $S$.
== Proof ==
=== ===
=== ===
=== ===
Category:Division Rings
Category:Norm Theory
Division Theorem

== 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$
In the above equation:
:$a$ is the dividend
:$b$ is the divisor
:$q$ is the quotient
:$r$ is the remainder.
=== Half Remainder Version ===
== Proof 1 ==
== Proof 2 ==
== Informal Proof ==
== Also known as ==
== Also see ==
* Definition:Integer Division
== Sources ==
* : Appendix: Elementary set and number theory
* : $\S 2.3$: Some properties of subrings and ideals
* : $\S 8.28$
* 
* 
* 
Category:Division Theorem
Category:Named Theorems
Category:Divisors
Division Theorem/Also known as

== Division Theorem: Also known as == 
The Division Theorem is otherwise known as the Quotient Theorem, or (more specifically) the Quotient-Remainder Theorem (as there are several other "quotient theorems" around).
Some sources call this the Division Algorithm but it is preferable not to offer up a possible source of confusion between this and the Euclidean Algorithm to which it is closely related.
It is also known by some as Euclid's Division Lemma, and by others as the Euclidean Division Property.
== Sources ==
* : Appendix: Elementary set and number theory
* : $\S 2.3$: Some properties of subrings and ideals
* 
* 
Category:Division Theorem
Division Theorem/Half Remainder Version

== 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 $-\dfrac {\size b} 2 \le r < \dfrac {\size b} 2$:
:$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, -\dfrac {\size b} 2 \le r < \dfrac {\size b} 2$
In the above equation:
:$a$ is the dividend
:$b$ is the divisor
:$q$ is the quotient
:$r$ is the remainder.
== Proof ==
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.1$ The Division Algorithm: Problems $2.1$: $6$
Category:Division Theorem
Division Theorem/Positive Divisor

== Theorem ==
<onlyinclude>
For every pair of integers $a, b$ where $b > 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < b$:
:$\forall a, b \in \Z, b > 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < b$
<onlyinclude>
In the above equation:
:$a$ is the dividend
:$b$ is the divisor
:$q$ is the quotient
:$r$ is the principal remainder, or, more usually, just the remainder.
== Proof ==
This result can be split into two parts:
=== Proof of Existence ===
=== Proof of Uniqueness ===
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.1$ The Division Algorithm: Theorem $2 \text{-} 1$ (Division Algorithm)
* : $1$ Divisibility: $1.1$ The Euclidean algorithm and unique factorization: Theorem $1.1$
* 
Category:Division Theorem
Division Theorem/Positive Divisor/Existence

== Theorem ==
For every pair of integers $a, b$ where $b > 0$, there exist integers $q, r$ such that $a = q b + r$ and $0 \le r < b$:
:$\forall a, b \in \Z, b > 0: \exists q, r \in \Z: a = q b + r, 0 \le r < b$
In the above equation:
* $a$ is the dividend
* $b$ is the divisor
* $q$ is the quotient
* $r$ is the principal remainder, or, more usually, just the remainder.
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Sources ==
* : $\S 0.1$. Arithmetic: Theorem $2$
Category:Division Theorem
Division Theorem/Positive Divisor/Existence/Proof 1

== Theorem ==
== 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$.
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:
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:
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$.
== Sources ==
* : Chapter $\text {IV}$: Rings and Fields: $24$. The Division Algorithm: Theorem $24.1$
* : $\text {2-1}$ Euclid's Division Lemma: Theorem $\text {2-1}$
Category:Division Theorem
Division Theorem/Positive Divisor/Existence/Proof 2

== Theorem ==
For every pair of integers $a, b$ where $b > 0$, there exist integers $q, r$ such that $a = q b + r$ and $0 \le r < b$:
:$\forall a, b \in \Z, b > 0: \exists q, r \in \Z: a = q b + r, 0 \le r < 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$
== Sources ==
* : $\S 11.1$: The division algorithm
* : Chapter $2$: Integers and natural numbers: $\S 2.2$: Divisibility and factorization in $\mathbf Z$
Category:Division Theorem
Division Theorem/Positive Divisor/Existence/Proof 3

== Theorem ==
For every pair of integers $a, b$ where $b > 0$, there exist integers $q, r$ such that $a = q b + r$ and $0 \le r < b$:
:$\forall a, b \in \Z, b > 0: \exists q, r \in \Z: a = q b + r, 0 \le r < 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.
== Sources ==
* : Chapter $3$: The Integers: $\S 10$. Divisibility: Theorem $18$
* : $\text {2-1}$ Euclid's Division Lemma: Exercise $3$
* : Chapter $2$: Divisibility Theory in the Integers: $2.1$ The Division Algorithm: Theorem $2 \text{-} 1$ (Division Algorithm)
* : Chapter $2$: Integers and natural numbers: $\S 2.2$: Divisibility and factorization in $\mathbf Z$
Category:Division Theorem
Division Theorem/Positive Divisor/Positive Dividend

== Theorem ==
<onlyinclude>
For every pair of integers $a, b$ where $a \ge 0$ and $b > 0$, there exist unique 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$
<onlyinclude>
In the above equation:
:$a$ is the dividend
:$b$ is the divisor
:$q$ is the quotient
:$r$ is the principal remainder, or, more usually, just the remainder.
== Proof ==
This result can be split into two parts:
=== Proof of Existence ===
=== Proof of Uniqueness ===
Category:Division Theorem
Division Theorem/Positive Divisor/Positive Dividend/Existence

== 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 1 ==
== Proof 2 ==
== Proof 3 ==
Category:Division Theorem
Division Theorem/Positive Divisor/Positive Dividend/Existence/Proof 1

== Theorem ==
== 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$.
 $b \le r$.
So:
But then:
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.
== Sources ==
* : Chapter $1$: Properties of the Natural Numbers: $\S 21$
* : Appendix $1$: Some Results from the Elementary Theory of Numbers: Theorem $6$
* : $\text{A}.1$: Number theory: Theorem $\text{A}.1$
Category:Division Theorem
Division Theorem/Positive Divisor/Positive Dividend/Existence/Proof 2

== Theorem ==
== Proof ==
Let $a = 0$.
It is immediately apparent that $q = r = 0$ is the only possible solution with $0 \le r < b$.
Let $a > 0$ and $b = 1$.
Then from the condition $0 \le r < b$ it follows that $r = 0$ and hence $q = a$.
Let $a > 0$ and $b > 1$.
By the Basis Representation Theorem, $a$ has a unique representation to the base $b$:
== Sources ==
* : $\text {2-1}$ Euclid's Division Lemma: Theorem $\text {2-1}$
Category:Division Theorem
Division Theorem/Positive Divisor/Positive Dividend/Existence/Proof 3

== Theorem ==
== 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:
and so:
Hence the result.
== Sources ==
* : Chapter $\text {IV}$: Rings and Fields: $24$. The Division Algorithm: Theorem $24.1$
Category:Division Theorem
Division Theorem/Positive Divisor/Positive Dividend/Uniqueness

== Theorem ==
For every pair of integers $a, b$ where $a \ge 0$ and $b > 0$, the integers $q, r$ such that $a = q b + r$ and $0 \le r < b$ are unique:
:$\forall a, b \in \Z, a \ge 0, b > 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < b$
== Proof 1 ==
== Proof 2 ==
Category:Division Theorem
Division Theorem/Positive Divisor/Positive Dividend/Uniqueness/Proof 1

== Theorem ==
== Proof ==
It is given by Division Theorem: Positive Divisor: Positive Dividend: Existence that such $q$ and $r$ exist.
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:
This gives:
:$0 = b \paren {q_1 - q_2} + \paren {r_1 - r_2}$
 that $q_1 \ne q_2$.
, suppose that $q_1 > q_2$.
Then:
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.
== Sources ==
* : Chapter $1$: Properties of the Natural Numbers: $\S 21$
* : Appendix $1$: Some Results from the Elementary Theory of Numbers: Theorem $6$
Category:Division Theorem
Division Theorem/Positive Divisor/Positive Dividend/Uniqueness/Proof 2

== Theorem ==
== 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$.
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.
Let $a > 0$ and $b > 1$.
By the Basis Representation Theorem, $a$ has a unique representation to the base $b$:
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:
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:
and hence $q' = q$.
== Sources ==
* : $\text {2-1}$ Euclid's Division Lemma: Theorem $\text {2-1}$
Category:Division Theorem
Division Theorem/Positive Divisor/Uniqueness

== Theorem ==
For every pair of integers $a, b$ where $b > 0$, the integers $q, r$ such that $a = q b + r$ and $0 \le r < b$ are unique:
:$\forall a, b \in \Z, b > 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < b$
In the above equation:
:$a$ is the dividend
:$b$ is the divisor
:$q$ is the quotient
:$r$ is the principal remainder, or, more usually, just the remainder.
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Sources ==
* : Introduction $\S 6$: The division process in $I$: Theorem
* : $\text {2-1}$ Euclid's Division Lemma: Theorem $\text {2-1}$
Category:Division Theorem
Division Theorem/Positive Divisor/Uniqueness/Proof 2

== Theorem ==
For every pair of integers $a, b$ where $b > 0$, the integers $q, r$ such that $a = q b + r$ and $0 \le r < b$ are unique:
:$\forall a, b \in \Z, b > 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < 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.
== Sources ==
* : $\S 11.1$: The division algorithm
Category:Division Theorem
Division Theorem/Positive Divisor/Uniqueness/Proof 3

== Theorem ==
For every pair of integers $a, b$ where $b > 0$, the integers $q, r$ such that $a = q b + r$ and $0 \le r < b$ are unique:
:$\forall a, b \in \Z, b > 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < 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$.
, 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$.
== Sources ==
* : Chapter $3$: The Integers: $\S 10$. Divisibility: Theorem $18$
* : Chapter $2$: Divisibility Theory in the Integers: $2.1$ The Division Algorithm: Theorem $2 \text{-} 1$ (Division Algorithm)
Category:Division Theorem
Division Theorem/Proof 1

== Theorem ==
== 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$.
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$.
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.1$ The Division Algorithm: Theorem $2 \text{-} 1$ (Division Algorithm): Corollary
Category:Division Theorem
Division Theorem/Proof 2

== Theorem ==
== Proof ==
Consider the set of integer multiples $x \size b$ of $\size b$ less than or equal to $a$:
:$M := \set {k \in \Z: \exists x \in \Z: k = x \size b, k \le a}$
We have that:
:$-\size a \size b \le -\size a \le a$
and so $M \ne \O$.
From Set of Integers Bounded Above by Integer has Greatest Element, $M$ has a greatest element $h \size b$.
Then $h \size b \le a$ and so:
:$a = h \size b + r$
where $r \ge 0$.
On the other hand:
:$\paren {h + 1} \size b = h \size b + \size b > h \size b$
So:
:$\paren {h + 1} \size b > a$
and:
:$h \size b + \size b > h \size b + r$
Thus:
:$r \le b$
Setting:
:$q = h$ when $b > 0$
:$q = -h$ when $b < 0$
it follows that:
:$h \size b = q b$
and so:
:$a = q b + r$
as required.
== Sources ==
* : Introduction $\S 6$: The division process in $I$: Theorem
Category:Division Theorem
Division Theorem/Proof 3

== Theorem ==
== Proof ==
=== Existence ===
Consider the arithmetic sequence:
:$\ldots, a - 3 b, a - 2 b, a - b, a, a + b, a + 2 b, a + 3 b, \ldots$
which extends in both directions.
Then by the Well-Ordering Principle, there must exist a smallest non-negative element, denoted by $r$.
So $r = a - q b$ for some $q \in \Z$.
$r$ must be in the interval $\hointr 0 b$ because otherwise $r - b$ would be smaller than $r$ and a non-negative element in the sequence.
=== Uniqueness ===
Suppose we have another pair $q_0$ and $r_0$ such that $a = b q_0 + r_0$, with $0 \le r_0 < b$.
Then:
:$b q + r = b q_0 + r_0$
Factoring we see that:
:$r - r_0 = b \paren {q_0 - q}$
and so:
:$b \divides \paren {r - r_0}$
Since $0 \le r < b$ and $0 \le r_0 < b$, we have that:
:$-b < r - r_0 < b$
Hence:
:$r - r_0 = 0 \implies r = r_0$
So now:
:$r - r_0 = 0 = b \paren {q_0 - q}$
which implies that:
:$q = q_0$
Therefore the solution is unique.
Category:Division Theorem
Division Theorem for Ordinals

== Theorem ==
Let $x$ and $y$ be ordinals.
Let $0$ denote the zero ordinal.
Suppose $y \ne 0$.
Then there exist unique ordinals $z$ and $w$ such that:
:$x = \paren {y \times z} + w$ and $w < y$.
== Proof ==
=== Existence of $z$ and $w$ ===
First, it must be proven that such $z$ and $w$ exist.
By Relation between Two Ordinals, it follows that:
:$x < y$ or $y \le x$
The proof shall proceed by cases.
==== Case 1 ====
If $x < y$, then set $z = 0$ and $w = x$.
Since $w = x$, then $w < y$.
Furthermore, by Ordinal Multiplication by Zero:
:$x = \paren {y \times z} + w$
==== Case 2 ====
If $y \le x$, then set $z = \bigcup \set {v : \paren {y \times v} \le x}$.
Set $w$ equal to the unique $u$ such that $\paren {y \times z} + u = x$.
By Ordinal Multiplication by One, it follows that $1 \le z$.
By Union of Ordinals is Least Upper Bound, it follows that $z$ is the least upper bound of $\set {v : \paren {y \times v} \le x}$.
Take any $u \in z$.
Then $u \in v$ for some $\paren {y \times v} \le x$
But then, by Membership is Left Compatible with Ordinal Multiplication, it follows that $\paren {y \times u} \le x$.
So $z$ is a transitive subset of $\On$ and therefore, it is an ordinal.
Since $z \ne 0$, then by the definition of limit ordinal, then $z = u^+$ for some $u$ or $z$ is a limit ordinal.
Suppose $z = u^+$.
Then $u < z$ and $y \times u \le x$.
Moreover, $u < v$ for some $y \times v \le x$.
This means that $v \not < z$ by No Natural Number between Number and Successor.
By Ordinal Membership is Trichotomy, $z \le v$.
Therefore:
:$y \times z \le x$
Suppose $z \in K_{II}$.
Note that $\forall u \in z: y \times u \le x$ so:
In either case, $y \times z \le x$.
Moreover, suppose that $y \times z^+ \le x$.
Then $z$ is not an upper bound of the set $\set {v : \paren {y \times v} \le x}$, which is a contradiction.
So $\paren {y \times z} + w = x$ for some $w \in y$ by Ordinal Subtraction when Possible is Unique.
=== Uniqueness of $z$ and $w$ ===
Suppose that $\paren {y \times z_1} + w_1 = x$ for some $w_1 \in y$.
Suppose that $\paren {y \times z_2} + w_2 = x$ for some $w_2 \in y$.
Then for both $z = z_1$ and $z = z_2$, the following inequality is established:
It follows that $y \times z_1 < y \times z_2^+$ and $y \times z_2 < y \times z_1^+$.
By Membership is Left Compatible with Ordinal Multiplication, $z_1 < z_2^+$ and $z_2 < z_1^+$.
Therefore $z$ is unique.
Since $z$ is unique, then $w$ is unique by Ordinal Subtraction when Possible is Unique.
== Sources ==
* : $\S 8.27$
Category:Ordinal Arithmetic