Greatest Common Divisor
suppose that $$a , b \in \mathbb{Z}$$ such that $$\left( a, b \right) \neq \left( 0, 0 \right)$$, then the greatest common divisor of $$a$$ and $$b$$ notated as $$\gcd{\left ( a , b \right )}$$ is the largest positive integer that divides each of $$a , b$$

Therefore $$\gcd : \mathbb{ Z } \times \mathbb{ Z } \to \mathbb{ N } _ 1$$

GCD's Characterization
Let $$a, b \in \mathbb{ Z }$$, and let $$g \in \mathbb{ Z }$$ sugh that $$g \mid a \land g \mid b$$ and $\forall d \in \mathbb{ N } _ 1, \left( d \mid a \land d \mid b \right) \implies d \le g$ if and only if $$g = \gcd \left( a, b \right)$$

Note that since $$d \mid g \implies d \le g$$ we may use $$d \mid g$$ on the right hand side of the implication

GCD is a Linear Combination
For any $$a, b \in \mathbb{ Z } ^ { \neq 0 }$$, there exist integers $$s, t \in \mathbb{ Z }$$ such that $$\gcd \left( a, b \right) = as + bt$$, moreover $$\gcd \left( a, b \right)$$ is the smallest such positive integer of the form $$as + bt$$

Define $$S := \left\{ am + bn: m, n \in \mathbb{ Z } \text{ and } am + bn > 0\right\}$$, we first note that $$S$$ cannot be empty. The only way it could be empty would be if that given any choice of $$m, n$$ we have $$am + bn < 0$$, but if that's the case we can always see that $$- \left( am + bn \right) > 0$$ and note that $$- \left( am + bn \right) = a \left( -m \right) + b \left( -n \right)$$, which shows that there is an element in $$S$$.

Since $$S \subseteq \mathbb{ N } _ 0$$, the well ordering principle tells us that there is some smallest element of $$S$$, say $$d = a j + b k$$. We will prove that $$\gcd \left( a, b \right) = d$$.

By the quotient remainder theorem, we have some $$q, r$$ such that $$a = qd + r$$ where $$0 \le r < d$$, from here we can see that \begin{aligned} r &= a - qd \\ &= a - q \left( aj + bk \right) \\ &= a \left( 1 - qj \right) + b \left( qk \right) \end{aligned} at this point in time if $$r > 0$$, then we would have a contradiction because $$r$$ would be a value smaller than $$d$$ that is an element of $$S$$, but we assumed that $$d$$ was the smallest such element. Therefore, the only way forward is that $$r = 0$$

If $$r = 0$$, then $$a = qd$$ meaning that $$d$$ divides $$a$$, by copying the above text and replacing the variable $$a$$ with $$b$$ we obtain a proof that $$d$$ divides $$b$$ as well. To complete showing that $$d = \gcd \left( a, b \right)$$ we need to prove that $$d$$ is the smallest divisor.

Suppose that $$m$$ is another common divisor of $$a, b$$, then we have $$k_a, k_b \in \mathbb{ Z }$$, such that $$a = k_a m$$ and $$b = k_b m$$, from $$d$$'s definition we see $$d = a j + bk = \left( k_a m \right) j + \left( k_b m \right) k = m \left( k_a j + k_b k \right)$$, this shows that $$m \mid d$$ so that $$m \le d$$ showing that $$d$$ is the largest divisor and we conclude $$d = \gcd \left( a, b \right)$$

