avewright/proofwiki-math huggingface dataset:
Theorem: Ring Epimorphism from Integers to Integers Modulo m

Let $\struct {\Z, +, \times}$ be the ring of integers.
Let $\struct {\Z_m, +_m, \times_m}$ be the ring of integers modulo $m$.
Let $\phi: \struct {\Z, +, \times} \to \struct {\Z_m, +_m, \times_m}$ be the mapping defined as:
:$\forall x \in \Z: \map \phi x = \eqclass x m$
where $\eqclass x m$ is the residue class modulo $m$.
Then $\phi$ is a ring epimorphism, but specifically not a ring monomorphism.
The image of $\phi$ is $\struct {\Z_m, +_m, \times_m}$.
The kernel of $\phi$ is $m \Z$, the set of integer multiples of $m$.

Proof:
Let $a, b \in \Z$.
Then:
{{begin-eqn}}
{{eqn | l = \map \phi {a + b}
      | r = \eqclass {a + b} m
      | c = Definition of $\phi$
}}
{{eqn | r = \eqclass a m +_m \eqclass b m
      | c = {{Defof|Modulo Addition}}
}}
{{eqn | r = \map \phi a +_m \map \phi b
      | c = Definition of $\phi$
}}
{{end-eqn}}
{{begin-eqn}}
{{eqn | l = \map \phi {a \times b}
      | r = \eqclass {a \times b} m
      | c = Definition of $\phi$
}}
{{eqn | r = \eqclass a m \times_m \eqclass b m
      | c = {{Defof|Modulo Multiplication}}
}}
{{eqn | r = \map \phi a \times_m \map \phi b
      | c = Definition of $\phi$
}}
{{end-eqn}}
Hence $\phi$ is a ring homomorphism.
Now let $\eqclass a m \in \Z_m$.
By definition of residue class modulo $m$:
:$\eqclass a m = \set {x \in \Z: \exists k \in \Z: z = a + k m}$
Setting $k = 0$:
:$\map \phi a = \eqclass a m$
and so:
:$\map {\phi^{-1} } {\eqclass a m} \ne \O$
Thus $\phi$ is a surjection.
Now setting $k = 1$, for example, we have that:
:$\map \phi {a + m} = \eqclass a m$
and so:
:$\map \phi a = \map \phi {a + m}$.
So $\phi$ is specifically not an injection.
It follows by definition that $\phi$ is a ring epimorphism, but specifically not a ring monomorphism.
Next we note that:
:$\forall x \in \Z: \map \phi x \in \Z_m$
and so:
:$\Img \phi = \Z_m$
Finally, we have that the kernel of $\phi$ is:
:$\map \ker \phi = \set {x \in \Z: \map \phi x = \eqclass 0 m}$
Let $\map \phi x = \eqclass 0 m$
Then $x = 0 + k m$ for some $k \in \Z$.
That is, $x \in m \Z$ and so:
:$\map \ker \phi \subseteq m \Z$
Now let $x \in m \Z$.
Then:
:$\exists k \in \Z: x = 0 + k m$
and so by definition:
:$\map \phi x = \eqclass 0 m$
So:
:$m \Z \subseteq \map \ker \phi$
Hence:
:$\map \ker \phi = m \Z$
{{qed}}
Theorem: Monotone Additive Function is Linear

Let $f: \R \to \R$ be a monotone real function which is additive, that is:
:$\forall x, y \in \R: \map f {x + y} = \map f x + \map f y$
Then:
:$\exists a \in \R: \forall x \in \R: \map f x = a x$
That is, $f$ is a linear function.

Proof:
We use a Proof by Contraposition.
To that end, suppose $f$ is not linear.
We know that Graph of Nonlinear Additive Function is Dense in the Plane.
Therefore $f$ is not bounded on any nonempty open interval.
But then $f$ is certainly not monotone.
Hence, by Rule of Transposition, if $f$ is monotone, then it is linear.
Theorem: Units of Ring of Polynomial Forms over Field

