avewright/proofwiki-math huggingface dataset:
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:
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.
{{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:
=== 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.
{{qed|lemma}}
=== 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.
{{Qed}}
Theorem: Odd Integer 2n + 1

Let $m$ be an odd integer.
Then there exists exactly one integer $n$ such that $2 n + 1 = m$.

Proof:
Follows directly from the Division Theorem.
{{qed}}
Category:Odd Integers
mpi9q6vy7fvjpowo6jxu7u75i7r217j
Theorem: Integer Divisor Results

Let $m, n \in \Z$ be integers.
Let $m \divides n$ denote that $m$ is a divisor of $n$.
The following results all hold:

Proof:
From Integer Multiplication Identity is One:
:$\forall n \in \Z: 1 \cdot n = n = n \cdot 1$
thus demonstrating that $n$ is a divisor of itself.
{{qed}}
Theorem: Integer Divisor Results

Let $m, n \in \Z$ be integers.
Let $m \divides n$ denote that $m$ is a divisor of $n$.
The following results all hold:

Proof:
As the set of integers form an integral domain, the concept '''divides''' is fully applicable to the integers.
Therefore this result follows directly from Element of Integral Domain is Divisor of Itself.
{{qed}}
Theorem: Zero Divides Zero

Let $n \in \Z$ be an integer.
Then:
:$0 \divides n \implies n = 0$
That is, zero is the only integer divisible by zero.

Proof:
{{begin-eqn}}
{{eqn | l = 0
      | o = \divides
      | r = n
      | c = 
}}
{{eqn | ll= \leadsto
      | q = \exists q \in \Z
      | l = n
      | r = q \times 0
      | c = {{Defof|Divisor of Integer}}
}}
{{eqn | ll= \leadsto
      | l = n
      | r = 0
      | c = Integers have no zero divisors, as Integers form Integral Domain.
}}
{{end-eqn}}
{{Qed}}
Theorem: Absolute Value of Integer is not less than Divisors

A (non-zero) integer is greater than or equal to its divisors in magnitude:
:$\forall c \in \Z_{\ne 0}: a \divides c \implies a \le \size a \le \size c$

Proof:
Suppose $a \divides c$ for some $c \ne 0$.
From Negative of Absolute Value:
: $a \le \size a$
Then:
{{begin-eqn}}
{{eqn | l = a
      | o = \divides
      | r = c
      | c = 
}}
{{eqn | ll= \leadsto
      | q = \exists q \in \Z
      | l = c
      | r = a q
      | c = {{Defof|Divisor of Integer}}
}}
{{eqn | ll= \leadsto
      | l = \size c
      | r = \size a \size q
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \size a \size q \ge \size a \times 1
      | r = \size a
      | c = 
}}
{{eqn | ll= \leadsto
      | l = a \le \size a
      | o = \le
      | r = \size c
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Divisor Relation on Positive Integers is Partial Ordering

The divisor relation is a partial ordering of $\Z_{>0}$.

Proof:
Checking in turn each of the criteria for an ordering:
Theorem: Common Divisor in Integral Domain Divides Linear Combination

Let $\struct {D, +, \times}$ be an integral domain.
Let $c$ be a common divisor of two elements $a$ and $b$ of $D$.
That is:
:$a, b, c \in D: c \divides a \land c \divides b$
Then:
:$\forall p, q \in D: c \divides \paren {p \times a + q \times b}$

Proof:
{{begin-eqn}}
{{eqn | l = c
      | o = \divides
      | r = a
}}
{{eqn | ll= \leadsto
      | q = \exists x \in D
      | l = a
      | r = x \times c
      | c = {{Defof|Divisor of Ring Element}}
}}
{{eqn | l = c
      | o = \divides
      | r = b
}}
{{eqn | ll= \leadsto
      | q = \exists y \in D
      | l = b
      | r = y \times c
      | c = {{Defof|Divisor of Ring Element}}
}}
{{eqn | ll= \leadsto
      | q = \forall p, q \in D
      | l = p \times a + q \times b
      | r = p \times x \times c + q \times y \times c
      | c = substituting for $a$ and $b$
}}
{{eqn | r = \paren {p \times x + q \times y} c
      | c = as $\times$ is distributive over $+$
}}
{{eqn | ll= \leadsto
      | q = \exists z \in D
      | l = p \times a + q \times b
      | r = z \times c
      | c = where $z = p \times x + q \times y$
}}
{{eqn | ll= \leadsto
      | l = c
      | o = \divides
      | r = \paren {p \times a + q \times b}
      | c = {{Defof|Divisor of Ring Element}}
}}
{{end-eqn}}
{{qed}}
Theorem: Existence of Greatest Common Divisor

Let $a, b \in \Z$ be integers such that $a \ne 0$ or $b \ne 0$.
Then the greatest common divisor of $a$ and $b$ exists.

Proof:
=== Proof of Existence ===
This is proved in Greatest Common Divisor is at least $1$.
{{qed|lemma}}
=== Proof of there being a Largest ===
{{WLOG}}, suppose $a \ne 0$.
First we note that from Absolute Value of Integer is not less than Divisors:
:$\forall c \in \Z: \forall a \in \Z_{>0}: c \divides a \implies c \le \size c \le \size a$
The same applies for $c \divides b$.
Now we have three different results depending on $a$ and $b$:
{{begin-eqn}}
{{eqn | l = a \ne 0 \land b \ne 0
      | o = \implies
      | r = \gcd \set {a, b} \le \min \set {\size a, \size b}
      | c = 
}}
{{eqn | l = a = 0 \lor b = 0
      | o = \implies
      | r = \gcd \set {a, b} = \max \set {\size a, \size b}
      | c = 
}}
{{eqn | l = a = b = 0
      | o = \implies
      | r = \forall x \in \Z: x \divides a \land x \divides b
      | c = 
}}
{{end-eqn}}
So if $a$ and $b$ are ''both'' zero, then ''any'' $n \in \Z$ divides both, and there is no greatest common divisor.
This is why the proviso that $a \ne 0 \lor b \ne 0$.
So we have proved that common divisors exist and are bounded above.
Therefore, from Set of Integers Bounded Above by Integer has Greatest Element there is always a '''greatest''' common divisor.
{{qed}}
Theorem: Existence of Greatest Common Divisor

Let $a, b \in \Z$ be integers such that $a \ne 0$ or $b \ne 0$.
Then the greatest common divisor of $a$ and $b$ exists.

Proof:
By definition of greatest common divisor, we aim to show that there exists $c \in \Z_{>0}$ such that:
{{begin-eqn}}
{{eqn | l = c
      | o = \divides
      | r = a
}}
{{eqn | l = c
      | o = \divides
      | r = b
}}
{{end-eqn}}
and:
:$d \divides a, d \divides b \implies d \divides c$
Consider the set $S$:
:$S = \set {s \in \Z_0: \exists x, y \in \Z: s = a x + b y}$
$S$ is not empty, because by setting $x = 1$ and $y = 0$ we have at least that $a \in S$.
From the Well-Ordering Principle, there exists a smallest $c \in S$.
So, by definition, we have $c > 0$ is the smallest such that $c = a x + b y$ for some $x, y \in \Z$.
Let $d$ be such that $d \divides a$ and $d \divides b$.
Then from Common Divisor Divides Integer Combination:
:$d \divides a x + b y$
That is:
:$d \divides c$
We have that:
{{begin-eqn}}
{{eqn | q = \exists t, u \in \Z
      | l = a
      | r = c t + u:
      | rr= 0 \le u < c
      | c = Division Theorem
}}
{{eqn | ll= \leadsto
      | l = a
      | r = a x t + b y t + u
      | c = Definition of $c$
}}
{{eqn | ll= \leadsto
      | l = u
      | r = r \paren {1 - x t} + b \paren {-y t} 
      | c = rearranging
}}
{{eqn | ll= \leadsto
      | l = u
      | r = 0
      | c = as $u < c$ and the definition of $c$
}}
{{eqn | ll= \leadsto
      | l = c
      | o = \divides
      | r = a
      | c = {{Defof|Divisor of Integer}}
}}
{{end-eqn}}
Mutatis mutandis:
:$c \divides b$
Now suppose $c'$ is such that:
{{begin-eqn}}
{{eqn | l = c'
      | o = \divides
      | r = a
}}
{{eqn | l = c'
      | o = \divides
      | r = b
}}
{{end-eqn}}
and:
:$d \divides a, d \divides b \implies d \divides c'$
Then we have immediately that:
:$c' \divides c$
and by the same coin:
$c \divides c'$
and so:
:$c = c'$
demonstrating that $c$ is unique.
{{qed}}
Theorem: Existence of Greatest Common Divisor

Let $a, b \in \Z$ be integers such that $a \ne 0$ or $b \ne 0$.
Then the greatest common divisor of $a$ and $b$ exists.

Proof:
From Integers form Integral Domain, we have that $\Z$ is an integral domain.
From Euclidean Domain is GCD Domain, $a$ and $b$ have a greatest common divisor $c$.
This proves existence.
From Ring of Integers is Principal Ideal Domain, we have that $\Z$ is a principal ideal domain.
Suppose $c$ and $c'$ are both greatest common divisors of $a$ and $b$.
From Greatest Common Divisors in Principal Ideal Domain are Associates:
:$c \divides c'$
and:
:$c' \divides c$
and the proof is complete.
{{qed}}
Theorem: Existence of Greatest Common Divisor

Let $a, b \in \Z$ be integers such that $a \ne 0$ or $b \ne 0$.
Then the greatest common divisor of $a$ and $b$ exists.

Proof:
From the Euclidean Algorithm, we have calculated a sequence $\tuple {r_1, r_2, \ldots r_{n - 2}, r_{n - 1}, r_n}$ such that:
:$b > r_1 > r_2 > \dotsb > r_{n - 2} > r_{n - 1} > r_n = 0$
We have that:
:$r_{n - 1} \divides a$
and:
:$r_{n - 1} \divides b$
Working backwards from the final equation, we see that:
:$r_k \divides r{k - 1}$
for all $k$ such that $1 < k \le n$.
Hence, if $d \divides a$ and $d \divides b$, we can use induction to proceed through the Euclidean Algorithm and see that $d$ divides $r_1, r_2, \ldots, r_{n - 2}, r_{n - 1}$.
Thus we see that $r_{n - 1}$ fulfils the criteria to be the greatest common divisor of $a$ and $b$.
{{qed|lemma}}
Suppose $c_1$ and $c_2$ are both greatest common divisors of $a$ and $b$.
Then by definition there exist $g, h \in \Z_{>0}$ such that:
:$g c_1 = c_2$
:$h c_2 = c_1$
Hence:
:$c_2 = g h c_2$
and so:
:$g h = 1$
That is:
:$g = h = 1$
and so:
:$c_1 = c_2$
That is, the greatest common divisor of $a$ and $b$ is unique.
{{qed}}
Theorem: Greatest Common Divisor is at least 1

Let $a, b \in \Z$ be integers.
The greatest common divisor of $a$ and $b$ is at least $1$:
:$\forall a, b \in \Z_{\ne 0}: \gcd \set {a, b} \ge 1$

Proof:
From One Divides all Integers:
:$\forall a, b \in \Z: 1 \divides a \land 1 \divides b$
and so:
:$1 \le \gcd \set {a, b}$
as required.
{{qed}}
Category:Greatest Common Divisor
2nrji97dz25wb80mslueng8xuvr7oza
Theorem: GCD of Integer and Divisor

Let $a, b \in \Z_{>0}$ be strictly positive integers.
Then:
:$a \divides b \implies \gcd \set {a, b} = a$

Proof:
We have:
:$a \divides b$ {{hypothesis}}
:$a \divides a$ from Integer Divides Itself.
Thus $a$ is a common divisor of $a$ and $b$.
Then from Absolute Value of Integer is not less than Divisors:
:$\forall x \in \Z: x \divides a \implies x \le \size a$
As $a$ and $b$ are both positive, the result follows.
{{qed}}
Theorem: GCD for Negative Integers

Let $a$ and $b$ be integers.
:$\gcd \set {a, b} = \gcd \set {\size a, b} = \gcd \set {a, \size b} = \gcd \set {\size a, \size b}$
where $\gcd$ denotes the greatest common divisor.
Alternatively, this can be put:
:$\gcd \set {a, b} = \gcd \set {-a, b} = \gcd \set {a, -b} = \gcd \set {-a, -b}$
which follows directly from the above.

Proof:
Note that $\size a = \pm a$.
Suppose that:
:$u \divides a$
where $\divides$ denotes divisibility.
Then:
:$\exists q \in \Z: a = q u$
Then:
:$\size a = \pm q u = \paren {\pm q} u \implies u \divides \size a$
So every divisor of $a$ is a divisor of $\size a$.
Similarly, note that:
:$a = \pm \size a$
so every divisor of $\size a$ is a divisor of $a$.
So it follows that the common divisors of $a$ and $b$ are the same as those of $a$ and $\size b$, and so on.
In particular:
:$\gcd \set {a, b} = \gcd \set {a, \size b}$
and so on.
{{Qed}}
Theorem: GCD with Zero

Let $a \in \Z$ be an integer such that $a \ne 0$.
Then:
:$\gcd \set {a, 0} = \size a$
where $\gcd$ denotes greatest common divisor (GCD).

Proof:
Follows from:
:Integer Divides Zero
and:
:GCD for Negative Integers.
{{qed}}
Theorem: Set of Integer Combinations equals Set of Multiples of GCD

The set of all integer combinations of $a$ and $b$ is precisely the set of all integer multiples of the GCD of $a$ and $b$:
:$\gcd \set {a, b} \divides c \iff \exists x, y \in \Z: c = x a + y b$

Proof:
=== Necessary Condition ===
Let $d = \gcd \set {a, b}$.
Then:
:$d \divides c \implies \exists m \in \Z: c = m d$
So:
{{begin-eqn}}
{{eqn | q = \exists p, q \in \Z
      | l = d
      | r = p a + q b
      | c = Bézout's Identity
}}
{{eqn | ll= \leadsto
      | l = c
      | r = m d
      | c = 
}}
{{eqn | r = m p a + m q b
      | c = 
}}
{{eqn | r = \paren {m p} a + \paren {m q} b
      | c = 
}}
{{eqn | ll= \leadsto
      | q = \exists x, y \in \Z
      | l = c
      | r = x a + y b
      | c = 
}}
{{end-eqn}}
Thus:
:$\gcd \set {a, b} \divides c \implies \exists x, y \in \Z: c = x a + y b$
{{qed|lemma}}
Theorem: GCD with Remainder

Let $a, b \in \Z$.
Let $q, r \in \Z$ such that $a = q b + r$.
Then:
:$\gcd \set {a, b} = \gcd \set {b, r}$
where $\gcd \set {a, b}$ is the greatest common divisor of $a$ and $b$.

Proof:
{{begin-eqn}}
{{eqn | o = 
      | r = \gcd \set {a, b} \divides a \land \gcd \set {a, b} \divides b
      | c = {{Defof|Greatest Common Divisor of Integers}}
}}
{{eqn | ll= \leadsto
      | o = 
      | r = \gcd \set {a, b} \divides \paren {a - q b}
      | c = Common Divisor Divides Integer Combination
}}
{{eqn | ll= \leadsto
      | o = 
      | r = \gcd \set {a, b} \divides r
      | c = as $r = a - q b$
}}
{{eqn | ll= \leadsto
      | o = 
      | r = \gcd \set {a, b} \le \gcd \set {b, r}
      | c = {{Defof|Greatest Common Divisor of Integers}}
}}
{{end-eqn}}
The argument works the other way about:
{{begin-eqn}}
{{eqn | o = 
      | r = \gcd \set {b, r} \divides b \land \gcd \set {b, r} \divides r
      | c = {{Defof|Greatest Common Divisor of Integers}}
}}
{{eqn | ll= \leadsto
      | o = 
      | r = \gcd \set {b, r} \divides \paren {q b + r}
      | c = Common Divisor Divides Integer Combination
}}
{{eqn | ll= \leadsto
      | o = 
      | r = \gcd \set {b, r} \divides a
      | c = as $a = q b + r$
}}
{{eqn | ll= \leadsto
      | o = 
      | r = \gcd \set {b, r} \le \gcd \set {a, b}
      | c = {{Defof|Greatest Common Divisor of Integers}}
}}
{{end-eqn}}
Thus:
:$\gcd \set {a, b} = \gcd \set {b, r}$
{{qed}}
Theorem: Integer Combination of Coprime Integers

Let $a, b \in \Z$ be integers, not both zero.
Then:
:$a$ and $b$ are coprime
{{iff}}:
:there exists an integer combination of them equal to $1$:
::$\forall a, b \in \Z: a \perp b \iff \exists m, n \in \Z: m a + n b = 1$
In such an integer combination $m a + n b = 1$, the integers $m$ and $n$ are also coprime.

Proof:
The proof can conveniently be divided into two parts:
Theorem: Integer Combination of Coprime Integers

Let $a, b \in \Z$ be integers, not both zero.
Then:
:$a$ and $b$ are coprime
{{iff}}:
:there exists an integer combination of them equal to $1$:
::$\forall a, b \in \Z: a \perp b \iff \exists m, n \in \Z: m a + n b = 1$
In such an integer combination $m a + n b = 1$, the integers $m$ and $n$ are also coprime.

Proof:
{{begin-eqn}}
{{eqn | q = \exists m, n \in \Z
      | l = m a + n b
      | r = 1
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \gcd \set {a, b}
      | o = \divides
      | r = 1
      | c = Set of Integer Combinations equals Set of Multiples of GCD
}}
{{eqn | ll= \leadsto
      | l = \gcd \set {a, b}
      | r = 1
      | c = 
}}
{{eqn | ll= \leadsto
      | l = a
      | o = \perp
      | r = b
      | c = {{Defof|Coprime Integers}}
}}
{{end-eqn}}
{{qed}}
Theorem: Integer Combination of Coprime Integers

Let $a, b \in \Z$ be integers, not both zero.
Then:
:$a$ and $b$ are coprime
{{iff}}:
:there exists an integer combination of them equal to $1$:
::$\forall a, b \in \Z: a \perp b \iff \exists m, n \in \Z: m a + n b = 1$
In such an integer combination $m a + n b = 1$, the integers $m$ and $n$ are also coprime.

Proof:
Let $a, b \in \Z$ be such that $\exists m, n \in \Z: m a + n b = 1$.
Let $d$ be a divisor of both $a$ and $b$.
Then:
:$d \divides m a + n b$
and so:
:$d \divides 1$
Thus:
:$d = \pm 1$
and so:
:$\gcd \set {a, b} = 1$
Thus, by definition, $a$ and $b$ are coprime.
{{qed}}
Theorem: Integer Combination of Coprime Integers

Let $a, b \in \Z$ be integers, not both zero.
Then:
:$a$ and $b$ are coprime
{{iff}}:
:there exists an integer combination of them equal to $1$:
::$\forall a, b \in \Z: a \perp b \iff \exists m, n \in \Z: m a + n b = 1$
In such an integer combination $m a + n b = 1$, the integers $m$ and $n$ are also coprime.

Proof:
{{begin-eqn}}
{{eqn | l = a
      | o = \perp
      | r = b
}}
{{eqn | ll= \leadsto
      | l = \gcd \set {a, b}
      | r = 1
      | c = {{Defof|Coprime Integers}}
}}
{{eqn | ll= \leadsto
      | q = \exists m, n \in \Z
      | l = m a + n b
      | r = 1
      | c = Bézout's Identity
}}
{{end-eqn}}
{{qed}}
Theorem: Integer Combination of Coprime Integers

Let $a, b \in \Z$ be integers, not both zero.
Then:
:$a$ and $b$ are coprime
{{iff}}:
:there exists an integer combination of them equal to $1$:
::$\forall a, b \in \Z: a \perp b \iff \exists m, n \in \Z: m a + n b = 1$
In such an integer combination $m a + n b = 1$, the integers $m$ and $n$ are also coprime.

Proof:
Let $a \perp b$.
Thus they are not both $0$.
Let $S$ be defined as:
:$S = \set {a m + b n: m, n \in \Z}$
$S$ contains at least one strictly positive integer, because for example $a^2 + b^2 \in S$.
By Set of Integers Bounded Below has Smallest Element, let $d$ be the smallest element of $S$ which is strictly positive.
Let $d = a x + b y$.
It remains to be shown that $d = 1$.
By the Division Theorem:
:$a = d q + r$ where $0 \le r < d$
Then:
{{begin-eqn}}
{{eqn | l = r
      | r = a - d q
      | c = 
}}
{{eqn | r = a - \paren {a x + b y} q
      | c = 
}}
{{eqn | r = a \paren {1 - x q} + b \paren {- y q}
      | c = 
}}
{{eqn | o = \in
      | r = S
      | c = 
}}
{{end-eqn}}
But we have that $0 \le r < d$.
We have defined $d$ as the smallest element of $S$ which is strictly positive
Hence it follows that $r$ cannot therefore be strictly positive itself.
Hence $r = 0$ and so $a = d q$.
That is:
:$d \divides a$
By a similar argument:
:$d \divides b$
and so $d$ is a common divisor of both $a$ and $b$.
But the GCD of $a$ and $b$ is $1$.
Thus it follows that, as $d \in S$:
:$\exists m, n \in \Z: m a + n b = 1$
{{qed}}
Theorem: Integer Combination of Coprime Integers

Let $a, b \in \Z$ be integers, not both zero.
Then:
:$a$ and $b$ are coprime
{{iff}}:
:there exists an integer combination of them equal to $1$:
::$\forall a, b \in \Z: a \perp b \iff \exists m, n \in \Z: m a + n b = 1$
In such an integer combination $m a + n b = 1$, the integers $m$ and $n$ are also coprime.

Proof:
Let $a \perp b$.
Thus they are not both $0$.
Let $S$ be defined as:
:$S = \set {\lambda a + \mu b: \lambda, \mu \in \Z}$
$S$ contains at least one strictly positive integer, because for example:
:$a \in S$ (setting $\lambda = 1$ and $\mu = 0$)
:$b \in S$ (setting $\lambda = 0$ and $\mu = 1$)
By Set of Integers Bounded Below has Smallest Element, let $d$ be the smallest element of $S$ which is strictly positive.
Let $d = \alpha a + \beta b$.
Let $c \in S$, such that $\lambda_0 a + \mu_0 b = c$ for some $\lambda_0, \mu_0 \in \Z$.
By the Division Algorithm:
:$\exists \gamma, \delta \in \Z: c = \gamma d + \delta$
where $0 \le \delta < d$
Then:
{{begin-eqn}}
{{eqn | l = \delta
      | r = c - \gamma d
      | c = 
}}
{{eqn | r = \paren {\lambda_0 a + \mu_0 b} - \gamma \paren {\alpha a + \beta b}
      | c = 
}}
{{eqn | r = \paren {\lambda_0 - \gamma \alpha} a + \paren {\mu_0 - \gamma \beta} b
      | c = 
}}
{{eqn | o = \in
      | r = S
      | c = 
}}
{{end-eqn}}
But we have that $0 \le \delta < d$.
We have defined $d$ as the smallest element of $S$ which is strictly positive
Hence it follows that $\delta$ cannot therefore be strictly positive itself.
Hence $\delta = 0$ and so $c = \gamma d$.
That is:
:$d \divides c$
and so the smallest element of $S$ which is strictly positive is a divisor of both $a$ and $b$.
But $a$ and $b$ are coprime.
Thus it follows that, as $d \divides 1$:
:$d = 1$
and so, by definition of $S$:
:$\exists m, n \in \Z: m a + n b = 1$
{{qed}}
Theorem: Divisor of Sum of Coprime Integers

Let $a, b, c \in \Z_{>0}$ such that:
:$a \perp b$ and $c \divides \paren {a + b}$.
where:
:$a \perp b$ denotes $a$ and $b$ are coprime
:$c \divides \paren {a + b}$ denotes that $c$ is a divisor of $a + b$.
Then $a \perp c$ and $b \perp c$.
That is, a divisor of the sum of two coprime integers is coprime to both.

Proof:
Let $d \in \Z_{>0}: d \divides c \land d \divides a$.
Then:
{{begin-eqn}}
{{eqn | l = d
      | o = \divides
      | r = \paren {a + b}
      | c = as $c \divides \paren {a + b}$
}}
{{eqn | ll= \leadsto
      | l = d
      | o = \divides
      | r = \paren {a + b - a}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = d
      | o = \divides
      | r = b
      | c = 
}}
{{eqn | ll= \leadsto
      | l = d
      | r = 1
      | c = as $d \divides a$ and $d \divides b$ which are coprime
}}
{{end-eqn}}
A similar argument shows that if $d \divides c \land d \divides b$ then $d \divides a$.
It follows that:
:$\gcd \set {a, c} = \gcd \set {b, c} = 1$
Hence the result.
{{qed}}
Theorem: Integers Divided by GCD are Coprime

Let $a, b \in \Z$ be integers which are not both zero.
Let $d$ be a common divisor of $a$ and $b$, that is:
:$\dfrac a d, \dfrac b d \in \Z$
Then:
:$\gcd \set {a, b} = d$
{{iff}}:
:$\gcd \set {\dfrac a d, \dfrac b d} = 1$
that is:
:$\dfrac a {\gcd \set {a, b} } \perp \dfrac b {\gcd \set {a, b} }$
where:
:$\gcd$ denotes greatest common divisor
:$\perp$ denotes coprimality.

Proof:
Let $d = \gcd \set {a, b}$.
By definition of divisor:
:$d \divides a \iff \exists s \in \Z: a = d s$
:$d \divides b \iff \exists t \in \Z: b = d t$
So:
{{begin-eqn}}
{{eqn | q = \exists m, n \in \Z
      | l = d
      | r = m a + n b
      | c = Bézout's Identity
}}
{{eqn | ll= \leadstoandfrom
      | l = d
      | r = m d s + n d t
      | c = Definition of $s$ and $t$
}}
{{eqn | ll= \leadstoandfrom
      | l = 1
      | r = m s + n t
      | c = dividing through by $d$
}}
{{eqn | ll= \leadstoandfrom
      | l = \gcd \set {s, t}
      | r = 1
      | c = Bézout's Identity
}}
{{eqn | ll= \leadstoandfrom
      | l = \gcd \set {\frac a d, \frac b d}
      | r = 1
      | c = Definition of $s$ and $t$
}}
{{end-eqn}}
{{qed}}