Relatively Prime implies there is a Linear Combination of One
If $$a, b$$ are relatively prime, then there exists $$s, t \in \mathbb{ Z }$$ such that $$1 = as + bt$$
By the definition of $$a, b$$ being reliatively prime, we know that $$\gcd \left( a, b \right) = 1$$, then we know that there are integers $$s, t$$ such that $$\gcd \left( a, b \right) = as + bt$$
Factoring GCD
For any $$k , a, b \in \mathbb{ Z }$$ such that $$k \neq 0$$ we have $\gcd \left( ka, kb \right) = \left\lvert k \right\rvert \gcd \left( a, b \right)$
Forced Division through GCD
Suppose we have $$n, a, b \in \mathbb{Z}$$ and that $$\gcd (a, n) = 1$$, then if $$n \mid a b$$ then $$n \mid b$$
The gcd is a linear combination, and therefore $$ax + ny = 1$$ so that $$abx + nby = b$$ since $$n \mid ab$$ then we have some $$k \in \mathbb{ Z }$$ such that $$ab = nk$$ therefore $$nkx + nby = b$$ so that $$n \left( kx + by \right) = b$$ so therefore $$n \mid b$$
If you Can find a Linear Combination that Yields One, then Their gcd is one
Let $$a, b \in \mathbb{ Z }$$, there exists $$x, y \in \mathbb{ Z }$$ such that $ax + by = 1$ if and only if $$\gcd \left( a, b \right) = 1$$
$$\implies$$ Suppose we have a $$d \in \mathbb{ Z }$$ such that $$d \mid a, b$$ then we know that $$d \mid ax + by = 1$$, therefore $$d = \pm 1$$, therefore by definition $$\gcd \left( a, b \right) = 1$$. $$\impliedby$$ We know this because gcd is a linear combination
Swapping Factors
Prove that for any $$a \in \mathbb{ Z }$$ we have $\gcd \left( 5 a + 2, 7a + 3 \right) = 1$
Observe that $$\left( 5a + 2 \right) \left( -7 \right) + \left( 7 a + 3 \right) 5 = -35a + 35a - 14 + 15 = 1$$ and therefore $$\gcd \left( 5a + 2, 7a + 3 \right) = 1$$ as needed.
Coefficients have GCD one
Suppose that $$\gcd \left( a, b \right) = g$$ and thus we have some $$x, y \in \mathbb{ Z }$$ such that $$ax + b y = g$$ then $$\gcd \left( x, y \right) = 1$$
$ax + b y = g \iff \left( \frac{a}{g} \right) x + \left( \frac{b}{g} \right) y = 1$ therefore $$\gcd \left( x, y \right) = 1$$
Dividing out by GCD removes all Common Factors
Suppose $$a, b \in \mathbb{ Z }$$ and let $$d := \gcd \left( a, b \right)$$ then $\gcd \left( \frac{a}{d} , \frac{b}{d} \right) = 1$
We know that the gcd is a linear combination, so we get some $$x, y \in \mathbb{ Z }$$ such that $$d = ax + by$$ therefore $1 = \left( \frac{a}{d} \right) x + \left( \frac{b}{d} \right) y$ therefore by the previous proposition we see that $$\gcd \left( \frac{a}{d} , \frac{b}{d} \right) = 1$$
Rational in Lowest Terms
A rational number $$r \in \mathbb{ Q }$$ written as a fraction $$r = \frac{a}{b}$$ is said to be in lowest terms if $$\gcd \left( a, b \right) = 1$$
Lowest Terms Rational Always Exists
For any $$r \in \mathbb{ Q }$$ it can be represented in lowest terms
Suppose $$r = \frac{a}{b} \in \mathbb{ Q }$$ and let $$d = \gcd \left( a, b \right)$$ and consider $\frac{a}{b} = \left( \frac{\frac{1}{d} }{\frac{1}{d} } \right) \left( \frac{a}{d} \right) = \frac{\frac{a}{d} }{\frac{b}{d}}$ and since we know that $$\gcd \left( \frac{a}{d} , \frac{b}{d} \right) = 1$$ we've proven the statement true
Non Trivial Divisors
Let $$n \in \mathbb{ Z }$$ such that $$\left\lvert n \right\rvert \ge 2$$ then we define $\operatorname{ ntd } \left( n \right) = \left\{ d \in \mathbb{ N } _ 2 : d \mid n \right\}$
Non Trivial Divisors is a Subset of 2 up to The Number
For any $$n \in \mathbb{ Z }$$ such that $$\left\lvert n \right\rvert \ge 2$$ then we have $\operatorname{ ntd } \left( n \right) \subseteq \left[ 2, \ldots , n \right]$
The Non Trivial Divisors of n Factorial Plus or Minus One
Suppose that $$n \in \mathbb{ N } _ 1$$ then $\operatorname{ ntd } \left( n! + 1 \right) \subseteq \left[ n + 1, \ldots , n! + 1 \right]$
Let $$d \in \operatorname{ ntd } \left( n ! + 1 \right)$$ then we know that $$d \in \left[ 2, \ldots , n! + 1 \right]$$ but if $$d \in \left[ 2, \ldots , n \right]$$ then we already know that $$d \nmid n! + 1$$ which is a contradiction, therefore we must have that $$d \in \left[ n + 1, \ldots n! + 1 \right]$$ as needed.
Common Divisor Set
Suppose that $$a, b \in \mathbb{ Z }$$ then we define $\operatorname{ cd } \left( a, b \right) = \left\{ d \in \mathbb{ Z } : d \mid a \land d \mid b \right\}$
Common Divisors as the Intersection of the Non Trivial Divisors
Suppose that $$a, b \in \mathbb{ Z }$$ then $\operatorname{ cd } \left( a, b \right) = \operatorname{ ntd } \left( a \right) \cap \operatorname{ ntd } \left( b \right) \cup \left\{ 1 \right\}$
Common Divisor Set is Bounded Above
$\operatorname{ cd } \left( a, b \right) \le \min \left( a, b \right)$
Add a multiple of the other Yields Same Common Divisors
For any $$a, b, k \in \mathbb{ Z }$$ $\operatorname{ cd } \left( a , b \right) = \operatorname{ cd } \left( a, b + k a \right)$