Let $\struct {F, +, \circ}$ be a field whose zero is $0_F$ and whose unity is $1_F$.
Let $F \sqbrk X$ be the ring of polynomial forms in an indeterminate $X$ over $F$.
Then the units of $F \sqbrk X$ are all the elements of $F \sqbrk X$ whose degree is $0$.

Proof:
An element of $F \sqbrk X$ whose degree is $0$ is merely an element of $F$.
But note that $0_F$, considered as an element of $F \sqbrk X$, has a degree which is not defined, so the null polynomial is seen to be excluded.
Any element $a$ of $F$ has an inverse $1_F / a$.
So all the elements of $F \sqbrk X$ whose degree is $0$ are units of $F$ and hence of $F \sqbrk X$.
Now suppose $\map a X \in F \sqbrk X$ is a unit of $F \sqbrk X$.
Then $\map a X \, \map q X = 1_F$ for some $\map q X \in F \sqbrk X$.
Neither $\map a X$ nor $\map q X$ can be null.
So by Properties of Degree $\map \deg {\map a X} + \map \deg {\map q X} = 0$.
So $\map \deg {\map a X} = 0$.
{{qed}}
Theorem: Units of Quadratic Integers over 2

Let $\Z \sqbrk {\sqrt 2}$ denote the set of quadratic integers over $2$:
:$\Z \sqbrk {\sqrt 2} := \set {a + b \sqrt 2: a, b \in \Z}$
that is, all numbers of the form $a + b \sqrt 2$ where $a$ and $b$ are integers.
Let $\struct {\Z \sqbrk {\sqrt 2}, +, \times}$ be the integral domain where $+$ and $\times$ are conventional addition and multiplication on real numbers.
Then numbers of the form $a + b \sqrt 2$ such that $a^2 - 2 b^2 = \pm 1$ are all units of $\struct {\Z \sqbrk {\sqrt 2}, +, \times}$.

Proof:
For $a + b \sqrt 2$ to be a unit of $\struct {\Z \sqbrk {\sqrt 2}, +, \times}$, we require that:
:$\exists c, d \in \Z: \paren {a + b \sqrt 2} \paren {c + d \sqrt 2} = 1$
In Quadratic Integers over 2 are Not a Field it is shown that the product inverse of $\paren {a + b \sqrt 2}$ is $\dfrac a {a^2 - 2 b^2} + \dfrac {b \sqrt 2} {a^2 - 2 b^2}$.
So if $a^2 - 2 b^2 = \pm 1$ it follows that $c$ and $d$ are integers.
Hence the result.
{{qed}}
Theorem: Units of Gaussian Integers

Let $\struct {\Z \sqbrk i, +, \times}$ be the ring of Gaussian integers.
The set of units of $\struct {\Z \sqbrk i, +, \times}$ is $\set {1, i, -1, -i}$.

Proof:
By definition of the imaginary unit $i$:
{{begin-eqn}}
{{eqn | l = i^2
      | r = -1
}}
{{eqn | l = i^3
      | r = -i
}}
{{eqn | l = i^4
      | r = 1
}}
{{end-eqn}}
thus demonstrating that $U_\C$ is generated by $i$.
Thus $\struct {U_\C, \times}$ is by definition a cyclic group of order $4$.
{{qed}}
Theorem: Units of Gaussian Integers

Let $\struct {\Z \sqbrk i, +, \times}$ be the ring of Gaussian integers.
The set of units of $\struct {\Z \sqbrk i, +, \times}$ is $\set {1, i, -1, -i}$.

Proof:
From Gaussian Integer Units are 4th Roots of Unity:
: $\left\{{1, i, -1, -i}\right\}$ constitutes the set of the $4$th roots of unity.
The result follows from Roots of Unity under Multiplication form Cyclic Group.
{{qed}}
Theorem: Units of Gaussian Integers

Let $\struct {\Z \sqbrk i, +, \times}$ be the ring of Gaussian integers.
The set of units of $\struct {\Z \sqbrk i, +, \times}$ is $\set {1, i, -1, -i}$.

Proof:
From Units of Gaussian Integers, $U_\C$ is the set of units of the ring of Gaussian integers.
From Group of Units is Group, $\left({U_\C, \times}\right)$ forms a group.
It remains to note that:
{{begin-eqn}}
{{eqn | l = i^2
      | r = -1
}}
{{eqn | l = i^3
      | r = -i
}}
{{eqn | l = i^4
      | r = 1
}}
{{end-eqn}}
thus demonstrating that $U_\C$ is  cyclic.
{{qed}}
Theorem: Units of Gaussian Integers

Let $\struct {\Z \sqbrk i, +, \times}$ be the ring of Gaussian integers.
The set of units of $\struct {\Z \sqbrk i, +, \times}$ is $\set {1, i, -1, -i}$.

Proof:
Let $a + b i$ be a unit of $\struct {\Z \sqbrk i, +, \times}$.
Then $a$ and $b$ are not both $0$ as then $a + b i$ would be the zero of $\struct {\Z \sqbrk i, +, \times}$.
Then:
:$\exists c, d \in \Z: \paren {a + b i} \paren {c + d i} = 1 + 0 i$
This leads (after algebra) to:
:$c = \dfrac a {a^2 + b^2}, d = \dfrac {-b} {a^2 + b^2}$
Let $a^2 + b^2 = n$.
We have that $n \in \Z, n > 0$.
If $c$ and $d$ are integers, then $a$ and $b$ must both be divisible by $n$.
Let $a = n x, b = n y$.
Then:
:$n^2 x^2 + n^2 y^2 = n$
and so:
:$n \paren {x^2 + y^2} = 1$
Thus $n = a^2 + b^2 = 1$ and so as $a, b \in \Z$ we have:
:$a^2 = 1, b^2 = 0$
or:
:$a^2 = 0, b^2 = 1$
from which the result follows.
{{qed}}
Theorem: Units of Gaussian Integers

Let $\struct {\Z \sqbrk i, +, \times}$ be the ring of Gaussian integers.
The set of units of $\struct {\Z \sqbrk i, +, \times}$ is $\set {1, i, -1, -i}$.

Proof:
Let $\alpha = a + b i$ be a unit of $\struct {\Z \sqbrk i, +, \times}$.
Then by definition of unit:
:$\exists\beta = c + d i \in \Z \sqbrk i: \alpha \beta = 1$
Let $\cmod \alpha$ denote the modulus of $\alpha$.
Then:
{{begin-eqn}}
{{eqn | l = \cmod \alpha^2 \cdot \cmod \beta^2
      | r = \cmod {\alpha \beta}^2
      | c = Modulus of Product
}}
{{eqn | r = \cmod 1^2
      | c = 
}}
{{eqn | r = 1
      | c = 
}}
{{end-eqn}}
By Divisors of One:
:$\cmod a^2 = 1$ or $-1$
Since $\cmod \alpha$ and $\cmod \beta$ are positive integers:
:$\cmod \alpha^2 = a^2 + b^2 = 1$
and so either:
:$\cmod a = 1$ and $\cmod b = 0$
or:
:$\cmod b = 1$ and $\cmod a = 0$.
Hence the set of units of $\struct {\Z \sqbrk i, +, \times}$ is $\set {\pm 1, \pm i}$.
{{qed}}
Theorem: Integers are Euclidean Domain

The integers $\Z$ with the mapping $\nu: \Z \to \Z$ defined as:
:$\forall x \in \Z: \map \nu x = \size x$
form a Euclidean domain.