$$\subseteq$$ Suppose $$d \mid a, b$$ therefore $$d \mid a + k a$$ as needed. $$\supseteq$$ now suppose that $$d \mid a, b + ka$$ since $$d \mid a$$ then $$d \mid ka$$ and therefore $$d \mid \left( b + ka \right) - ka = b$$ therefore $$d \in \operatorname{ cd } \left( a, b \right)$$

No Common Non Trivial Divisors Implies Relatively Prime
Suppose $$a, b \in \mathbb{ Z }$$ then $\operatorname{ ntd } \left( a \right) \cap \operatorname{ ntd } \left( b \right) = \emptyset \implies \gcd \left( a, b \right) = 1$
Superset Divisors Implies Greater GCD
For any $$a, b, p, q \in \mathbb{ Z }$$ $\operatorname{ cd } \left( a, b \right) \subseteq \operatorname{ cd } \left( p, q \right) \implies \gcd \left( a, b \right) \le \gcd \left( p, q \right)$
For any $$X \subseteq Y \subseteq \mathbb{ Z }$$ then $$\max \left( X \right) \lt \max \left( Y \right)$$ therefore we have $\gcd \left( a, b \right) = \max \left( \operatorname{ cd } \left( a, b \right) \right) \le \max \left( \operatorname{ cd } \left( p, q \right) \right) = \gcd \left( p, q \right)$ so that $$\gcd \left( a, b \right) \le \gcd \left( p, q \right)$$ as needed.
Same Divisors Implies same GCD
Suppose that $$a , b , p , q \in \mathbb{Z}$$, then $\operatorname{ cd } \left( a, b \right) = \operatorname{ cd } \left( p, q \right) \implies \gcd \left( a, b \right) = \gcd \left( p, q \right)$
Since $$\operatorname{ cd } \left( a, b \right) = \operatorname{ cd } \left( p, q \right)$$ then we know that $$\operatorname{ cd } \left( a, b \right) \subseteq \operatorname{ cd } \left( p, q \right)$$ and that $$\operatorname{ cd } \left( a, b \right) \supseteq \operatorname{ cd } \left( p, q \right)$$ so that we have $$gcd \left( a, b \right) \le \gcd \left( p, q \right)$$ and $$\gcd \left( a, b \right) \ge \gcd \left( a, b \right)$$ so that $$\gcd \left( a, b \right) = \gcd \left( p, q \right)$$ as needed.
Add a multiple of the other Yields same GCD
For any $$a, b, k \in \mathbb{ Z }$$ we have $\gcd \left( a, b \right) = \gcd \left( a, b + ka \right)$
Since the common divisors are the same, then the gcd of the two is the same
Let $$n \in \mathbb{ Z }$$ then $\gcd \left( n, n + 1 \right) = 1$
Suppose that there existed some $$d \in \mathbb{ N } _ 2$$ such that $$d \mid n$$ and $$d \mid n + 1$$ then we would have $$d \mid n + 1 - n = 1$$ which implies that $$d = \pm 1$$ which is a contradiction, thus the only divisor of $$n$$ and $$n + 1$$ is one, so that $$\gcd \left( n, n + 1 \right) = 1$$
Division by Individuals Implies Division by Product when GCD is one
Suppose $$\gcd \left( a, b \right) = 1$$ then $\left( a \mid c \land b \mid c \right) \implies ab \mid c$
The gcd is a linear combintion of $$a, b$$ so $$a x + by = 1$$ for some $$x, y \in \mathbb{ z }$$ but then $acx + bcy = c$ but recall that $$a \mid c$$ and $$b \mid c$$ so we have $$k _ a, k _ b \in \mathbb{ Z }$$ such that $$c = k _ a a$$ and $$c = k _ b b$$ subbing each of these equations into the above equation we have $a \left( b k _ b \right) x + b \left( a k _ a \right) y = c$ so therefore $$\left( a b \right) \left( k _ b x + k _ a y \right) = c$$ so that $$ab \mid c$$ as needed.
GCD of a Multiple is Greater
For any $$a, b ,k \in \mathbb{ Z }$$ we have: $\gcd \left( a, b \right) \le \gcd \left( k a, b \right)$
Recall this, therefore we can show that $$\operatorname{ cd } \left( a, b \right) \subseteq \operatorname{ cd } \left( ak , b \right)$$ thus $$\gcd \left( a, b \right) \le \gcd \left( ka, b \right)$$
A Divisor of a Coprime number Is also Coprime
Suppose that $$a, b, d \in \mathbb{ Z }$$ such that $$\gcd \left( a, b \right) = 1$$ and $$d \mid a$$ then $$\gcd \left( d, b \right) = 1$$
Let $$g := \gcd \left( b, d \right)$$ clearly $$g \mid d$$ and since $$d \mid a$$ then $$g \mid a$$, also we know that $$g \mid b$$ and therefore $$g$$ is a common divisor of $$a, b$$ and therefore $$g = 1$$, as needed.
Relatively Prime Factors Implies Relatively Prime Product
Suppose that $$\gcd \left( a, b \right) = 1$$ and $$\gcd \left( a, c \right) = 1$$ then $$\gcd \left( a, bc \right) = 1$$
We have some $$x _ 1, x _ 2, y _ 1, y _ 2$$ such that $a x _ 1 + b y _ 1 = 1 = a x _ 2 + c y _ 2$ So then \begin{align} 1 &= \left( a x _ 1 + b y _ 1 \right) \left( a x _ 2 + c y _ 2 \right) \\ &= a ^ 2 x _ 1 x _ 2 + a x _ 1 c y _ 2 + b y _ 1 a x _ 2 + b c y _ 1 y _ 2 \\ &= a \left( a x _ 1 x _ 2 + x _ 1 b y _ 2 + b y _ 1 x _ 2 \right) + bc \left( y _ 1 y _ 2 \right) \end{align} so therefore $$\gcd \left( a, bc \right) = 1$$
GCD of a Factorial
Suppose that $$n \in \mathbb{ N } _ 1$$, determine $\gcd \left( n! + 1 , \left( n + 1 \right)! + 1 \right)$
We know that \begin{align} \gcd \left( n! + 1 , \left( n + 1 \right)! + 1 \right) &= \gcd \left( n! + 1, \left( n! + 1 \right) ! + 1 - \left( n! + 1 \right) \right) \\ &= \gcd \left( n! + 1, \left( n + 1 \right)! - n! \right) \\ &= \gcd \left( n! + 1 , n! \left( n + 1 - 1\right) \right) \\ &= \gcd \left( n! + 1 , n! n \right) \\ \end{align}