Proof:
From Integers form Ordered Integral Domain we have that $\struct {\Z, +, \times, \le}$ forms an ordered integral domain.
For all $a \in \Z$, the absolute value of $a$ is defined as:
:$\size a = \begin{cases} a & : 0 \le a \\ -a & : a < 0 \end{cases}$
By Product of Absolute Values on Ordered Integral Domain we have:
:$\forall a, b \in \Z: \size a \cdot \size b = \size {a b}$
Since $\size b > 0$ it follows from Relation Induced by Strict Positivity Property is Compatible with Multiplication that $\size a \cdot \size b \ge \size a$.
The second criterion:
:For any $a, b \in R$, $b \ne 0$, there exist $q, r \in R$ with $\map \nu r < \map \nu b$, or $r = 0$ such that:
::$ a = q \circ b + r$
follows from the Division Theorem.
{{qed}}
Theorem: Gaussian Integers form Euclidean Domain

Let $\struct {\Z \sqbrk i, +, \times}$ be the integral domain of Gaussian Integers.
Let $\nu: \Z \sqbrk i \to \R$ be the real-valued function defined as: 
:$\forall a \in \Z \sqbrk i: \map \nu a = \cmod a^2$ 
where $\cmod a$ is the (complex) modulus of $a$.
Then $\nu$ is a Euclidean valuation on $\Z \sqbrk i$.
Hence $\struct {\Z \sqbrk i, +, \times}$ with $\nu: \Z \sqbrk i \to \Z$ forms a Euclidean domain.

Proof:
We have by definition that $\Z \sqbrk i \subseteq \C$.
Let $a, b \in \Z \sqbrk i$.
We have from Modulus of Product that $\cmod a \cdot \cmod b = \cmod {a b}$.
From Complex Modulus is Non-Negative:
:$\forall a \in \C: \cmod a \ge 0$
and:
:$\cmod a = 0 \iff a = 0$
Let $a = x + i y$.
Suppose $a \in \Z \sqbrk i \ne 0$.
Then $x \ne 0$ or $y \ne 0$ and $x^2 \ge 1$ or $y^2 \ge 1$.
So:
:$\cmod a \ge 1$
Similarly, $b \in \Z \sqbrk i, b \ne 0 \implies \cmod b \ge 1$.
Thus it follows that $\cmod {a b} \ge \cmod a$ and so $\nu$ is a Euclidean valuation on $\Z \left[{i}\right]$.
{{finish|definition of Euclidean valuation requires codomain $\N$, consider modulus squared instead}}
Now, consider $x, y \in \Z \sqbrk i$.
We want to find $q, r \in \Z \sqbrk i$ such that $x = q y + r$.
Note that this means we want $r = y \paren {\dfrac x y - q}$ where $\dfrac x y$ is complex but not necessarily Gaussian.
We extend $\nu$ to the complex numbers and define $\nu: \C \to \C$ as:
:$\forall z \in \C: \map \nu z = \cmod z$
Then we have:
:$\map \nu r = \map \nu y \cdot \map \nu {\dfrac x y - q}$
Thus if $\map \nu {\dfrac x y - q} < 1$ we have:
:$\map \nu r < \map \nu y$
Consider the point $P = \dfrac x y$ as a point on the complex plane.
Let $Q$ lie at a point representing the Gaussian integer $q$ which lies closest to $P$.
The distance $P Q$ is at most half the length of a diagonal of a unit square in the complex plane.
Thus:
:$\map \nu {\dfrac x y - q} = \cmod {\dfrac x y - q} \le \dfrac {\sqrt 2} 2 = \dfrac 1 {\sqrt 2} < 1$
This element $q$ and the element $r$, where $\map \nu r < \map \nu y$, are the required values.
Thus $\Z \sqbrk i$ is a Euclidean domain.
{{qed}}
{{Improve}}
Theorem: Gaussian Integers form Euclidean Domain

Let $\struct {\Z \sqbrk i, +, \times}$ be the integral domain of Gaussian Integers.
Let $\nu: \Z \sqbrk i \to \R$ be the real-valued function defined as: 
:$\forall a \in \Z \sqbrk i: \map \nu a = \cmod a^2$ 
where $\cmod a$ is the (complex) modulus of $a$.
Then $\nu$ is a Euclidean valuation on $\Z \sqbrk i$.
Hence $\struct {\Z \sqbrk i, +, \times}$ with $\nu: \Z \sqbrk i \to \Z$ forms a Euclidean domain.

Proof:
We have by definition that $\Z \sqbrk i \subseteq \C$.
Let $a, b \in \Z \sqbrk i$.
We have from Modulus of Product that:
:$\cmod a \cdot \cmod b = \cmod {a b}$
From Complex Modulus is Norm we have that:
:$\forall a \in \C: \cmod a \ge 0$
:$\cmod a = 0 \iff a = 0$
Suppose $a = x + i y \in \Z \sqbrk i$ and $a \ne 0$.
Then either $x \ne 0$ or $y \ne 0$, so either $x^2 \ge 1$ or $y^2 \ge 1$.
So $\cmod a^2 \ge 1$.
If also $b \in \Z \sqbrk i, b \ne 0$, then:
:$\map \nu {a b} = \cmod {a b}^2 \ge \cmod a^2 = \map \nu a$
Now, consider $x, y \in Z \sqbrk i$ with $y \ne 0$.
We want to find $q, r \in Z \sqbrk i$ such that $x = q y + r$ and $\map \nu r < \map \nu y$.
Note that this means we want $r = y \paren {\dfrac x y - q}$ where $\dfrac x y$ is complex but not necessarily Gaussian.
Consider the complex number $p = \dfrac x y = p_r + i p_i$.
We extend $\nu$ to the complex numbers and define $\nu: \C \to \C$ as:
:$\forall z \in \C: \map \nu z = \cmod z^2$
Let $q = q_r + i q_i$ be the Gaussian integer such that:
:$\map \nu {p - q} = \cmod {p - q}^2 = \paren {p_r - q_r}^2 + \paren {p_i - q_i}^2$
is minimal.
That is, $q_r$ is the nearest integer to $p_r$ and $q_i$ is the nearest integer to $p_i$.
A given real number can be at a distance at most $1/2$ from an integer, so it follows that:
:$(1): \quad \map \nu {p - q} \le \paren {\dfrac 1 2}^2 + \paren {\dfrac 1 2}^2 = \dfrac 1 2$
Now by Complex Modulus is Norm, for any two complex numbers $z_1, z_2$ we have:
:$\map \nu {z_1 z_2} = \map \nu {z_1} \, \map \nu {z_2}$
Thus we obtain:
{{begin-eqn}}
{{eqn | l = \map \nu {y \paren {p - q} }
      | r = \map \nu y \, \map \nu {p - q}
}}
{{eqn | r = \dfrac {\map \nu y} 2
      | o = \le
      | c = by $(1)$
}}
{{eqn | r = \map \nu y
      | o = <
      | c = since $\map \nu y \ne 0$
}}
{{end-eqn}}
On the other hand:
{{begin-eqn}}
{{eqn | l = \map \nu {y \paren {p - q} }
      | r = \map \nu {y \paren {\frac x y - q} }
}}
{{eqn | r = \map \nu {x - y q}
}}
{{end-eqn}}
So letting $r = x - y q$ we have $\map \nu r < \map \nu y$.
Moreover we trivially have $x = q y + r$.
Thus $\Z \sqbrk i$ is a Euclidean domain.
{{qed}}
Theorem: Degree of Product of Polynomials over Ring

:$\forall f, g \in R \sqbrk X: \map \deg {f g} \le \map \deg f + \map \deg g$