Note that $\operatorname{ ntd } \left( n ! + 1 \right) \cap \operatorname{ ntd } \left( n \right) = \emptyset$ because $$\operatorname{ ntd } \left( n! + 1 \right) \subseteq \left[ n + 1, \ldots , n ! + 1 \right]$$ and that $$\operatorname{ ntd } \left( n \right) \subseteq \left[ 2, \ldots , n \right]$$, therefore $\gcd \left( n! + 1 , n \right) = 1$ we also know that $$\gcd \left( n! + 1, n! \right) = 1$$ therefore $\gcd \left( n! + 1 , n n! \right) = 1$

Coprime
$$a , b \in \mathbb{Z}$$ are said to be coprime if the only positive integer that divides them is $$1$$.
Coprime GCD Characterization
$$a , b \in \mathbb{Z}$$ are coprime if and only if $$\gcd{\left ( a , b \right )} = 1$$
$$\implies$$ If $$a, b$$ are coprime, then $$D _ { a, b } = \left\{ 1, -1 \right\}$$ and therefore $$\gcd \left( a, b \right) = 1$$ as needed. $$\impliedby$$ if $$\gcd \left( a, b \right) = 1$$ then the only positive integer that divides them is $$1$$ because if some other positive integer divided both of them then $$\gcd \left( a, b \right) \gt 1$$ which would be a contradiction.
Least Common Multiple
Suppose that $$a , b \in \mathbb{Z}$$ then the least common multiple of $$a$$ and $$b$$ notated as $$\operatorname{ lcm } \left ( a , b \right)$$ is the smallest positive integer such that $$a, b \mid \operatorname{ lcm } \left( a, b \right)$$
Least Common Multiple Characterization
The lcm $$l := \operatorname{ lcm } \left( a, b \right)$$ is the unique number satisfying
• $$a, b \mid l$$
• For every $$m \in \mathbb{ Z } ^ +, \left( a, b \mid m \right) \implies l \le m$$