Proof:
Let the leading coefficient of:
:$\map f X$ be $a_n$
:$\map g X$ be $b_n$.
Then:
{{begin-eqn}}
{{eqn | l = \map f X
      | r = a_n X^n + \cdots + a_0
}}
{{eqn | l = \map g X
      | r = b_n X^n + \cdots + b_0
}}
{{end-eqn}}
Consider the leading coefficient of the product $\map f X \map g X$: call it $c$.
From the definition of polynomial addition and polynomial multiplication: 
:$\map f X \map g X = c X^{n + m} + \cdots + a_0 b_0$
Clearly the highest term of $\map f X \map g X$ can have an index no higher than $n + m$.
Hence the result:
:$\map \deg {f g} \not > \map \deg f + \map \deg g$
Next, note that the general ring with unity $\struct {R, +, \circ}$ may have proper zero divisors.
Therefore it is possible that $X^{n + m}$ may equal $0_R$.
If that is the case, then the highest term will have an index definitely less than $n + m$.
That is, in that particular case:
:$\map \deg {f g} < \map \deg f + \map \deg g$
Thus, for a general ring with unity $\struct {R, +, \circ}$:
:$\map \deg {f g} \le \map \deg f + \map \deg g$
{{qed}}
Theorem: Degree of Sum of Polynomials

:$\forall f, g \in R \sqbrk X: \map \deg {f + g} \le \max \set {\map \deg f, \map \deg g}$

Proof:
First we associate to $f = a_0 + a_1 X + \cdots + a_n X^n \in R \sqbrk X$ a formal vector $x_f = \tuple {a_0, a_1, \ldots, a_n, 0_R, \ldots} \in R^\infty$.
Let $x_f^i \in R$ denote the element at the $i$th position. 
Then:
:$\map \deg f = \sup \set {i \in \N : x_f^i \ne 0_R}$
The sum $+$ in the polynomial ring $R \sqbrk X$ gives rise to the following identity in $R^\infty$:
:$x_{f + g}^i = x_f^i + x_g^i$
Next, let $f, g \in R \sqbrk X$, and let $d = \max \set {\map \deg f, \map \deg g}$.
Then $x_f^i = 0_R = x_g^i$ for all $i > d$, so we have:
:$\map \deg {f + g} = \sup \set {i \in \N : x_{f + g}^i \ne 0_R} = \sup \set {i \in \N : x_f^i + x_g^i \ne 0_R} \le d$
{{qed}}
Theorem: Degree of Product of Polynomials over Integral Domain not Less than Degree of Factors

:$\forall f, g \in R \sqbrk X: \map \deg {f g} \ge \map \deg f$

Proof:
From Degree of Product of Polynomials over Integral Domain, we have:
:$\map \deg {f g} = \map \deg f + \map \deg g$
But $\map \deg g \ge 0$ by definition of degree, as $g$ is not null.
Hence the result.
{{qed}}
Theorem: Polynomial Forms over Field is Euclidean Domain

Let $\struct {F, +, \circ}$ be a field whose zero is $0_F$ and whose unity is $1_F$.
Let $X$ be transcendental in $F$.
Let $F \sqbrk X$ be the ring of polynomial forms in $X$ over $F$.
Then $F \sqbrk X$ is a Euclidean domain.

Proof:
From Degree of Product of Polynomials over Integral Domain not Less than Degree of Factors we have that:
:$\forall a, b \in F \sqbrk X, a \ne 0_F, b \ne 0_F: \map \deg {a b} \ge \map \deg a$
where $\map \deg a$ denotes the degree of $a$.
From Division Theorem for Polynomial Forms over Field:
:$\forall a, b \in F \sqbrk X, b \ne 0_F: \exists q, r \in F \sqbrk X: a = q b + r$
where $\map \deg r < \map \deg b$ (or $r = 0$), and $q$ and $r$ are unique.
So $\deg$ is a Euclidean valuation on $F \sqbrk X$.
Hence the result.
{{qed}}
Theorem: Euclidean Domain is Principal Ideal Domain

A Euclidean domain is a principal ideal domain.