Similarly we may replace $$l \le m$$ with $$l \mid m$$ since it implies $$l \le m$$.

GCD and LCM Connection
$\gcd \left( a, b \right) \operatorname{ lcm } \left( a, b \right) = ab$

For simplicity let $$g, l$$ denote the the gcd and lcm respectively, then we're trying to prove that $$l = \frac{ab}{g}$$ we'll do that using the characterization, so note that $$l = a \left( \frac{b}{d} \right) = b \left( \frac{a}{d} \right)$$ and that $$\frac{b}{d} , \frac{a}{d} \in \mathbb{ Z }$$ since $$d$$ divides both by definition, thus $$a, b \mid l$$.

Now suppose that there is some $$m \in \mathbb{ Z } ^ +$$ such that $$a , b \mid m$$ in other words there exists some $$k _ a, k _ b \in \mathbb{ Z }$$ such that $$m = a k _ a = b k _ b$$ we'll show that $$l \le m$$. Recall that $$d \mid a, b$$ and so we get some $$\alpha , \beta \in \mathbb{ Z }$$ such that $$a = \alpha d$$ and $$b = \beta d$$ therfore $m = a k _ a = b k _ b \iff \left( \alpha d \right) k _ a = \left( \beta d \right) k _ b \iff \alpha k _ a = \beta k _ b$

The above equation shows that $$\alpha \mid \beta k _ b$$ and $$\beta \mid \alpha k _ a$$, but note that $$\gcd \left( \alpha , \beta \right) = \gcd \left( \frac{a}{d} , \frac{b}{d} \right) = 1$$ therefore by the previous proposition we must have that $$\alpha \mid k _ b$$ and $$\beta \mid k _ a$$ therefore there is some $$j \in \mathbb{ Z }$$ such that $$k _ b = j \alpha$$ thus finally $m = b k _ b = b j \alpha = b \left( \frac{a}{d} \right) j = l j$ therefore $$l \mid m$$ so that $$l \le m$$. Therefore $$l = \frac{ab}{g}$$ and thus $$g l = ab$$ as needed.

Divisor Function is a Bijection if Relatively Prime
For $$n \in \mathbb{ N } _ 1$$ let $$D _ n$$ denote its set of positive divisors $$D _ n := \left\{ a \mid n: a \in \mathbb{ N } _ 1 \right\}$$, prove that for any $$m, n \in \mathbb{ N } _ 1$$ that $$f: D _ n \times D _ m \to D _ { n m }$$ defined as $f \left( a, b \right) = ab$ is well defined, and is a bijection if $$\gcd \left( m, n \right) = 1$$

Recall that a function is well defined if given two equal inputs it cannot map to a different value, this is true simply because for any $$a, b$$ $$a \cdot b$$ is equal to exactly one value. Additionally note that given a divisor of $$m$$ and a divisor of $$n$$ then their product divides $$m n$$ so under the given definition it respects the functions signature.

Now suppose that $$\gcd \left( m, n \right) = 1$$ we want to prove that $$f$$ is a bijection. First we show that it is injective, so suppose that $$f \left( a, b \right) = f \left( c, d \right)$$ and we will prove that $$\left( a, b \right) = \left( c, d \right)$$ the first equality we assumed really means that $$ab = cd$$, but we also know that $$a, c \mid n$$ and that $$b, d \mid m$$ therefore we know that $$\gcd \left( a, d \right) = \gcd \left( b, c \right) = 1$$ but from the equation $$ab = cd$$ we see that $$a \mid cd$$ so that $$a \mid c$$, but on the other hand $$c \mid ab$$ so that $$c \mid a$$ so we conclude that $$a = c$$ similarly we conclude that $$b = d$$ so that $$\left( a, b \right) = \left( c, d \right)$$ as needed.

Now we show that it is surjective so let $$x \in D _ { m n }$$ we need to find a $$\left( j, k \right)$$ that gets mapped to $$x$$ since $$gcd \left( m, n \right) = 1$$ then we know that since $$x \mid m, n$$ then $$x = d _ n d _ m$$ where $$d _ n, d _ m$$ are divisors of $$n , m$$ respectively, thus $$f \left( d _ n, d _ m \right) = x$$