Proof:
Let $\struct {D, +, \times}$ be a Euclidean domain whose zero is $0$ and whose Euclidean valuation is $\nu$.
We need to show that every ideal of $\struct {D, +, \times}$ is a principal ideal.
Let $U$ be an ideal of $\struct {D, +, \times}$ such that $U \ne \set 0$.
Let $d \in U$ such that $d \ne 0$ and $\map \nu d$ is as small as possible for elements of $U$.
By definition, $\nu$ is defined as $\nu : D \setminus \set 0 \to \N$, so the codomain of $\nu$ is a subset of the natural numbers.
By the Well-Ordering Principle, such an element $d$ exists as an element of the preimage of the least member of the image of $U$.
<!--{{explain|Need to ensure that the Well-Ordering Principle can be applied here.}}-->
Let $a \in U$.
Let us write $a = d q + r$ where either $r = 0$ or $\map \nu r < \map \nu d$.
Then $r = a - d q$ and so $r \in U$.
Suppose $r \ne 0$.
That would mean $\map \nu r < \map \nu d$ contradicting $d$ as the element of $U$ with the smallest $\nu$.
So $r = 0$, which means $a = q d$.
That is, every element of $U$ is a multiple of $d$.
So $U$ is the principal ideal generated by $d$.
This deduction holds for all ideals of $D$.
Hence the result.
{{qed}}
Theorem: Polynomial Forms is PID Implies Coefficient Ring is Field

Let $D$ be an integral domain.
Let $D \sqbrk X$ be the ring of polynomial forms in $X$ over $D$.
Let $D \sqbrk X$ be a principal ideal domain;
Then $D$ is a field.

Proof:
Let $y \in D$ be non-zero.
Then, using the principal ideal property, for some $f \in D \sqbrk X$ we have:
:$\gen {y, X} = \gen f \subseteq D \sqbrk X$
Therefore:
:$\exists p, q \in D \sqbrk X: y = f p, X = f q$
By Properties of Degree we conclude that $f = a$ and $q = b + c X$ for some $a, b, c \in D$.
Substituting into the equation $X = f q$ we obtain:
:$X = a b + a c X$
which implies that:
:$a c = 1$
That is:
:$a \in D^\times$
where $D^\times$ denotes the group of units of $D$.
Therefore:
:$\gen f = \gen 1 = D \sqbrk X$
Therefore:
:$\exists r, s \in D \sqbrk X: r y + s X = 1$
If $d$ is the constant term of $r$, then we have $y d = 1$.
Therefore $y \in D^\times$.
Our choice of $y$ was arbitrary, so this shows that $D^\times \supseteq D \setminus \set 0$.
This says precisely that $D$ is a field.
{{qed}}
Theorem: Euclidean Domain is GCD Domain

Let $\struct {D, +, \times}$ be a Euclidean domain.
Then any two elements $a, b \in D$ have a greatest common divisor $d$ such that:
:$d \divides a \land d \divides b$
:$x \divides a \land x \divides b \implies x \divides d$
and $d$ is written $\gcd \set {a, b}$.
For any $a, b \in D$:
:$\exists s, t \in D: s a + t b = d$
Any two greatest common divisors of any $a, b$ are associates.

Proof:
Let $a, b \in D$.
Let $U \subseteq D$ be the set of all elements $h a + k b$ of $D$ where $h, k \in D$.
Then $U$ is an ideal of $D$.
Note that $U = \ideal a + \ideal b$ where $\ideal a$ and $\ideal b$ are Principal Ideal.
By Sum of Ideals is Ideal, $U$ is an ideal.
By Euclidean Domain is Principal Ideal Domain, $U$ is a principal ideal, $\ideal d$ say.
As $a, b \in U$ it follows that $d$ is a divisor of $a$ and $b$, that is:
:$d \divides a \land d \divides b$
Since $d$ itself is in $U$, we have:
:$\exists s, t \in D: s a + t b = d$
By Common Divisor in Integral Domain Divides Linear Combination:
:$x \divides a \land x \divides b \implies x \divides d$
So $d$ is a greatest common divisor of $a$ and $b$.
If $d$ and $d'$ are both greatest common divisors of $a$ and $b$, then $d \divides a \land d \divides b$ and so $d \divides d'$.
Similarly $d' \divides d$.
So $d$ and $d'$ are associates.
{{qed}}
Theorem: Associates in Ring of Polynomial Forms over Field

Let $F \sqbrk X$ be the ring of polynomial forms over the field $F$.
Let $\map d X$ and $\map {d'} X$ be polynomial forms in $F \sqbrk X$.
Then $\map d X$ is an associate of $\map {d'} X$ {{iff}} $\map d X = c \cdot \map {d'} X$ for some $c \in F, c \ne 0_F$.
Hence any two polynomials in $F \sqbrk X$ have a unique monic GCD.

Proof:
From the definition of associate, there exist $\map e X$ and $\map {e'} X$ \in $F \sqbrk X$ such that:
:$\map d X = \map e X \cdot \map {d'} X$
:$\map {d'} X = \map {e'} X \cdot \map d X$
From Field is Integral Domain, $F$ is an integral domain.
From Degree of Product of Polynomials over Integral Domain it follows that necessarily $\deg e = \deg e' = 0$, as $F$ has no proper zero divisors.
Thus for some $c, c' \in F$, it must be that $\map e X = c$ and $\map {e'} X = c'$.
From the two equations above it follows that $c \cdot c' = 1_F$, where $1_F$ is the unity of $F$.
Hence, it follows that $c \ne 0_F$.
The result follows.
{{qed}}
Theorem: Zero Element Generates Null Ideal

Let $\struct {R, +, \circ}$ be a ring whose zero is $0_R$.
For $r \in R$, let $\ideal r$ denote the ideal generated by $r$.
Then $\ideal {0_R}$ is the null ideal.

Proof:
By definition:
:$\ideal {0_R} = \set {r \circ 0_R: r \in R}$
but for each $r \in R$ we have by Ring Product with Zero that $r \circ 0_R = 0_R$ for all $r \in R$.
Therefore $\ideal {0_R}$ is the null ideal.
{{qed}}
Category:Ideal Theory
g0bxzwsul4zh97e4us5incfu0yaqszb
Theorem: Irreducible Elements of Ring of Integers

Let $\struct {\Z, +, \times}$ be the ring of integers.
The irreducible elements of $\struct {\Z, +, \times}$ are the prime numbers and their negatives.

Proof:
We have that Integers form Integral Domain.
Therefore the concept of irreducible is defined.
Let $p$ be a prime number.
By definition, the only divisors of $p$ are $1, -1, p, -p$.
From Units of Ring of Integers, $1$ and $-1$ are (the only) units of $\Z$.
From Associates are Unit Multiples, $p$ and $-p$ are (the only) associates of each other.
Hence the result, from the definition of irreducible.
{{qed}}
Theorem: Euclid's Lemma for Euclidean Domains

Let $\struct {D, +, \times}$ be a Euclidean domain whose unity is $1$.
Let $a, b, c \in D$.
Let $a \divides b \times c$, where $\divides$ denotes divisibility.
Let $a \perp b$, where $\perp$ denotes relative primeness.
Then $a \divides c$.

Proof:
{{begin-eqn}}
{{eqn | l = a
      | o = \perp
      | r = b
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \gcd \set {a, b}
      | r = 1
      | c = {{Defof|Coprime Elements of Euclidean Domain}}
}}
{{eqn | ll= \leadsto
      | q = \exists x, y \in D
      | l = a \times x + b \times y
      | r = 1
      | c = Bézout's Identity on Euclidean Domain
}}
{{eqn | ll= \leadsto
      | l = c
      | r = c \times \paren {a \times x + b \times y}
      | c = 
}}
{{eqn | r = c \times a \times x + c \times b \times y
      | c = 
}}
{{eqn | r = \paren {a \times c} \times x + \paren {b \times c} \times y
      | c = 
}}
{{eqn | ll= \leadsto
      | l = a
      | o = \divides
      | r = c \times \paren {a \times x + b \times y}
      | c = as $a \divides a \times c$ and $a \divides b \times c$
}}
{{eqn | r = c \times 1
      | c = Bézout's Identity on Euclidean Domain
}}
{{eqn | r = c
      | c = 
}}
{{end-eqn}}
{{qed}}
{{Namedfor|Euclid}}